#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")

#include <bits/stdc++.h>

#pragma GCC target("avx,avx2,bmi,bmi2,sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,abm,mmx,tune=native")

using namespace std;

int n, m, grr;
vector<pair<int, int>> ed;

vector<vector<int>> g, grev;
vector<int> topsort;
vector<unsigned long long> hhel;
vector<unsigned long long> grps;
unsigned long long chash = 0;
vector<bool> used;

void dfs1(int v) {
    used[v] = true;
    for(auto t : g[v]) {
        if(used[t]) continue;
        dfs1(t);
    }
    topsort.push_back(v);
}

void dfs2(int v, int col) {
    used[v] = true;
    grps[col] ^= hhel[v];
    // cout << v + 1 << ' ' << col + 1 << '\n';
    for(auto t : grev[v]) {
        if(used[t]) continue;
        dfs2(t, col);
    }
}

int main() {
    cin >> n >> m >> grr;
    ed.resize(m);
    for(int i = 0; i < m; i++) {
        cin >> ed[i].first >> ed[i].second;
        ed[i].first--;
        ed[i].second--;
    }
    mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
    hhel.resize(n);
    for(int i = 0; i < n; i++) hhel[i] = rng();

    unsigned long long thash = 0;

    {
        g.clear();
        grev.clear();
        topsort.clear();
        used.clear();
        grps.clear();

        g.resize(n);
        grev.resize(n);
        topsort.resize(n);
        used.resize(n);
        grps.resize(n);

        for(int i = 0; i < m; i++) {
            auto [a, b] = ed[i];
            g[a].push_back(b);
            grev[b].push_back(a);
        }

        for(int i = 0; i < n; i++) {
            if(!used[i]) dfs1(i);
        }
        used.assign(n, false);
        int cc = 0;
        chash = 1;
        reverse(topsort.begin(), topsort.end());
        // cout << ">> " << bitset<6>(m2) << ":\n";
        for(auto i : topsort) {
            if(!used[i]) dfs2(i, cc++);
        }
        sort(grps.begin(), grps.end());
        for(auto i : grps) {
            chash = chash * 7398471209ull + i;
        }
        thash = chash;
    }

    vector<int> dp(1 << m, -1);
    for(int m2 = 0; m2 < (1 << m); m2++) {
        g.clear();
        grev.clear();
        topsort.clear();
        used.clear();
        grps.clear();

        g.resize(n);
        grev.resize(n);
        topsort.resize(n);
        used.resize(n);
        grps.resize(n);

        for(int i = 0; i < m; i++) {
            auto [a, b] = ed[i];
            if((m2 >> i) & 1) swap(a, b);
            g[a].push_back(b);
            grev[b].push_back(a);
        }

        for(int i = 0; i < n; i++) {
            if(!used[i]) dfs1(i);
        }
        used.assign(n, false);
        int cc = 0;
        chash = 1;
        reverse(topsort.begin(), topsort.end());
        // cout << ">> " << bitset<6>(m2) << ":\n";
        for(auto i : topsort) {
            if(!used[i]) dfs2(i, cc++);
        }
        sort(grps.begin(), grps.end());
        for(auto i : grps) {
            chash = chash * 7398471209ull + i;
        }
        if(chash == thash) dp[m2] = m2;
    }

    int mxAns = -1, cntAns = 0;
    for(int mask = 0; mask < (1 << m); mask++) {
        for(int i = 0; i < m; i++) {
            if((mask >> i) & 1) continue;
            int tm = mask | (1 << i);
            if(dp[tm] == -2) continue;
            if(dp[tm] >= 0 && dp[tm] != dp[mask]) dp[tm] = -2;
            else dp[tm] = dp[mask];
        }
        if(dp[mask] >= 0) {
            if(__popcount(mask) > mxAns) {
                mxAns = __popcount(mask);
                cntAns = 0;
            }
            if(__popcount(mask) == mxAns) {
                cntAns++;
            }
        }
    }
    // for(int mask = 0; mask < (1 << m); mask++) {
    //     cout << bitset<6>(mask) << ' ' << dp[mask] << '\n';
    // }
    cout << mxAns << '\n' << cntAns << '\n';
}
