#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(time(0));
constexpr int MAXN = 2005;
vector <int> g[MAXN];
vector <int> g2[MAXN];
vector <pair <int, int>> sp;
vector <int> top;
bool used[MAXN];
void dfs1(int v){
    used[v] = true;
    for (auto to: g[v]){
        if (!used[to])
            dfs1(to);
    }
    top.push_back(v);
}
int c[MAXN];
int color = 0;
void dfs2(int v){
    used[v] = true;
    c[v] = color;
    for (auto to: g2[v]){
        if (!used[to]){
            dfs2(to);
        }
    }
}
int cnt(int a){
    int res = 0;
    while (a != 0){
        res += a % 2;
        a /= 2;
    }
    return res;
}
void solve(){
    int n, m, G;
    cin >> n >> m >> G;
    vector <bool> dp(1 << m, true);
    for (int i = 0; i < m; i++){
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        g[u].push_back(v);
        g2[v].push_back(u);
        sp.push_back({u, v});
    }
    for (int i = 0; i < n; i++){
        if (!used[i]){
            dfs1(i);
        }
    }
    fill(used, used + n, false);
    reverse(top.begin(), top.end());
    for (int i = 0; i < n; i++){
        if (!used[top[i]]){
            color++;
            dfs2(top[i]);
        }
    }
    map <int, int> dct;
    int nw = 0;
    vector <int> nc(n, 0);
    for (int i = 0; i < n; i++){
        if (dct.find(c[i]) == dct.end()){
            nw++;
            dct[c[i]] = nw;
            nc[i] = nw;
        }
        else{
            nc[i] = dct[c[i]];
        }
    }
    for (int mask = 1; mask < (1 << m); mask++){
        for (int i = 0; i < n; i++){
            g[i].clear();
            g2[i].clear();
        }
        for (int j = 0; j < m; j++){
            int u = sp[j].first;
            int v = sp[j].second;
            if ((mask >> j) & 1){
                g[v].push_back(u);
                g2[u].push_back(v);
            }
            else{
                g[u].push_back(v);
                g2[v].push_back(u);
            }
        }
        color = 0;
        fill(used, used + n, false);
        top.clear();
        for (int i = 0; i < n; i++){
            if (!used[i]){
                dfs1(i);
            }
        }
        //cout << "AAA " << g2[1][0] << endl;
        reverse(top.begin(), top.end());
        fill(used, used + n, false);
        for (int i = 0; i < n; i++){
            //cout << top[i] << " ";
            if (!used[top[i]]){
                color++;
                dfs2(top[i]);
            }
        }
        //cout << '\n';
        map <int, int> dct;
        int nw = 0;
        vector <int> nwc(n, 0);
        for (int i = 0; i < n; i++){
            if (dct.find(c[i]) == dct.end()){
                nw++;
                dct[c[i]] = nw;
                nwc[i] = nw;
            }
            else{
                nwc[i] = dct[c[i]];
            }
        }
        /*for (auto v: nwc){
            cout << v << " ";
        }
        cout << '\n';*/
        if (nwc == nc){
            dp[mask] = false;
        }
    }
    int res = 0;
    int cntres = 0;
    vector <bool> ans(1 << m, true);
    for (int mask = 0; mask < (1 << m); mask++){
        ans[mask] = dp[mask];
        for (int i = 0; i < m; i++){
            if ((mask >> i) & 1){
                if (!ans[mask ^ (1 << i)]){
                    ans[mask] = false;
                }
            }
        }
        if (ans[mask]){
            if (cnt(mask) > res){
                res = cnt(mask);
                cntres = 0;
            }
            if (cnt(mask) == res){
                cntres++;
            }
        }
    }
    cout << res << '\n' << cntres << '\n';
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    while (t--){
        solve();
    }
}



