#include <bits/stdc++.h>

#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using ld = long double;
template<class T> using ordered_set = tree<T, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;

const int mod = int(1e9) + 7, lg = 20;
const ll inf = ll(2e18) + 36;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());


ll n, m, grr;
vector<vector<ll>> g, gr;
vector <bool> used;
vector <ll> srt;

void dfs1(ll v, const vector <vector <ll>>& g) {
    used[v] = true;
    for (auto& u : g[v]) {
        if (used[u]) continue;
        dfs1(u, g);
    }
    srt.emplace_back(v);
}

int curC = 0;
void dfs2(ll v, vector <ll>& cmp, const vector <vector <ll>>& g) {
    used[v] = true;
    cmp[v] = curC;
    for (auto& u : g[v]) {
        if (used[u]) continue;
        dfs2(u, cmp, g);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif
    cin >> n >> m >> grr;
    g.resize(n);
    used.resize(n);
    gr.resize(n);
    vector <pair <ll, ll>> e;
    for (ll i = 0; i < m; i++) {
        ll u, v;
        cin >> u >> v;
        u--;
        v--;
        e.emplace_back(u, v);
        g[u].emplace_back(v);
        gr[v].emplace_back(u);
    }
    for (ll v = 0; v < n; v++) {
        if (!used[v]) {
            dfs1(v, g);
        }
    }
    reverse(srt.begin(), srt.end());
    vector <ll> cmp(n, -1);
    used.assign(n, false);
    for (auto& v : srt) {
        if (!used[v]) {
            dfs2(v, cmp, gr);
        }
    }
    ll best = 0, cc = 0;
    for (ll ms = 0; ms < (1 << n); ms++) {
        ll l = 0;
        vector <ll> p;
        for (ll i = 0; i < n; i++) {
            if ((ms >> i) & 1) {
                p.emplace_back(i);
                l++;
            }
        }
        ll cnt = 0;
        for (ll mk = ms; mk >= 0; mk = (mk - 1) & ms) {
            vector <vector <ll>> g1(n), gr1(n);
            for (ll i = 0; i < n; i++) {
                if ((mk >> i) & 1) {
                    g1[e[i].second].emplace_back(e[i].first);
                    gr1[e[i].first].emplace_back(e[i].second);
                } else {
                    g1[e[i].first].emplace_back(e[i].second);
                    gr1[e[i].second].emplace_back(e[i].first);
                }
            }
            used.assign(n, false);
            srt.clear();
            for (ll v = 0; v < n; v++) {
                if (!used[v]) {
                    dfs1(v, g1);
                }
            }
            reverse(srt.begin(), srt.end());
            vector <ll> cmp1(n, -1);
            used.assign(n, false);
            for (auto& v : srt) {
                if (!used[v]) {
                    dfs2(v, cmp1, gr1);
                }
            }
            if (cmp1 == cmp) {
                if (cnt) {
                    cnt = 2;
                    break;
                }
                cnt = 1;
            }
        }
        if (cnt == 1) {
            if (l > best) {
                best = l;
                cc = 0;
            }
            if (l == best) cc++;
        }
    }
    cout << best << '\n' << cc;
    return 0;
}
