#ifdef LOCAL
#define _GLIBCXX_DEBUG
#else
#pragma GCC optimize("O3")
#endif

#include <bits/stdc++.h>

using namespace std;

#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) int((x).size())
using pii = pair<int, int>;
using pll = pair<int64_t, int64_t>;
using ll = int64_t;
using ull = uint64_t;
using ld = long double;
#define MAX_FAC 5000
const ll MOD = 1e9 + 7;

ll binpow(ll x, int p) {
    ll res = 1;
    while (p) {
        if (p % 2) res = res * x % MOD;
        x = x * x % MOD;
        p /= 2;
    }
    return res;
}

ll inv(ll x) {
    return binpow(x, MOD - 2);
}

vector<ll> fac(MAX_FAC);
vector<ll> inv_fac(MAX_FAC);
vector<vector<int>> g;
vector<vector<int>> back_g;
vector<vector<int>> full_g;
vector<bool> used;
vector<int> tout;
vector<int> component;

int n, m, G;
// int t = 52;
void get_tout(int v) {
    used[v] = true;
    for (int u : g[v]) {
        if (!used[u]) {
            get_tout(u);
        }
    }
    tout.push_back(v);
}

void mark_component(int v, int c) {
    component[v] = c;
    used[v] = true;
    for (int u : back_g[v]) {
        if (!used[u]) {
            mark_component(u, c);
        }
    }
}

vector<int> get_current_components() {
    tout.clear();
    fill(all(component), -1);
    fill(all(used), false);
    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            get_tout(i);
        }
    }
    fill(all(used), false);
    reverse(all(tout));
    //     for (int i = 0; i < n; i++) {
    //     cout << tout[i] << " ";
    // }
    int c = 0;
    for (int v : tout) {
        if (!used[v]) {
            mark_component(v, ++c);
        }
    }
    return component;
}

void solve() {
    cin >> n >> m >> G;
    g.resize(n);
    used.resize(n);
    full_g.resize(n);
    component.resize(n);
    back_g.resize(n);
    // vector<int> incoming(n);
    vector<pii> edges;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        g[u].push_back(v);
        full_g[v].push_back(u);
        full_g[u].push_back(v);
        back_g[v].push_back(u);
        edges.push_back({v, u});
        // incoming[v]++;
    }
    // int cnt_components = 0;
    // for (int i = 0; i < n; i++) {
    //     if (!marked[i]) {
    //         mark_component(i);
    //         cnt_components++;
    //     }
    // }
    vector<int> first_comp = get_current_components();
    vector<int> okay((1 << m));
    okay[0] = true;
    ll ans_amount = 0, ans_ways = 1;
    for (int i = 0; i < (1 << m); i++) {
        vector<pii> new_edges = edges;
        bool bad = false;
        for (int j = 0; j < m; j++) {
            if (i & (1 << j)) {
                swap(new_edges[j].ff, new_edges[j].ss);
                if (!okay[i - (1 << j)]) {
                    bad = true;
                }
            }
        }
        if (bad) {
            continue;
        }
        g.clear();
        back_g.clear();
        g.resize(n);
        back_g.resize(n);
        for (auto [u, v] : new_edges) {
            g[u].push_back(v);
            back_g[v].push_back(u);
        }
        vector<int> now_comp = get_current_components();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if ((now_comp[i] == now_comp[j]) != (first_comp[i] == first_comp[j])) {
                    bad = true;
                }
            }
        }
        if (bad) {
            okay[i] = true;
            int x = __builtin_popcount(i);
            if (x > ans_amount) {
                ans_amount = x;
                ans_ways = 1;
            }
            else if (x == ans_amount) {
                ans_ways++;
            }
        }
    }

    // for (int i = 0; i < n; i++) {
    //     cout << first_comp[i] << " ";
    // }
    // cout << '\n';
    // for (int i = 1; i < n; i++) {
    //     if (incoming[i] == 0 && g[i].empty()) {
    //         ans_amount++;
    //     }
    // }
    cout << ans_amount << '\n' << ans_ways << '\n';
    // cout << m - (n - 1) << ' ' << c(m, m - (n - 1)) << '\n';
}

signed main() {
    fac[0] = 1;
    for (int i = 1; i < MAX_FAC; i++) {
        fac[i] = fac[i - 1] * i;
    }
    for (int i = 0; i < MAX_FAC; i++) {
        inv_fac[i] = inv(fac[i]);
    }
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    while (t--) solve();
}