//#pragma GCC optimize("O3, Ofast, unroll-loops, inline, no-stack-protector")
#include <bits/stdc++.h>
//#pragma GCC target("avx2")

using namespace std;

using ll = long long;
using pii = pair<int, int>;

vector<vector<pii>> g;
vector<vector<int>> g2, original;
int ans = 0, res = 0;
vector<int> used;
vector<pii> edges;
int n, m;


void dfs_ts(int v, vector<int> &used, vector<vector<int>> &g, vector<int> &ts) {
    used[v] = 1;
    for (auto u : g[v]) {
        if (used[u]) continue;
        dfs_ts(u, used, g, ts);
    }
    used[v] = 2;
    ts.push_back(v);
}

int total = 0;

vector<vector<int>> KSS(vector<vector<int>> &g) {
    total += n;
    vector<int> ts;
    vector<int> used(n);
    for (int i = 0; i < n; ++i) {
        if (!used[i]) {
            dfs_ts(i, used, g, ts);
        }
    }
    std::reverse(ts.begin(), ts.end());
    vector<vector<int>> gr(n);
    for (int i = 0; i < n; ++i) {
        for (auto u : g[i]) gr[u].push_back(i);
    }
    vector<vector<int>> comps;
    used.assign(n, 0);
    for (int i = 0; i < n; ++i) {
        if (!used[ts[i]]) {
            comps.emplace_back();
            dfs_ts(ts[i], used, gr, comps.back());
            std::sort(comps.back().begin(), comps.back().end());
        }
    }
    std::sort(comps.begin(), comps.end());
    return comps;
}

int cnt2 = 0;



void gen2(int i) {
    if (total >= 2e7) {
        cout << ans << "\n";
        cout << 1;
        exit(0);
    }
    ++total;
    if (cnt2 >= 2) return;
    if (i == m) {
        auto now = KSS(g2);
        if (now == original) {
            ++cnt2;
        }
        return;
    }
    if (!used[i]) {
        g2[edges[i].first].push_back(edges[i].second);
        gen2(i + 1);
        g2[edges[i].first].pop_back();
        return;
    }
    g2[edges[i].first].push_back(edges[i].second);
    gen2(i + 1);
    g2[edges[i].first].pop_back();
    g2[edges[i].second].push_back(edges[i].first);
    gen2(i + 1);
    g2[edges[i].second].pop_back();
}

void gen(int v, int cnt) {
    if (total >= 2e7) {
        cout << ans << "\n";
        cout << cnt;
        exit(0);
    }
    ++total;
    if (v == n) {
        cnt2 = 0;
        gen2(0);
        if (cnt2 == 1) {
            if (cnt > ans) {
                ans = cnt;
                res = 1;
            } else if (cnt == ans) {
                ++res;
            }
        }
        return;
    }
    int k = g[v].size();
    for (int mask = (1 << k) - 1; mask >= 0; --mask) {
        int add = 0;
        for (int i = 0; i < k; ++i) {

            if ((1 << i) & mask) {
                used[g[v][i].second] = 1;
                ++add;
            }

        }
        gen(v + 1, cnt + add);
        for (int i = 0; i < k; ++i) {
            if ((1 << i) & mask) {
                used[g[v][i].second] = 0;
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int group;
    cin >> n >> m >> group;
    g2.resize(n);
    g.resize(n);
    vector<vector<int>> g2(n);
    edges.resize(m);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        edges[i] = {u, v};
        g[u].emplace_back(v, i);
        g2[u].push_back(v);
    }
    original = KSS(g2);
    used.resize(m);
//    used = {1, 1, 0, 1, 1, 1};
    gen(0, 0);
//    gen2(0);
    cout << ans << "\n" << res << "\n";
}
