#include <bits/stdc++.h>

using namespace std;

#define ll long long
//#define ld long double
//#define ull unsigned long long
//#define sll __int128
#define size(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
//#define int long long

mt19937 rnd(time(0));

ll INF = 1e18;
int mod = 1e9 + 7;

int kv(int x) {
    return ((ll)x * x) % mod;
}

int mult(int a, int b){
    return ((ll)a * b) % mod;
}

int fast_pow(int x, int a){
    if (a == 0) return 1;
    if (a == 1) return x;
    if (a & 1) return mult(x, fast_pow(x, a - 1));
    return kv(fast_pow(x, a / 2));
}



void gsrt(int v, vector<bool> &used, vector<vector<int>> &g, vector<int> &ord){
    used[v] = true;
    for (auto to : g[v]){
        if (used[to]) continue;
        gsrt(to, used, g, ord);
    }
    ord.push_back(v);
}

void recol(int v, vector<bool> &used, int &cl, vector<vector<int>> &g){
    cl ^= (1 << v);
    used[v] = true;
    for (auto to : g[v]){
        if (used[to]) continue;
        recol(to, used, cl, g);
    }
}

void solve(){
    int n, m, G;
    cin >> n >> m >> G;
    vector<pair<int, int>> edges(m);
    for (int i = 0; i < m; i++){
        int v, u;
        cin >> v >> u;
        v--; u--;
        edges[i] = {v, u};
    }
    int all = (1 << m);
    int mx = 0, cnt = 1;
    ll nw = 0;
    vector<ll> f(all);
    for (int i = 0; i < all; i++){
        f[i] = (ll)rnd() * rnd();
    }
    vector<bool> dp(all, 1);
    vector<vector<int>> g(n), gr(n);
    for (int mask = 0; mask < all; mask++){
        for (int i = 0; i < m; i++){
            auto [v, u] = edges[i];
            if ((mask >> i) & 1) swap(v, u);
            g[v].push_back(u);
            gr[u].push_back(v);
        }
        vector<bool> used(n);
        ll cl = 0;
        vector<int> ord;
        for (int i = 0; i < n; i++){
            if (!used[i]){
                gsrt(i, used, g, ord);
            }
            
        }
        reverse(ord.begin(), ord.end());
        used = vector<bool>(n, false);
        for (auto v : ord){
            if (!used[v]){
                int nn = 0;
                recol(v, used, nn, gr);
                cl ^= f[nn];
            }
            g[i].clear();
            gr[i].clear();
        }
        //cerr << mask << endl;
        if (mask == 0){
            nw = cl;
            continue;
        }
        dp[mask] = (cl != nw);
    }
    for (int mask = 0; mask < all; mask++){
        for (int j = 0; j < m; j++){
            if (mask >> j & 1) {
                dp[mask] = min(dp[mask], dp[mask ^ (1 << j)]);
            }
        }
        int c = __builtin_popcount(mask);
        if (dp[mask]){
            //cout << c << " " << mask << endl;
            if (mx < c){
                mx = c;
                cnt = 0;
            }
            if (mx == c){
                cnt++;
            }
        }
    }
    cout << mx << "\n" << cnt;
}

signed main(){
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    int ttt = 1;
    //cin >> ttt;
    while (ttt--){
        solve();
    }
}
