//#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr ll INF = 1e18;

void dfs1(ll v, vector<vector<ll>> &g, vector<bool> &used, vector<ll> &ord) {
    used[v] = true;
    for (ll to : g[v]) {
        if (!used[to]) {
            dfs1(to, g, used, ord);
        }
    }
    ord.push_back(v);
}

void dfs2(ll v, vector<vector<ll>> &g, vector<ll> &colour, ll cur_colour) {
    colour[v] = cur_colour;
    for (ll to : g[v]) {
        if (colour[to] == -1) {
            dfs2(to, g, colour, cur_colour);
        }
    }
}

void calc_comp(ll n, vector<vector<ll>> &g, vector<ll> &colour, ll &k) {
    vector<ll> ord;
    vector<bool> used(n, false);
    for (ll i = 0; i < n; ++i) {
        if (!used[i]) {
            dfs1(i, g, used, ord);
        }
    }
    reverse(ord.begin(), ord.end());

    vector<vector<ll>> rev(n);
    for (ll i = 0; i < n; ++i) {
        for (ll to : g[i]) {
            rev[to].push_back(i);
        }
    }
    k = 0;
    colour.resize(n, -1);
    for (ll i = 0; i < n; ++i) {
        if (colour[ord[i]] == -1) {
            dfs2(ord[i], rev, colour, k++);
        }
    }
}

bool check_comp(ll n, ll k1, vector<ll> &c1, ll k2, vector<ll> &c2) {
    if (k1 != k2) {
        return false;
    }

    vector<ll> parall(k1, -1);
    for (ll i = 0; i < n; ++i) {
        if (parall[c1[i]] == -1) {
            parall[c1[i]] = c2[i];
        } else if (c2[i] != parall[c1[i]]) {
            return false;
        }
    }
    return true;
}

bool check_lol(ll n, ll k1, vector<ll> &c1, vector<vector<ll>> &g, vector<pair<ll, ll>> &v1, vector<pair<ll, ll>> &v2) {
    ll cnt = 0;
    for (ll i = 0; i < (1ll << v1.size()); ++i) {
        ll i1 = i;
        for (ll j = 0; j < v1.size(); ++j) {
            if (i1 & 1) {
                g[v1[j].first].push_back(v1[j].second);
            } else {
                g[v2[j].first].push_back(v2[j].second);
            }
            i1 >>= 1;
        }

        vector<ll> c2;
        ll k2;
        calc_comp(n, g, c2, k2);
        if (check_comp(n, k1, c1, k2, c2)) {
            cnt++;
        }

        i1 = i;
        for (ll j = 0; j < v1.size(); ++j) {
            if (i1 & 1) {
                g[v1[j].first].pop_back();
            } else {
                g[v2[j].first].pop_back();
            }
            i1 >>= 1;
        }
    }

    if (cnt == 1) {
        return true;
    }
    return false;
}

void solve() {
    ll n, m, group;
    cin >> n >> m >> group;
    vector<vector<ll>> g(n);
    for (ll i = 0; i < m; ++i) {
        ll a, b;
        cin >> a >> b;
        a--;
        b--;
        g[a].push_back(b);
    }

    vector<ll> c1;
    ll k1;
    calc_comp(n, g, c1, k1);

    ll ans = -1, cnt = 0;
    for (ll i = 0; i < (1ll << m); ++i) {
        vector<vector<ll>> g1(n);
        vector<pair<ll, ll>> venom1, venom2;
        ll i1 = i, cur = 0;
        for (ll j = 0; j < n; ++j) {
            for (ll jj : g[j]) {
                if (i1 & 1) {
                    g1[j].push_back(jj);
                } else {
                    venom1.emplace_back(j, jj);
                    venom2.emplace_back(jj, j);
                    cur++;
                }
                i1 >>= 1;
            }
        }

        if (check_lol(n, k1, c1, g1, venom1, venom2)) {
            if (ans == cur) {
                cnt++;
            } else if (ans < cur) {
                ans = cur;
                cnt = 1;
            }
        }
    }

    cout << ans << ' ' << cnt << '\n';
}

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    ll t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
}
