#include <bits/stdc++.h>

using namespace std;

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

mt19937 rnd(1485);

vector<vector<int>> gr;
vector<vector<int>> g;
vector<bool> fl;
vector<int> eu;
vector<vector<int>> cnt;
vector<int> cv;
int col = 0;

void dfs(int v){
    eu.pb(v);
    fl[v] = true;
    for (auto u:gr[v]){
        if (!fl[u]){
            dfs(u);
        }
    }
}

void dfs2(int v, bool fl2){
    cv[v] = col;
    fl[v] = true;
    if (fl2){
        cnt[col].pb(v);
    }
    for (auto u:g[v]){
        if (!fl[u]){
            dfs2(u, fl2);
        }
    }
}

void solve(){
    int n, m, g2;
    cin >> n >> m >> g2;
    vector<pii> r(m);
    gr.assign(n, {});
    g.assign(n, {});
    for (int i = 0; i < m; i++){
        cin >> r[i].ff >> r[i].ss;
        --r[i].ff;
        --r[i].ss;
        gr[r[i].ff].pb(r[i].ss);
        g[r[i].ss].pb(r[i].ff);
    }
    fl.resize(n);
    for (int i = 0; i < n; i++){
        if (!fl[i]){
            dfs(i);
        }
    }
    fl.assign(n, false);
    cnt.resize(n);
    cv.resize(n);
    for (auto u:eu){
        if (!fl[u]){
            dfs2(u, true);
            col++;
        }
    }
    int mx = 0;
    int ans = 0;
    for (int mask = 0; mask < (1 << m); mask++){
        cout << mask << endl;
        int cnt2 = 0;
        gr.assign(n, {});
        g.assign(n, {});
        for (int i = 0; i < m; i++){
            if (mask >> i & 1){
                cnt2++;
                gr[r[i].ss].pb(r[i].ff);
                g[r[i].ff].pb(r[i].ss);
            }
            else{
                g[r[i].ss].pb(r[i].ff);
                gr[r[i].ff].pb(r[i].ss);
            }
        }
        eu.clear();
        fl.assign(n, false);
        for (int i = 0; i < n; i++){
            if (!fl[i]){
                dfs(0);
            }
        }
        fl.assign(n, false);
        cv.resize(n);
        col = 0;
        for (auto u:eu){
            if (!fl[u]){
                dfs2(u, false);
                col++;
            }
        }
        bool fl2 = true;
        for (auto i:cnt){
            int d = cv[i[0]];
            for (auto j:i){
                if (d != cv[j]){
                    fl2 = false;
                    break;
                }
            }
        }
        if (fl2){
            if (mx < cnt2){
                mx = cnt2;
                ans = 1;
            }
            else if (mx == cnt2){
                ans++;
            }
        }
    }
    cout << mx << "\n" << ans;
}

int32_t main(){
    cin.tie(0)->ios_base::sync_with_stdio(0);
#ifdef LOCAL
    freopen("inp.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCAL
    int _ = 1;
    //cin >> _;
    while (_--){
        solve();
    }
}
