//#define _GLIBCXX_DEBUG
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2")

#include<bits/stdc++.h>
//#include<ext/pb_ds/tree_policy.hpp>
//#include<ext/pb_ds/assoc_container.hpp>
using ll = long long;
#define int ll
using namespace std;
//using namespace __gnu_pbds;
//mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
//mt19937 mt(52);
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
int mod = 1000000007;
vector<set<int>> g; int n;
void ts(int u, vector<int> &used, vector<int> &ans){
    used[u] = 1;
    for(auto &v : g[u]) if(!used[v]) ts(v, used, ans);
    ans.push_back(u);
}
void dfs(int u, vector<int> &used, vector<vector<int>> &rg, int col){
    used[u] = col;
    for(auto &v : rg[u]) if(!used[v]) dfs(v, used, rg, col);
}
vector<int> color(){
    vector<int> used(n);
    vector<int> t;
    for(int i=0; i<n; ++i) if(!used[i]) ts(i, used, t);
    reverse(t.begin(), t.end());
    vector<vector<int>> rg(n);
    for(int u=0; u<n; ++u) for(auto &v : g[u]) rg[v].push_back(u);
    vector<int> ans(n); int col = 1;
    for(auto &u : t) if(!ans[u]){
        dfs(u, ans, rg ,col);
        ++col;
    }
    return ans;
}
bool check(vector<int> a, vector<int>b){
    vector<int> s(n+1);
    for(int i=0; i<n; ++i){
        s[a[i]] = b[i];
    }
    for(int i=0; i<n; ++i){
        if(s[a[i]] != b[i]) return 0;
    } 
    swap(a, b);
    s.clear();
    for(int i=0; i<n; ++i){
        s[a[i]] = b[i];
    }
    for(int i=0; i<n; ++i){
        if(s[a[i]] != b[i]) return 0;
    } 
    return 1;
}
void solve() {
    int m, _;
    cin >> n >>m >> _;
    g.resize(n);
    vector<pair<int, int>> vs;
    for(int i=0; i<m; ++i){
        int u, v;cin >> u >> v; --u; --v; g[u].insert(v);
        vs.emplace_back(u, v);
    }
    auto e = color();
    int ans = 0, k = 1;
    for(int mask = (1<<m)-1; mask > 0; --mask){
        vector<int> cur; int cmask = mask;
        for(int i=0; i<m; ++i) {
            if(cmask &1) cur.push_back(i);
            cmask = cmask >> 1;
        }
        if(cur.size() < ans) continue;
        bool fl = 1;
        for(int nmask = 1; nmask < (1<<cur.size()); ++nmask){
            cmask = nmask;
            for(int i=0; i<cur.size(); ++i){
                if(cmask&1){
                    g[vs[cur[i]].first].erase(vs[cur[i]].second);
                    g[vs[cur[i]].second].insert(vs[cur[i]].first);
                }
                cmask = cmask >> 1;
            }
            cmask = nmask;
            if(check(e, color())) fl = 0;
            for(int i=0; i<cur.size(); ++i){
                if(cmask&1){
                    g[vs[cur[i]].second].erase(vs[cur[i]].first);
                    g[vs[cur[i]].first].insert(vs[cur[i]].second);
                }
                cmask = cmask >> 1;
            }
            if(!fl) break;
        }
        if(fl){
            if(cur.size() > ans){
                ans = cur.size(); k = 1;
            } else ++k;
        }
    }
    cout << ans << '\n' << k;
}


signed main(){
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    bool cfmode = !(42);
    if(cfmode){
        int t;
        cin >> t;
        while(t--){
            solve();
            cout << '\n';
        }
    } else solve();
}