#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#include <windows.h>

#define f first
#define s second
#define pb push_back
#define pf push_front
#define in insert
#define nl '\n'
#define orderedSet tree <int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update>

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC poison

typedef long double ld;
typedef int64_t int64;
typedef uint64_t uint64;
typedef uint32_t uint;

using namespace std;
using namespace __gnu_pbds;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());

#define int int64

const int N = 21, mod = 1e9 + 7;

bool was[N];
bool ok[1 << N];
int n, m, g, col[N], dp[N];
vector <int> v[N], w[N], order;

void topSort(int x) {
    was[x] = 1;
    for (int u : v[x])
        if (!was[u])
            topSort(u);
    order.pb(x);
}

void dfs2(int x, int c) {
    col[x] = c;
    for (int u : w[x])
        if (col[u] == -1)
            dfs2(u, c);
}

vector <int> makeComp() {
    fill(was, was + n, 0);
    order.clear();
    topSort(0);
    reverse(order.begin(), order.end());
    fill(col, col + n, -1);
    int cntCol = 0;
    for (int i = 0; i < n; ++i)
        if (col[i] == -1)
            dfs2(i, cntCol++);
    vector <int> ans(n);
    for (int i = 0; i < n; ++i)
        ans[i] = col[i];
    return ans;
}

main() {
    cin.tie(0); ios::sync_with_stdio(0); cout.tie(0);
    cin >> n >> m >> g;
    int X[m], Y[m];
    for (int i = 0; i < m; ++i) {
        cin >> X[i] >> Y[i];
             --X[i]; --Y[i];
        v[X[i]].pb(Y[i]);
        w[Y[i]].pb(X[i]);
    }
    auto g0 = makeComp();
    for (int msk = 0; msk < (1 << m); ++msk)
        ok[msk] = 1;
    int p = pow(3, m);
    for (int msk = 0; msk < p; ++msk) {
        for (int i = 0; i < n; ++i) {
            v[i].clear();
            w[i].clear();
        }
        for (int x = msk, i = 0; i < m; ++i, x /= 3) {
            if (x % 3 <= 1) {
                v[X[i]].pb(Y[i]);
                w[Y[i]].pb(X[i]);
            }
            else {
                v[Y[i]].pb(X[i]);
                w[X[i]].pb(Y[i]);
            }
        }
        auto g1 = makeComp();
        if (g0 != g1) {
            bool bad = 0;
            for (int x = msk, i = 0; i < m; ++i, x /= 3, bad *= 2)
                if (x > 0)
                    ++bad;
            ok[bad] = 0;
        }
    }
    int mx = 0, ans = 1;
    for (int msk = 0; msk < (1 << m); ++msk) {
        if (!ok[msk])
            continue;
        int cnt = __builtin_popcount(msk);
        if (cnt > mx) {
            mx = cnt;
            ans = 0;
        }
        ans += (cnt == mx);
    }
    cout << mx << nl << ans;
}
