#include <bits/stdc++.h>

//#define int ll
#define vec vector
#define ll long long
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pb push_back
#define pii pair < int, int >

using namespace std;

const int N = 21;
const int mod = 1e9 + 7;
const int oo = 2e9;
const ll OO = 1e18;

template <typename T>
bool umx (T &a, T b) {return (a < b ? (a = b, 1) : 0); }

int bpow (int a, int b) {
    if (b == 0)
        return 1;
    if (b % 2)
        return a * bpow(a, b - 1);
    int t = bpow(a, b / 2);
    return t * t;
}

void update (int v, int l, int r, int ql, int qr, int x) {
    if (l > qr || r < ql)
        return;
    if (l >= ql && r <= qr) {

        return;
    }
    int m = l + r >> 1;
    update(v << 1, l, m, ql, qr, x);
    update(v << 1 | 1, m + 1, r, ql, qr, x);
//    seg[v] =
}

vec < int > g[N];
vec < int > gt[N], gr[N];
vec < int > base, c, ord;
bool used[N];

void dfs (int v) {
    used[v] = 1;
    for (int u : gt[v])
        if (!used[u])
            dfs(u);
    ord.pb(v);
}

void scc (int v, int ci) {
//    cout << v << " " << ci << "\n";
    c[v] = ci;
    for (int u : gr[v]) {
        if (c[u] == -1) {
            scc(u, ci);
        }
    }
}

int to[N], w[N];
const int M = 1048576;
bool a[M], b[M];

signed main () {
    int n, m, g1g1;
    cin >> n >> m >> g1g1;
    vec < pii > e;
    for (int i = 0, u, v; i < m; ++i) {
        cin >> u >> v;
        --u, --v;
        g[u].pb(v);
        e.pb({u, v});
    }
    base.resize(n);
    vec < int > good;
    c.resize(n);
    for (int mm = 0; mm < 1 << m; ++mm) {

        for (int i = 0; i < n; ++i) {
            gt[i].clear();
            gr[i].clear();
        }

        for (int i = 0; i < m; ++i) {
            if ((1 << i) & mm)
                swap(e[i].f, e[i].s);
            gt[e[i].f].pb(e[i].s);
            gr[e[i].s].pb(e[i].f);
            if ((1 << i) & mm)
                swap(e[i].f, e[i].s);
        }
        ord.clear();
        fill(used, used + n, 0);
        for (int i = 0; i < n; ++i)
            if (!used[i])
                dfs(i);

        reverse(all(ord));
        int coli = 0;
        fill(all(c), -1);
        fill(to, to + n, -1);
        fill(w, w + n, -1);
        for (int i : ord) {
            if (c[i] == -1)
                scc(i, coli++);
//            cout << i << " ";
        }
//        cout << "\n";
        if (mm == 0)
            base = c;


        int ok = 1;
        for (int i = 0; i < n; ++i) {
            if (to[base[i]] == -1 && w[c[i]] == -1)
                to[base[i]] = c[i];
            w[c[i]] = 1;
            if (to[base[i]] != c[i]) {
                ok = 0;
                break;
            }

        }

        if (ok && mm)
            a[mm] = 1;
    }
//    cout << sz(good) << "\n";
    int best = 0, cnt = 0;
//    for (int i = 1; i < sz(good); ++i) {
//        int x = good[i];
//        a[x] = 1;
//        for (int j = 0; j < n; ++j) {
//            if ((1 << j) & x)
//                a[x] |= a[x ^ (1 << j)];
//        }
//
////        if (a[x]) {
////            int vi = __builtin_popcount(x);
////            if (vi > best) {
////                cnt = 1;
////                best = vi;
////            } else if (vi == best) cnt++;
////        }
////        cout << x << " " << a[x] << "\n";
//    }

    for (int x = 0; x < 1 << m; ++x) {
        for (int j = 0; j < m; ++j) {
            if ((1 << j) & x)
                a[x] |= a[x ^ (1 << j)];
        }

        if (!a[x]) {
            int vi = __builtin_popcount(x);
            if (vi > best) {
                cnt = 1;
                best = vi;
            } else if (vi == best) cnt++;

        }
    }

    cout << best << " " << cnt;
}
