#include <bits/stdc++.h>
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define endl '\n'
typedef long long ll;
using namespace std;

const int N = 2e3 + 5;
pair<int, int> eg[N];
int cmp[N];

vector<int> g[N], g2[N];
int u[N], u2[N];
vector<int> ts;

int dp[1 << 22], b[1 << 22];

void dfs0(int v) {
    u[v] = 1;
    for (auto to : g[v]) {
        if (!u[to]) dfs0(to);
    }
    ts.push_back(v);
}

int cnt = 2;
void dfs(int v) {
    u[v] = cnt;
    for (auto to : g2[v]) {
        if (u[to] == 1) dfs(to);
    }
}

int solve2(int mask, int n, int m) {
    for (int i = 0; i < 100; i++) {
        u2[i] = 0;
        u[i] = 0;
        g[i].clear();
        g2[i].clear();
    }
    ts.clear();

    for (int i = 0; i < m; i++) {
        auto [x, y] = eg[i];
        if ((mask >> i) & 1) swap(x, y);

        g[x].push_back(y);
        g2[y].push_back(x);
    }

    for (int i = 0; i < n; i++) {
        if (!u[i]) dfs0(i);
    }
    reverse(all(ts));

    cnt = 2;
    for (auto x : ts) {
        if (u[x] == 1) {
            dfs(x);
            cnt++;
        }
    }

    int w = 1;
    for (int i = 0; i < n; i++) {
        if (!u2[u[i]]) u2[u[i]] = w++;
        u[i] = u2[u[i]];
    }

    for (int i = 0; i < n; i++) {
        //cout << i << " " << u[i] << " " << cmp[i] << endl;
        if (u[i] != cmp[i]) return 1;
    }
    return 0;
}

void solve() {
    int n, m, gr;
    cin >> n >> m >> gr;

    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        x--;
        y--;

        eg[i] = {x, y};

        g[x].push_back(y);
        g2[y].push_back(x);
    }

    for (int i = 0; i < n; i++) {
        if (!u[i]) dfs0(i);
    }
    reverse(all(ts));

    for (auto x : ts) {
        if (u[x] == 1) {
            dfs(x);
            cnt++;
        }
    }

    int w = 1;
    for (int i = 0; i < n; i++) {
        if (!u2[u[i]]) u2[u[i]] = w++;
        cmp[i] = u2[u[i]];
    }

    for (int ms = 0; ms < (1 << m); ms++) {
        dp[ms] = 1;
    }

    //solve2(3, n, m);

    int k = 0, ans = 1;
    for (int ms = 1; ms < (1 << m); ms++) {
        int fl = solve2(ms, n, m);
        dp[ms] = (dp[ms] & fl);

        for (int j = 0; j < m; j++) {
            if ((ms >> j) & 1) {
                b[ms]++;
                continue;
            }

            dp[ms + (1 << j)] &= dp[ms];
        }

        //cout << ms << " " << fl << endl;
    }
    for (int ms = 1; ms < (1 << m); ms++) {
        if (dp[ms]) {
            if (k == b[ms]) ans++;
            else if (b[ms] > k) {
                k = b[ms];
                ans = 1;
            }
        }

        //cout << ms << " " << dp[ms] << endl;
    }
    cout << k << " " << ans << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solve();
}
