#include <bits/stdc++.h>

using namespace std;

const int N = 2000 +123;

using ll = long long;

mt19937_64 rng (time (0));
vector<vector<int>> comp1, comp2;
#define int long long
bool used[N];
int cnt_e, cnt_v, st, st2, ans, color[N], color2[N];
vector<int> tops;
vector<int> g[N], rg[N], ng[N], ngr[N];
vector<pair<int,int>> e;
void Dfs (int v) {
    used[v] = 1;
    cnt_v += 1;
    cnt_e += (int)g[v].size();
    for (auto to : g[v]) {
        if (!used[to]) Dfs (to);
    }
}
void dfs (int v) {
    used[v] = 1;
    for (auto to : g[v]) if (!used[to]) dfs (to);
    tops.push_back (v);
}
void build (int v) {
    comp1.back().push_back (v);
    color[v] = st;
    for (auto to : rg[v]) if (!color[to]) build (to);
}
void dfs2 (int v) {
    used[v] = 1;
    for (auto to : ng[v]) if (!used[to]) dfs2 (to);
    tops.push_back (v);
}
void build2 (int v) {
    comp2.back().push_back (v);
    color2[v] = st2;
    for (auto to : ngr[v]) if (!color2[to]) build2 (to);
}

void solve () {
    int n, m, group;
    cin >> n >> m >> group;
    for (int i = 1; i <= m; ++i) {
        int u, v; cin >> u >> v;
        g[u].push_back (v);
        rg[v].push_back (u);
        e.push_back ({u, v});
    }
    for (int i = 1; i <= n; ++i) if (!used[i]) dfs (i);
    reverse (begin (tops), end (tops));
    for (auto v : tops) {
        if (!color[v]) {
            comp1.push_back ({});
            st++;
            build (v);
            sort (begin (comp1.back()), end (comp1.back()));
        }
    }
    sort (begin (comp1), end (comp1));
    int mx = 0, cnt_mx =0;
    for (int m1 = 0; m1 < (1 << m); ++m1) {
        vector<pair<int,int>> e2;
        for (int i = 0; i < m; ++i) {
            if ((m1 >> i) & 1) {
                e2.push_back (e[i]);
            }
        }
        int cnt = 0;
        for (int m2 = 0; m2 < (1 << (int)e2.size()); ++m2) {
            for (int i = 1; i <= n; ++i) ng[i].clear(), ngr[i].clear();
            int cur = 0;
            for (int i = 0; i < m; ++i) {
                int u = e[i].first, v = e[i].second;
                if ((m1 >> i) & 1) {
                    if ((m2 >> cur) & 1) {
                        ng[u].push_back (v);
                        ngr[v].push_back(u);
                    } else {
                        swap (u, v);
                        ng[u].push_back (v);
                        ngr[v].push_back(u);
                    }
                    ++cur;
                } else {
                    ng[u].push_back (v);
                    ngr[v].push_back(u);
                }
            }

            fill (used + 1, used + 1 + n, 0);
            st2 = 0, tops.clear();
            fill (color2 + 1, color2 + 1 + n, 0);
            for (int i = 1; i <= n; ++i) if (!used[i]) dfs2 (i);
            reverse (begin (tops), end (tops));
            comp2.clear();
            for (auto v : tops) {
                if (!color2[v]) {
                    st2++;
                    comp2.push_back ({});
                    build2(v);
                    sort (begin (comp2.back()), end (comp2.back()));
                }
            }
            sort (begin (comp2), end (comp2));

            if (comp1 == comp2) cnt += 1;
            if (cnt > 1) break;
        }

        if (cnt == 1) {
            if (mx == (int)e2.size()) ++ cnt_mx;
            if (mx < (int)e2.size()) mx = e2.size(), cnt_mx = 1;
        }
    }
    cout << mx << '\n' << cnt_mx << '\n';
    return;
//    fill (used + 1, used + 1 + n, 0);
    for (int i = 1; i <= n; ++i) if (!used[i]) {
        cnt_v = cnt_e = 0;
        Dfs (i);
        ans += cnt_e - cnt_v + 1;
    }
    cout << ans << '\n' << "0\n";
}

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