#include <bits/stdc++.h>

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")

//#define int long long

using ll = long long;
using namespace std;

const int MAXN = 20;

int c = 0;
vector<int> t, used1(MAXN), used2(MAXN);
vector<vector<int>> g(MAXN), gr(MAXN);

void dfs(int v, vector<int> &used) {
    used[v] = 1;
    for (auto u : g[v]) {
        if (!used[u]) {
            dfs(u, used);
        }
    }
    t.push_back(v);
}

void comp(int v, vector<int> &used) {
    used[v] = c;
    for (auto u : gr[v]) {
        if (!used[u]) {
            comp(u, used);
        }
    }
}

void solve() {
    int n, m, kal;
    cin >> n >> m >> kal;
    vector<pair<int, int>> e;
    vector<int> dp(1 << m);
    for (int i = 0; i < m; i++) {
        int v, u;
        cin >> v >> u;
        v--;
        u--;
        e.emplace_back(v, u);
        g[v].push_back(u);
        gr[u].push_back(v);
    }
    for (int i = 0; i < n; i++) {
        if (!used1[i]) {
            dfs(i, used1);
        }
    }
    used1.assign(n, 0);
    reverse(t.begin(), t.end());
    for (int i = 0; i < n; i++) {
        if (!used1[t[i]]) {
            c++;
            comp(t[i], used1);
        }
    }
    for (int mask = 0; mask < (1 << m); mask++) {
        for (int i = 0; i < m; i++) {
            if (mask & (1 << i)) {
                swap(e[i].first, e[i].second);
            }
        }
        g.clear();
        gr.clear();
        g.resize(n);
        gr.resize(n);
        for (int i = 0; i < m; i++) {
            auto [v, u] = e[i];
            g[v].push_back(u);
            gr[u].push_back(v);
        }
        used2.assign(n, 0);
        t.clear();
        for (int i = 0; i < n; i++) {
            if (!used2[i]) {
                dfs(i, used2);
            }
        }
        c = 0;
        used2.assign(n, 0);
        reverse(t.begin(), t.end());
        for (int i = 0; i < n; i++) {
            if (!used2[t[i]]) {
                c++;
                comp(t[i], used2);
            }
        }
        bool flag = 0;
        unordered_set<int> s;
        unordered_map<int, int> mp;
        for (int i = 0; i < m; i++) {
            if (mp.find(used2[i]) != mp.end()) {
                if (used1[i] != mp[used2[i]]) {
                    flag = 1;
                    break;
                }
            } else {
                if (s.find(used1[i]) != s.end()) {
                    flag = 1;
                    break;
                }
                mp[used2[i]] = used1[i];
                s.insert(used1[i]);
            }
        }
        if (flag) {
            dp[mask] = 1;
        } else {
            dp[mask] = 0;
        }
        for (int i = 0; i < m; i++) {
            if (mask & (1 << i)) {
                swap(e[i].first, e[i].second);
            }
        }
    }
    for (int mask = 1; mask < (1 << m); mask++) {
        if (dp[mask]) {
            continue;
        }
        for (int i = 0; i < m; i++) {
            if (mask & (1 << i)) {
                continue;
            }
            dp[mask + (1 << i)] = 0;
        }
    }
    int mx = 0, cnt = 0;
    for (int mask = 0; mask < (1 << m); mask++) {
        if (!dp[mask]) {
            continue;
        }
        int sum = 0;
        for (int i = 0; i < m; i++) {
            if (mask & (1 << i)) {
                sum++;
            }
        }
        if (sum > mx) {
            mx = sum;
            cnt = 1;
        } else if (sum == mx) {
            cnt++;
        }
    }
    if (mx == 0) {
        cnt = -1;
    }
    cout << mx << "\n" << cnt << "\n";
}

signed main() {
    int tests = 1;
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
//    cin >> t;
#else
    ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
#endif
//    cin >> t;
    while (tests--) {
        solve();
    }
}
