#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

void fast_in_out() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}

#define int long long
#define all(x) (x).begin(), (x).end()
using ll = long long;
using ull = long long;
using ld = long double;
typedef tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int N = 2e3;
vector<int> g[N];
pair<int, int> ed[N];
int n, m, G;
int d[N][N];

void dfs(int v, int lead) {
    d[lead][v] = 1;
    for (auto to: g[v]) {
        if (d[lead][to] == 0) {
            dfs(to, lead);
        }
    }
}

int p[N], sz[N];

int par(int v) {
    return p[v] = (p[v] == v ? v : par(p[v]));
}

void unite(int x, int y) {
    x = par(x);
    y = par(y);
    if (x != y) {
        if (sz[x] < sz[y]) {
            swap(x, y);
        }
        sz[x] += sz[y];
        p[y] = x;
    }
}

vector<vector<int>> komp() {
    for (int i = 0; i < n; ++i) {
        sz[i] = 1;
        p[i] = i;
        for (int j = 0; j < n; ++j) {
            d[i][j] = 0;
        }
    }
    for (int i = 0; i < n; ++i) {
        dfs(i, i);
    }
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (d[i][j] && d[j][i]) {
                unite(i, j);
            }
        }
    }
    vector<vector<int>> vec(n);
    for (int i = 0; i < n; ++i) {
        vec[par(i)].emplace_back(i);
    }
    sort(all(vec));
    return vec;
}

int b[1 << 20];

void solve() {
    cin >> n >> m >> G;
    for (int i = 0; i < m; ++i) {
        cin >> ed[i].first >> ed[i].second;
        --ed[i].first;
        --ed[i].second;
    }
    vector<vector<int >> Vec;
    for (int mask = 0; mask < (1 << m); ++mask) {
        for (int i = 0; i < m; ++i) {
            if ((mask >> i) & 1) {
                g[ed[i].second].emplace_back(ed[i].first);
            } else {
                g[ed[i].first].emplace_back(ed[i].second);
            }
        }
        vector<vector<int >> vec = komp();
        if (mask == 0) {
            Vec = vec;
        }
        if (Vec == vec) {
            b[mask] = 1;
        }
        for (int i = 0; i < n; ++i) {
            g[i].clear();
        }
    }
    int ans1 = 0, ans2 = 0;
    for (int mask = 0; mask < (1 << m); ++mask) {
        int kol = 0;
        for (int i = 0; i < m; ++i) {
            if ((mask >> i) & 1) {
                ++kol;
            }
        }
        if (kol < ans1) {
            continue;
        }
        int ok = 1;
        for (int mask1 = 1; mask1 < (1 << m); ++mask1) {
            if (((mask1 & mask) ^ mask1) == 0 && b[mask1] == 1) {
                ok = 0;
                break;
            }
        }
        if (!ok) {
            continue;
        }
        if (ans1 == kol) {
            ++ans2;
        } else if (ans1 < kol) {
            ans1 = kol;
            ans2 = 1;
        }
    }
    cout << ans1 << '\n' << ans2;
}

signed main() {
    fast_in_out();
    int qwe = 1;
//    cin >> qwe;
    while (qwe--) {
        solve();
    }
    return 0;
}
