#include <bits/extc++.h>

using namespace std;
using namespace __gnu_pbds;

#define itn int
#define int long long
#define all(a) begin(a), end(a)
#define rall(a) rbegin(a), rend(a)
#define pii pair<int, int>
#define ff first
#define ss second
#define sz(a) (int)(a).size()
#define ll long long
#define ld long double

mt19937 rnd(time(0));

const int N = 2000 + 10;

set <int> g[N];
set <int>  g1[N];

int c[N], mx = 1, used[N];
vector <int> tp;

void dfs(int v){
    used[v] = 1;

    for (auto x: g1[v]){
        if (!used[x]){
            dfs(x);
        }
    }
    tp.push_back(v);
}

void paint(int v, int col){
    used[v] = 1;
    c[v] = col;
    for (auto x: g[v]){
        if (used[x]) continue;
        paint(x, col);
    }
}

vector <int> col(int n){
    fill(all(used), 0);
    fill(all(c), 0);
    tp.clear();
    for (int i = 0; i < n; ++i){
        if (used[i]) continue;
        dfs(i);
    }

    fill(all(used), 0);
    reverse(all(tp));
    for (auto x: tp){
        if (!used[x])
            paint(x, mx++);
    }


    vector <itn> nw_c(n);
    int mn = 1;
    for (int i = 0; i < n; ++i){
        if (nw_c[i]) continue;
        for (int j = 0; j < n; ++j){
            if (c[j] == c[i]){
                nw_c[j] = mn;
            }
        }
        mn++;
    }
    return nw_c;
}


void solve(){
    int n, m, gr;
    cin >> n >> m >> gr;
//    cout << n  - 1 << ' ' << 0 << '\n';
    vector <pii> vsp;
    for (int i = 0; i < m; ++i){
        itn v, u;
        cin >> u >> v;
        u--, v--;
        vsp.push_back({u, v});
        g[u].insert(v);
        g1[v].insert(u);
    }

    vector <int> etalon = col(n);

    int mx_ans = 0, cnt_ans = 0;
    for (itn i = 0; i < (1ll << m); ++i){
        if (__builtin_popcount(i) < mx_ans || __builtin_popcount(i) > 5) continue;
        int cnt = 0;
        for (int j = i; j > 0; j = (j - 1) & i){
            for (int k = 0; k < m; ++k){
                if (j >> k & 1){
                    auto [u, v] = vsp[k];
                    g[u].erase(v);
                    g[v].insert(u);
                    g1[v].erase(u);
                    g1[u].insert(v);
                }
            }
            vector <int> cur = col(n);
            if (cur == etalon){
                cnt++;
            }
            for (int k = 0; k < m; ++k){
                if (j >> k & 1){
                    auto [u, v] = vsp[k];
                    g[v].erase(u);
                    g[u].insert(v);
                    g1[u].erase(v);
                    g1[v].insert(u);
                }
            }
            if (cnt != 0){
                break;
            }
        }
        if (cnt == 0){
            if (mx_ans < __builtin_popcount(i)){
                cnt_ans = 1;
                mx_ans = __builtin_popcount(i);
            }
            else if (mx_ans == __builtin_popcount(i)){
                cnt_ans++;
            }
        }
    }
    cout << mx_ans << ' ' << cnt_ans << '\n';
}

signed main(){
    cin.tie(nullptr) ->sync_with_stdio(false);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int t = 1;
//    cin >> t;
    while (t--){
        solve();
    }
}