#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <set>
#include <map>

using namespace std;


vector<vector<int>> rgr;

vector<bool> used;
vector<int> top;

void dfs(int v, vector<vector<int>> &gr) {
    used[v] = true;
    for (auto u : gr[v]) {
        if (!used[u]) {
            dfs(u, gr);
        }
    }
    top.push_back(v);
}



void dfs2(int v, int col, vector<int> &cmp) {
    cmp[v] = col;
    for (auto u : rgr[v]) {
        if (cmp[u] == -1) {
            dfs2(u, col, cmp);
        }
    }
}

void f(vector<int> &cmp) {
    int it = 0;
    map<int, int> mp;
    for (int i = 0; i < cmp.size(); i++) {
        if (mp.find(cmp[i]) == mp.end()) {
            mp[cmp[i]] = it++;
        }
    }
    for (int i = 0; i < cmp.size(); i++) {
        cmp[i] = mp[cmp[i]];
    }
}

vector<int> css(vector<vector<int>> &gr, int n) {
    rgr.clear();
    rgr.resize(n);
    top.clear();
    for (int i = 0; i < n; i++) {
        for (auto j : gr[i]) {
            rgr[j].push_back(i);
        }
    }
    used.assign(n, false);
    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            dfs(i, gr);
        }
    }
    reverse(top.begin(), top.end());
    vector<int> cmp(n, -1);
    int col = 0;
    for (int i = 0; i < n; i++) {
        if (cmp[top[i]] == -1) {
            dfs2(top[i], col++, cmp);
        }
    }
    f(cmp);
    return cmp;
}

int main()
{
    int n, m, g;
    cin >> n >> m >> g;
    vector<vector<int>> gr;
    gr.resize(n);
    vector<pair<int, int>> edg;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        gr[a].push_back(b);
        edg.push_back({a, b});
    }
    vector<int> gd = css(gr, n);
    vector<int> bad;
    for (int mask = 0; mask < (1 << m) - 1; mask++) {
        vector<vector<int>> gr2(n);
        for (int i = 0; i < m; i++) {
            auto [a, b] = edg[i];
            if (mask & (1 << i)) {
                gr2[a].push_back(b);
            } else {
                gr2[b].push_back(a);
            }
        }
        vector<int> col = css(gr2, n);
        if (gd == col) {
            bad.push_back(mask);
        }
    }
    int ans = 0, kol = 1;
    for (int mask = 21; mask < (1 << m); mask++) {
        int cnt = 0;
        for (int i = 0; i < m; i++) {
            if (!(mask & (1 << i))) {
                cnt++;
            }
        }
        bool fl = true;
        for (auto mask2 : bad) {
            if ((mask2 & mask) == mask) {
                fl = false;
                break;
            }
        }
        if (fl) {
            if (cnt == ans) {
                kol++;
            }
            if (cnt > ans) {
                ans = cnt;
                kol = 1;
            }
        }
    }
    cout << ans << endl << kol << endl;

    return 0;
}