#include <bits/stdc++.h>
using namespace std;
//#define int long long
const int INF = 1e9 + 7;
const int N = 2010;
vector <int> g[N], gr[N];
vector <int> tps;
int used[N], col[N];
int cur = 0;
vector <int> rn;
mt19937 rnd(time(0));
void tops(int v){
    used[v] = 1;
    for (auto to: g[v]){
        if (!used[to]){
            tops(to);
        }
    }
    tps.push_back(v);
}
void dfs(int v, int c){
    col[v] = c;
    cur |= rn[v];
    for (auto to: gr[v]){
        if (!col[to]){
            dfs(to, c);
        }
    }
}
void tops1(int v, vector <vector <int>> &gg){
    used[v] = 1;
    for (auto to: gg[v]){
        if (!used[to]){
            tops1(to, gg);
        }
    }
    tps.push_back(v);
}
void dfs1(int v, vector <vector <int>> &gg){
    cur |= rn[v];
    used[v] = 1;
    for (auto to: gg[v]){
        if (!used[to]){
            dfs1(to, gg);
        }
    }
}
void solve(){
    int n, m, groop;
    cin >> n >> m >> groop;
    rn.resize(n);
    for (int i = 0; i < n; ++i){
        rn[i] = rnd();
    }
    vector <pair <int, int>> rb(m);
    for (int i = 0; i < m; ++i){
        int v, u;
        cin >> v >> u;
        --v;
        --u;
        rb[i] = {v, u};
        g[v].push_back(u);
        gr[u].push_back(v);
    }
    tps.clear();
    for (int i = 0; i < n; ++i){
        if (!used[i]){
            tops(i);
        }
    }
    reverse(tps.begin(), tps.end());
    int c = 1;
    set<int> st;
    for (auto x: tps){
        if (!col[x]){
            cur = 0;
            dfs(x, c);
            st.insert(cur);
            c++;
        }
    }
    vector <int> dp(1 << m);
    for (int msk = 0; msk < (1 << m); ++msk){
        if (msk == 0){
            continue;
        }
        vector <vector <int>> g1(n), gr1(n);
        tps.clear();
        for (int i = 0;  i < n; ++i){
            used[i] = 0;
        }
        for (int j = 0; j < m; ++j){
            if ((msk >> j) & 1){
                g1[rb[j].second].push_back(rb[j].first);
                gr1[rb[j].first].push_back(rb[j].second);
            }
            else{
                gr1[rb[j].second].push_back(rb[j].first);
                g1[rb[j].first].push_back(rb[j].second);
            }
        }
        for (int i = 0; i < n; ++i){
            if (!used[i]){
                tops1(i, g1);
            }
        }

        for (int i = 0;  i < n; ++i){
            used[i] = 0;
        }
        reverse(tps.begin(), tps.end());
        set <int> st2;
        for (auto x: tps){
            if (!used[x]){
                cur = 0;
                dfs1(x, gr1);
                st2.insert(cur);
            }
        }
        for (int i = 0; i < m; ++i){
            if ((msk >> i) & 1){
                dp[msk] += dp[msk - (1 << i)];
            }
        }
        /*if (msk == 18){
            for (int x = 0; x < n; ++x){
                cout << x + 1<< ": ";
                for (auto y: g1[x]){
                    cout << y + 1 << " ";
                }
                cout << endl;
            }
            for (auto x: st2){
                for (auto y: x){
                    cout << y + 1 << " ";
                }
                cout << endl;
            }
            for (auto x: tps){
                cout << x + 1 << " ";
            }
            cout << endl;
        }*/
        if (st == st2){
            //cout << msk << endl;
            dp[msk]++;
        }
        //cout << "OK" << endl;
    }
    //cout << dp[20] << endl;
    int ans1 = 0, ans2 = 0;
    for (int i = 0; i < (1 << m); ++i){
        if (dp[i] == 0){
            int cn = __builtin_popcount(i);
            //cout << cn << endl;
            if (cn == ans1){
                ans2++;
            }
            else if(cn > ans1){
                ans2 = 1;
                ans1 = cn;
            }
        }
    }
    cout << ans1 << "\n" << ans2;
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    //cin >> t;
    while (t--){
        solve();
    }
}


