#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx")

using namespace std;
//#define int long long
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
int inf = 1e9;
int mod = 1e9+7;
int n, m;
vector<vector<int>> g;
vector<vector<int>> cp;
vector<pair<int, int>> e;

void dfs(int v, vector<int> &used, vector<int> &res){
    used[v] = 1;
    res.push_back(v);
    for(int i = 0; i < n; ++i){
        if(g[v][i]){
            if(!used[i]){
                dfs(i, used, res);
            }
        }
    }
}

vector<int> can(int v){
    vector<int> res;
    vector<int> used(n);
    dfs(v, used, res);
    return res;
}

vector<vector<int>> bcp(vector<vector<int>> &g){
    vector<vector<int>> h(n, vector<int> (n));
    for(int i = 0; i < n; ++i){
        vector<int> cn = can(i);
        for(auto x : cn){
            h[i][x] = 1;
        }
    }
    vector<int> used(n);
    vector<vector<int>> ans;
    for(int i=0 ; i < n; ++i){
        if(!used[i]){
            ans.push_back({});
            for(int j =0 ; j < n; ++j){
                if(!used[j]){
                    if(h[i][j] && h[j][i]){
                        ans.back().push_back(j);
                        used[j] = 1;
                    }
                }
            }
            sort(all(ans.back()));
        }
    }
    return ans;
}
bool check(vector<int> &c){
    for(int i = 0; i < m; ++i){
        if(c[i]){
            g[e[i].first][e[i].second] = 0;
        }
    }
    bool ans =0 ;
    if(bcp(g) == cp){
        ans = 1;
    }
    for(int i = 0; i < m; ++i){
        if(c[i]){
            g[e[i].first][e[i].second] = 1;
        }
    }
    return ans;
}

void solve() {
    cin >> n >> m;
    int gr;
    cin >> gr;
    g.assign(n, vector<int> (n));
    for(int i= 0; i < m; ++i){
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        g[u][v] = 1;
        e.push_back({u, v});
    }
    cp = bcp(g);
//    for(auto x : cp){
//        for(auto y : x){
//            cout << y << " ";
//        }
//        cout << endl;
//    }
    int l = 0, r = m+1, mid;
    vector<int> what(m+1);
    while(r > l+1){
        mid = (l+r)/2;
        int cnt =0 ;
        vector<int> c;
        for(int i = 0; i < m-mid; ++i){
            c.push_back(0);
        }
        for(int i = 0; i < mid; ++i){
            c.push_back(1);
        }
        if(check(c)){
            cnt++;
        }
        while(next_permutation(all(c))){
            if(check(c)){
                cnt++;
            }
        }
        what[mid] =  cnt;
        if(cnt){
            l = mid;
        }else{
            r = mid;
        }
    }
    cout << l << " " << what[l];
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt = 1;
    //cin >> tt;
    while(tt--) {
        solve();
        //cout << '\n';
    }
    return 0;
}
