#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
mt19937 rnd(time(NULL));
vector<vector<int>>graph;
vector<vector<int>>rev;
vector<bool>used;
vector<int>top;
void dfs(int start){
    used[start] = true;
    for(auto val: graph[start]){
        if(!used[val]) dfs(val);
    }
    top.push_back(start);
}
vector<int>comp; int c = 0;
void rev_dfs(int start){
    comp[start] = c;
    for(auto val: rev[start]){
        if(comp[val] == -1) rev_dfs(val);
    }
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m, g; cin >> n >> m >> g; graph.resize(n);
    vector<pair<int, int>>edge; graph.assign(n, vector<int>()); rev.assign(n, vector<int>());
    for(int i = 0; i < m; i++){
        int u, v; cin >> u >> v; u--; v--; edge.push_back({u, v});
        graph[u].push_back(v); rev[v].push_back(u);
    }
    comp.assign(n, -1); c = 0; used.assign(n, false);
    for(int i = 0; i < n; i++){
        if(!used[i]) dfs(i);
    }
    used.assign(n, false);
    for(int i = 0; i < n; i++){
        int u = top[n - i - 1];
        if(comp[u] == -1){
            rev_dfs(u); c++;
        }
    }
    vector<int>cmp(n); vector<int>mn(c, 1e9);
    for(int i = 0; i < n; i++){
        mn[comp[i]] = min(mn[comp[i]], i);
    }
    for(int i = 0; i < n; i++){
        comp[i] = mn[comp[i]];
    }
    for(int i = 0; i < n; i++) cmp[i] = comp[i];
    vector<bool>good(1 << m, true);
    int mx = 0; int num = 0;
    for(int i = 0; i < (1 << m); i++){
        graph.assign(n, vector<int>()); rev.assign(n, vector<int>());
        comp.assign(n, -1); c = 0; top.clear(); used.assign(n, false);
        for(int j = 0; j < m; j++) {
            if (i & (1 << j)) {
                graph[edge[j].second].push_back(edge[j].first);
                rev[edge[j].first].push_back(edge[j].second);
            } else {
                graph[edge[j].first].push_back(edge[j].second);
                rev[edge[j].second].push_back(edge[j].first);
            }
        }
        for(int j = 0; j < n; j++){
            if(!used[j]) dfs(j);
        }
        used.assign(n, false);
        for(int j = 0; j < n; j++){
            int u = top[n - 1 - j];
            if(comp[u] == -1){
                rev_dfs(u); c++;
            }
        }
        mn.assign(c, 1e9);
        for(int j = 0; j < n; j++){
            mn[comp[j]] = min(mn[comp[j]], j);
        }
        for(int j = 0; j < n; j++){
            comp[j] = mn[comp[j]];
        }
        for(int j = 0; j < n; j++){
            if(comp[j] != cmp[j]){
                good[i] = false;
            }
        }
        int sz = 0;
        for(int j = 0; j < m; j++){
            if(i & (1 << j)) sz++;
        }
    }
    for(int i = 1; i < (1 << m); i++){
        bool nice = true;
        for(int add = i; add > 0; add = (add - 1) & i){
            if(!good[add]) nice = false;
        }
        int sz = 0;
        for(int j = 0; j < m; j++){
            if(i & (1 << j)) sz++;
        }
        if(nice){
            if(mx == sz) num++;
            else if(sz > mx){
                mx = sz; num = 1;
            }
        }
    }
    cout << mx << "\n" << num;
}