#include <bits/stdc++.h>

#ifndef LOCAL
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#endif

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;

const int mod = 1e9 + 7;

struct Modular {
    int x;

    Modular(int x = 0): x(x) {}

    friend Modular operator+(Modular a, Modular b) {
        int res = a.x + b.x;
        return res - (res >= mod ? mod : 0);
    }

    friend Modular operator-(Modular a, Modular b) {
        int res = a.x - b.x;
        return res + (res < 0 ? mod : 0);
    }

    friend Modular operator*(Modular a, Modular b) {
        return ll(a.x) * b.x % mod;
    }
};


const int maxn = 14;
set<int> g[maxn];
set<int> rg[maxn];
int usd[maxn];
int n;

vector<int> ob;
void dfs0(int v) {
    usd[v] = 1;
    for(int i: g[v]) {
        if(!usd[i])
            dfs0(i);
    }
    ob.push_back(v);
}

void dfs3(int v, int c, vector<int> &comp) {
    comp[v] = c;
    for (int i: rg[v]) {
        if (comp[i] == -1) {
            dfs3(i, c, comp);
        }
    }
}

vector<int> build() {
    memset(usd, 0, sizeof usd);
    ob.clear();
    for (int i = 0; i < n; ++i) {
        if (!usd[i]) {
            dfs0(i);
        }
    }
    reverse(all(ob));
    vector<int> comp(n, -1);
    int c = 0;
    for (int i: ob) {
        if (comp[i] == -1) {
            dfs3(i, c++, comp);
        }
    }
    return comp;
}

bool check(const vector<int> &a, const vector<int> &b) {
    vector<int> sup(n, -1);
    for (int i = 0; i < n; ++i) {
        if (a[i] != b[i]) {
            if (sup[a[i]] == -1) {
                sup[a[i]] = b[i];
            } else if (sup[a[i]] != b[i]) {
                return false;
            }
        } else if (sup[a[i]] != b[i] && sup[a[i]] != -1) {
            return false;
        } else {
            sup[a[i]] = b[i];
        }
    }
    return true;
}

void solve() {
    int m, e;
    cin >> n >> m >> e;
    vector<pair<int, int>> eds;
    for(int i = 0; i < m; ++i){
        int a, b;
        cin >> a >> b;
        --a, --b;
        g[a].insert(b);
        rg[b].insert(a);
        eds.emplace_back(a, b);
    }
    int mx = 0;
    int cnt = 1;
    vector<int> comp = build();
    for (int i = 1; i < (1 << m); ++i) {
        bool f = true;
        for (int j = i; j > 0; j = (j - 1) & i) {
            for(int k = 0; k < m; ++k) {
                if (j >> k & 1) {
                    auto [a, b] = eds[k];
                    g[a].erase(b);
                    rg[b].erase(a);
                    g[b].insert(a);
                    rg[a].insert(b);
                }
            }
            if (!check(comp, build())) {
                f = false;
            }
            for(int k = 0; k < m; ++k) {
                if (j >> k & 1) {
                    auto [a, b] = eds[k];
                    rg[a].erase(b);
                    g[b].erase(a);
                    rg[b].insert(a);
                    g[a].insert(b);
                }
            }
        }
        if (f) {
            if (mx == __popcount(i)) {
                ++cnt;
            } else if (mx < __popcount(i)) {
                mx = __popcount(i);
                cnt = 1;
            }
        }
    }
    cout << mx << "\n" << cnt;
}

signed main() {
#ifndef LOCAL
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#else
    freopen("C:\\Users\\User\\aboab\\input.txt", "r", stdin);
#endif
    solve();
}