#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void solve();

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll q = 1;
    while (q--) {
        solve();
    }
}

const ll INF = 1e18;

vector<ll> top_sort;

void dfs(ll v, vector<ll>& used, vector<vector<ll>>& g) {
    used[v] = 1;
    for (auto u : g[v]) {
        if (!used[u]) {
            dfs(u, used, g);
        }
    }
    top_sort.push_back(v);
}

void paint(ll v, vector<ll>& used, vector<vector<ll>>& g, vector<vector<ll>>& ans) {
    used[v] = 1;
    ans.back().push_back(v);
    for (auto u : g[v]) {
        if (!used[u]) {
            paint(u, used, g, ans);
        }
    }
}

vector<vector<ll>> css(vector<vector<ll>>& g) {
    ll n = (int)g.size();
    vector<vector<ll>> gr(n);
    for (int i = 0; i < n; i++) {
        for (auto u : g[i]) {
            gr[u].push_back(i);
        }
    }

    top_sort.clear();
    vector<ll> used(n);
    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            dfs(i, used, g);
        }
    }
    reverse(top_sort.begin(), top_sort.end());


    used.assign(n, 0);
    vector<vector<ll>> ans;
    for (auto i : top_sort) {
        if (!used[i]) {
            ans.emplace_back();
            paint(i, used, gr, ans);
        }
    }
    for (auto &i : ans) {
        sort(i.begin(), i.end());
    }
    sort(ans.begin(), ans.end());
    return ans;
}

void solve() {
    ll n, m, gr;
    cin >> n >> m >> gr;
    vector<pair<ll, ll>> ed;
    vector<vector<ll>> gra(n);
    for (int i = 0; i < m; i++) {
        ll a, b;
        cin >> a >> b;
        a--, b--;
        gra[a].push_back(b);
        ed.emplace_back(a, b);
    }
    vector<vector<ll>> cl = css(gra);
    vector<ll> ban(1 << m);
    for (int mask = 1; mask < (1 << m); mask++) {
        vector<vector<ll>> g(n);
        for (int i = 0; i < m; i++) {
            if ((mask >> i) & 1) {
                g[ed[i].second].push_back(ed[i].first);
            } else {
                g[ed[i].first].push_back(ed[i].second);
            }
        }
        if (css(g) == cl) {
            ban[mask] = 1;
        }
    }
    ll ans = 0, sm = 1;
    for (int mask = 0; mask < (1 << m); mask++) {
        bool fl = true;
        for (int submask = mask; submask > 0; submask = (submask - 1) & mask) {
            if (ban[submask]) {
                fl = false;
                break;
            }
        }
        if (!fl) {
            continue;
        }
        ll col = 0;
        for (int i = 0; i < m; i++) {
            if ((mask >> i) & 1) {
                col++;
            }
        }
        if (col == ans) {
            sm++;
        } 
        if (col > ans) {
            ans = col;
            sm = 1;
        }
    }
    cout << ans << '\n' << sm;
} 