#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int N = 20;
vector<int> g[N], rg[N];
array<bool, N> used;
array<int, N> col, mcol;
vector<int> ord;
void dfs1(int v){
    used[v] = 1;
    for(auto to : rg[v]){
        if(used[to]) continue;
        dfs1(to);
    }
    ord.push_back(v);
}
int C;
void dfs2(int v){
    col[v] = C;
    for(auto to : g[v]){
        if(!col[to]){
            dfs2(to);
        }
    }
}
vector<int> do_comps(vector<pair<int, int>> edg, int n){
    ord.clear();
    for(int i = 0; i < n; i++){
        g[i].clear();
        rg[i].clear();
        used[i] = 0;
        col[i] = 0;
    }
    C = 1;
    for(auto [a, b] : edg){
        g[a].emplace_back(b);
        rg[b].emplace_back(a);
    }
    for(int i = 0; i < n; i++){
        if(!used[i])
            dfs1(i);
    }
    std::reverse(ord.begin(), ord.end());
    for(auto v : ord){
        if(!col[v]) {
            dfs2(v);
            C++;
        }
    }

    for(int i = n-1; i > -1; i--){
        mcol[col[i]] = i;
    }
    vector<int> ans(n);
    for(int i = 0; i < n; i++){
        ans[i] = mcol[col[i]];
    }
    return ans;
}
array<bool, (1<<20)> arr;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, G;
    cin >> n >> m >> G;
    vector<pair<int, int>> edg;
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        a--; b--;
        edg.emplace_back(a, b);
    }
    vector<int> orig = do_comps(edg, n);
    for(int i = 0; i < (1<<m); i++){
        vector<pair<int, int>> nedg = edg;
        for(int j = 0; j < m; j++){
            if((i>>j)&1)
                swap(nedg[j].first, nedg[j].second);
        }
        vector<int> t = do_comps(nedg, n);
        arr[i] = (t == orig);
    }
    pair<int, int> ans = {0, 0};
    for(int i = 0; i < (1<<m); i++){
        int sz = __popcount(i);
        if(sz < ans.first) continue;
        bool flag = true;
        for(int j = i; j > 0; j =(j-1)&i){
            if(arr[j]){
                flag = false;
                break;
            }
        }
        if(flag){
            if(ans.first < sz){
                ans = {sz, 1};
            }else
                ans.second++;
        }
    }
    cout << ans.first << '\n' << ans.second;
}
/*
 оставим только те где правилььное разбииение на компоненты
переберем маску-удаляемые ребра x = 0101001
не должно быть масок y таких что x&y > 0 && !x&y>0
 */