#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#define int long long

const int MAX = 2e3 + 7;
const int mod = 1e5 + 7;

mt19937_64 rng(time(0));

template <typename T>
bool umx(T& a, T b) {
    return (a < b ? a = b, 1 : 0);
}

int n, m, gr;
vector<int> g[MAX];
vector<int> rg[MAX];

bool was[MAX];
vector<int> tps;
int clr[MAX];
int sz[MAX];

void dfs1(int v) {
    if (was[v]) return;
    was[v] = true;
    for (auto to : g[v]) {
        dfs1(to);
    }
    tps.push_back(v);
}

void dfs2(int v, int cnt) {
    if (clr[v]) return;
    clr[v] = cnt;
    sz[cnt]++;
    for (auto to : rg[v]) {
        dfs2(to, cnt);
    }
}

int v[MAX], u[MAX];
bool flag[MAX];

void build() {
    for (int i = 1; i <= n; i++) {
        clr[i] = 0;
        was[i] = 0;
        g[i].clear();
        rg[i].clear();
    }
    tps.clear();
    for (int i = 1; i <= m; i++) {
        g[v[i]].push_back(u[i]);
        rg[u[i]].push_back(v[i]);
    }
    int res = 0;
    for (int i = 1; i <= n; i++) {
        dfs1(i);
    }
    int cnt = 0;
    reverse(tps.begin(), tps.end());
    for (auto i : tps) {
        if (clr[i] == 0) {
            dfs2(i, ++cnt);
        }
    }
}

void solve() {
    cin >> n >> m >> gr;
    for (int i = 1; i <= m; i++) {
        cin >> v[i] >> u[i];
        g[v[i]].push_back(u[i]);
        rg[u[i]].push_back(v[i]);
    }
    int res = 0;
    for (int i = 1; i <= n; i++) {
        dfs1(i);
    }
    int cnt = 0;
    reverse(tps.begin(), tps.end());
    for (auto i : tps) {
        if (clr[i] == 0) {
            dfs2(i, ++cnt);
        }
    }
    for (int i = 1; i <= m; i++) {
        flag[i] = clr[v[i]] == clr[u[i]];
    }
    int cnts = 0;
    for (int mask = 0; mask < (1 << m); mask++) {
        cnt = 0;
        vector<int> st;
        for (int i = 0; i < m; i++) {
            if ((mask >> i & 1)) {
                st.push_back(i + 1);
            }
        }
        for (int nmask = 0; nmask < (1 << (int)(st.size())); nmask++) {
            for (int i = 0; i < (int)(st.size()); i++) {
                if ((nmask >> i & 1)) {
                    swap(v[st[i]], u[st[i]]);
                }
            }
            build();
            bool good = true;
            for (int i = 1; i <= m; i++) {
                good &= flag[i] == (clr[v[i]] == clr[u[i]]);
            }
            cnt += good;
            for (int i = 0; i < (int)(st.size()); i++) {
                if ((nmask >> i & 1)) {
                    swap(v[st[i]], u[st[i]]);
                }
            }
            if (cnt > 1) break;
        }
        int bpp = __builtin_popcount(mask);
        if (cnt == 1) {
            if (res < bpp) {
                res = bpp;
                cnts = 1;
            } else {
                if (res == bpp) {
                    cnts++;
                }
            }
        }
    }
    cout << res << '\n';
    cout << cnts << '\n';
}

int32_t main() {
#ifdef __APPLE__
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(0); cin.tie(0);
    int tt = 1;
    // cin >> tt;
    while (tt--) {
        solve();
    }
}