#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <cmath>
#include <algorithm>

using namespace std;

typedef long long ll;

void dfs_ts(int v, vector<vector<pair<int, int>>> &g, vector<int> &ts, vector<int> &used, int fix, int mask) {
    used[v] = 1;
    for (auto [u, id] : g[v]) {
        //cout << id << ' ';
        if (used[u] /*|| (id > 0 && ((mask >> (id - 1)) & 1)) || (id < 0 && ((fix >> (- id + 1)) & 1))*/) {
            continue;
        }
        //cout << id << ' ';
        dfs_ts(u, g, ts, used, fix, mask);
    }
    ts.emplace_back(v);
}

void paint(int v, vector<vector<pair<int, int>>> &g, int c, vector<int> &comp, int fix, int mask) {
    comp[v] = c;
    for (auto [u, id] : g[v]) {
        if (comp[u] != -1 /*|| (id > 0 && ((mask >> (id - 1)) & 1)) || (id < 0 && ((fix >> (- id + 1)) & 1))*/) {
            continue;
        }
        //cout << id << ' ';
        paint(u, g, c, comp, fix, mask);
    }
}

vector<int> get_comp(int n, int m, vector<pair<int, int>> &edges, int fix, int mask) {
    vector<vector<pair<int, int>>> g(n), rg(n);
    for (int i = 0; i < m; ++i) {
        auto [v, u] = edges[i];
        if (((fix >> i) & 1) || !((mask >> i) & 1)) {
            g[v].emplace_back(u, i);
            rg[u].emplace_back(v, i);
        } else {
            g[u].emplace_back(v, i);
            rg[v].emplace_back(u, i);
        }
    }
    vector<int> ts, used(n);
    for (int v = 0; v < n; ++v) {
        if (!used[v]) {
            dfs_ts(v, g, ts, used, fix, mask);
        }
    }
    //cout << endl;
    reverse(ts.begin(), ts.end());
    vector<int> comp(n, -1);
    int c = 0;
    for (int v : ts) {
        //cout << v << endl;
        if (comp[v] == -1) {
            paint(v, rg, c++, comp, fix, mask);
        }
    }
    //cout << endl;
    map<int, int> t;
    c = 0;
    for (int &i : comp) {
        if (t.find(i) == t.end()) {
            t[i] = c++;
        }
        i = t[i];
    }

    /*for (auto i : comp) {
        cout << i << ' ';
    }
    cout << '\n';*/
    return comp;
}

int main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int n, m, subtask;
    cin >> n >> m >> subtask;
    vector<pair<int, int>> edges(m);
    for (auto &[v, u] : edges) {
        cin >> v >> u;
        v--;
        u--;
    }

    if (subtask <= 2) {
        vector<int> comp = get_comp(n, m, edges, (1 << m) - 1, 0);
        //cout << endl;
        int ans = 0, cnt = 0;
        for (int fix = 0; fix < (1 << m); ++fix) {
            int flex = 0;
            int k = 0;
            for (int i = 0; i < m; ++i) {
                flex |= (!((fix >> i) & 1) << i);
                k += !((fix >> i) & 1);
            }
            if (k < ans) {
                continue;
            }
            bool can = true;
            for (int mask = flex; mask > 0 && can; mask = flex & (mask - 1)) {
                //cout << fix << ' ' << mask << endl;
                can &= get_comp(n, m, edges, fix, mask) != comp;
            }
            if (can && ans < k) {
                ans = k;
                cnt = 0;
                /*cout << fix << '\n';
                for (int mask = flex; mask > 0; mask = flex & (mask - 1)) {
                    cout << mask << ' ';
                }
                cout << '\n';*/
            }
            cnt += (ans == k);
        }
        cout << ans << '\n' << cnt << '\n';
    }
    return 0;
}
