#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);
    }
}

bool flag[MAX];
int _v, _u;

void dfs4(int v) {
    if (was[v]) return;
    was[v] = true;
    for (auto to : g[v]) {
        if (v == _v && to == _u) continue;
        dfs4(to);
    }
}

bool pth(int v, int u) {
    _v = v;
    _u = u;
    for (int i = 1; i <= n; i++) was[i] = false;
    dfs4(v);
    return was[u];
}

bool bad[MAX];


int v[MAX], u[MAX];
int clri[MAX][MAX];
int id = 0;
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++) {
        if (i == id) continue;
        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) {
            sz[cnt + 1] = 0;
            dfs2(i, ++cnt);
        }
    }
    if (id) {
        for (int i = 1; i <= n; i++) {
            clri[id][i] = clr[i];
        }
    }
}
int nclr[MAX];
int nsz[MAX];

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]);
    }
    for (int i = 1; i <= m; i++) {
        id = i;
        build();
    }
    id = 0;
    build();
    int res = 0;
    for (int i = 1; i <= m; i++) {
        flag[i] = clr[v[i]] == clr[u[i]];
    }
    for (int i = 1; i <= n; i++) {
        nsz[clr[i]]++;
    }
    for (int i = 1; i <= m; i++) {
        if (clr[v[i]] == clr[u[i]]) {
            bad[i] = true;
            for (int j = 1; j <= m; j++) {
                if (flag[j] != (clri[i][v[j]] == clri[i][v[i]])) {
                    bad[i] = false;
                }
            }
            nclr[i] = clr[v[i]];
        } else {
            if (!pth(v[i], u[i])) {
                bad[i] = true;
                continue;
            }
//            res++;
            nclr[i] = -1;
        }
    }
    int cnts = 0;
    for (int mask = 0; mask < (1 << m); mask++) {
        int cnt = 0;
        vector<int> st;
        bool ret = false;
        map<int, int> mp;
        for (int i = 0; i < m; i++) {
            if ((mask >> i & 1)) {
                if (bad[i + 1]) ret = true;
                if (nclr[i + 1] != -1) {
                    mp[nclr[i + 1]]++;
                    if (mp[nclr[i + 1]] >= nsz[nclr[i + 1]]) {
                        ret = true;
                    }
                    st.push_back(i + 1);
                }
            }
        }
        if (ret) continue;
        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();
    }
}