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

using namespace std;

#define int ll
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using ordered_set = __gnu_pbds::tree<int, __gnu_pbds::null_type, less<int>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;

mt19937 rnd(time(0));

const int MAXN = 2e3 + 52;
vector<int> g[MAXN];
vector<int> gr[MAXN];
int used[MAXN];
vector<int> tp;

void dfs_tp(int v) {
    used[v] = 1;
    for (auto &u: gr[v]) {
        if (!used[u]) {
            dfs_tp(u);
        }
    }
    tp.push_back(v);
}

int cur = 1;

void dfs(int v) {
    used[v] = cur;
    for (auto &u: g[v]) {
        if (!used[u]) {
            dfs(u);
        }
    }
}

inline void solve() {
    int n, m, G;
    cin >> n >> m >> G;
    int M = m;
    vector<pii> ed(m);
    for (auto &[x, y]: ed) {
        cin >> x >> y;
        x--;
        y--;
        g[x].push_back(y);
        gr[y].push_back(x);
    }
    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            dfs_tp(i);
        }
    }
    reverse(all(tp));
    fill(used, used + n, 0);
    for (auto &u: tp) {
        if (!used[u]) {
            dfs(u);
            cur++;
        }
    }
    vector<int> col(n);
    for (int i = 0; i < n; i++) col[i] = used[i];
    int ans = 0;
    int ans1 = 0;
    for (int ms = 0; ms < (1 << m); ms++) {
        bool f = 1;
        if (__builtin_popcount(ms) < ans) continue;
        for (int sub = ms; sub > 0; sub = ms & (sub - 1)) {
            if (!f) break;
            for (int i = 0; i < n; i++) g[i].clear();
            for (int i = 0; i < n; i++) gr[i].clear();
            for (int i = 0; i < m; i++) {
                if ((sub >> i) & 1) {
                    g[ed[i].second].push_back(ed[i].first);
                    gr[ed[i].first].push_back(ed[i].second);

                } else {
                    g[ed[i].first].push_back(ed[i].second);
                    gr[ed[i].second].push_back(ed[i].first);

                }
            }
            fill(used, used + n, 0);
            tp.clear();
            for (int i = 0; i < n; i++) {
                if (!used[i]) {
                    dfs_tp(i);
                }
            }
            reverse(all(tp));
            fill(used, used + n, 0);
            cur = 1;
            for (auto &u: tp) {
                if (!used[u]) {
                    dfs(u);
                    cur++;
                }
            }
            vector<int> mt(n + 1, -1);
            bool f1 = 0;
            for (int i = 0; i < n; i++) {
                if (mt[used[i]] == -1) {
                    mt[used[i]] = col[i];
                } else {
                    if (mt[used[i]] != col[i]) {
                        f1 = 1;
                        break;
                    }
                }
            }
            set<int> s;
            for (auto &x: mt) {
                if (x != -1 && s.find(x) != s.end()) f1 = 1;
                s.insert(x);
            }
            if (!f1) {
                f = 0;
            }
        }
        if (f) {
            if (__builtin_popcount(ms) > ans) {
                ans = __builtin_popcount(ms);
                ans1 = 0;
            }
            if (__builtin_popcount(ms) == ans) ans1++;
        }
    }
    cout << ans << "\n" << ans1;
}

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