#pragma GCC optimize('Ofast')
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define int long long
using namespace std;
using namespace __gnu_pbds;

template <typename T>
using ordered_set = tree<T, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;
struct fenw {
    vector<int> f;
    explicit fenw(int n) {
        f.resize(n);
    }
    void upd(int i, int x) {
        while (i < f.size()) {
            f[i] += x;
            i |= (i + 1);
        }
    }
    int get(int i) {
        int sum = 0;
        while (i >= 0) {
            sum += f[i];
            i &= (i + 1);
            i--;
        }
        return sum;
    }
    int get(int l, int r) {
        return get(r) - get(l - 1);
    }
};
template <typename T>
bool smin(T& a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template <typename T>
bool smax(T& a, T b) {
    if (b > a) {
        a = b;
        return true;
    }
    return false;
}
vector<vector<pair<int, int>>> g;
vector<int> used;
vector<int> t;
vector<vector<int>> r;
int mk;
void dfs(int v) {
    used[v] = 1;
    for (auto [e, i] : g[v]) {
        if (!used[e] && r[i][((mk >> i) & 1)] == v) {
            dfs(e);
        }
    }
    t.push_back(v);
}
vector<int> c;
void kss(int v, int col) {
    c[v] = col;
    for (auto [e, i] : g[v]) {
        if (!c[e] && r[i][((mk >> i) & 1)] != v) {
            kss(e, col);
        }
    }
}
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, _;
    cin >> n >> m >> _;
    g.resize(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v, u--, v--;
        g[u].emplace_back(v, i);
        g[v].emplace_back(u, i);
        r.push_back({u, v});
    }
    c.assign(n, 0);
    used.assign(n, 0);
    mk = 0;
    for (int i = 0; i < n; i++) {
        if (!used[i]) dfs(i);
    }
    reverse(t.begin(), t.end());
    int col = 1;
    for (int i = 0; i < n; i++) {
        if (!c[t[i]]) {
            kss(t[i], col++);
        }
    }
    vector<vector<int>> IZN(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (c[i] == c[j]) IZN[j].push_back(i);
        }
    }
    for (int i = 0; i < n; i++) sort(IZN[i].begin(), IZN[i].end());
    vector<int> cntt((1 << m), 1);
    for (int mask = 1; mask < (1 << m); mask++) {
        mk = mask;
        int cnt = 0;
        for (int i = 0; i < m; i++) cnt += (mask >> i) & 1;
        used.assign(n, 0);
        c.assign(n, 0);
        t.clear();
        for (int i = 0; i < n; i++) {
            if (!used[i]) dfs(i);
        }
        reverse(t.begin(), t.end());
        int col = 1;
        for (int i = 0; i < n; i++) {
            if (!c[t[i]]) {
                kss(t[i], col++);
            }
        }
        vector<vector<int>> ne(n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (c[i] == c[j]) ne[j].push_back(i);
            }
        }
        for (int i = 0; i < n; i++) sort(ne[i].begin(), ne[i].end());
        if (IZN == ne) {
            mk = ((1 << m) - 1) ^ mk;
            for (int sub = mk; sub > 0; sub--, sub &= mk) cntt[sub] = 0;
            cntt[0] = 0;
        }
    }
    for (int len = 0; len <= m; len++) {
        int flag = 0;
        for (int mask = 0; mask < (1 << m); mask++) {
            int cnt = 0;
            for (int i = 0; i < m; i++) cnt += (mask >> i) & 1;
            if (cnt != len) continue;
            flag += cntt[mask];
        }
        if (flag) {
            cout << len << ' ' << flag << '\n';
            return 0;
        }
    }
    return 0;
}