#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ld long double
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define int long long

vector<vector<int>> g, g1;
vector<int> order, used, b, ob;
int timer = 1, col = 1;

void topsort(int v) {
    used[v] = timer;
    for (int i: g[v]) {
        if (used[i] < timer) {
            topsort(i);
        }
    }
    order.pb(v);
}

void dfs(int v) {
    b[v] = col;
    for (int i: g1[v]) {
        if (!b[i]) {
            dfs(i);
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m, t;
    cin >> n >> m >> t;
    used.resize(n + 1);
    vector<pair<int, int>> a(m);
    for (int i = 0; i < m; ++i) {
        cin >> a[i].first >> a[i].second;
    }
    vector<int> dp((1 << m), 1);
    int ans = 0, kol = 0;
    for (int i = 0; i < (1 << m); ++i) {
        g.assign(n + 1, {});
        g1.assign(n + 1, {});
        b.assign(n + 1, 0);
        for (int j = 0; j < m; ++j) {
            if ((i >> j) & 1) {
                if (!dp[i ^ (1 << j)]) {
                    dp[i] = 0;
                    break;
                }
                g1[a[j].first].pb(a[j].second);
                g[a[j].second].pb(a[j].first);
            } else {
                g[a[j].first].pb(a[j].second);
                g1[a[j].second].pb(a[j].first);
            }
        }
        if (dp[i]) {
            order.clear();
            col = 1;
            for (int j = 1; j <= n; ++j) {
                if (used[j] < timer) {
                    topsort(j);
                }
            }
            for (int j = sz(order) - 1; j >= 0; --j) {
                if (!b[order[j]]) {
                    dfs(order[j]);
                    col++;
                }
            }
            map<int, int> f;
            for (int j = 1; j <= n; ++j) {
                if (!f.contains(b[j])) {
                    f[b[j]] = sz(f);
                }
                b[j] = f[b[j]];
            }
            if (i == 0) {
                ob = b;
            } else if (b == ob) {
                dp[i] = 0;
            }
        }
        if (dp[i] && i != 0) {
            int tek = __builtin_popcount(i);
            if (ans < tek) {
                ans = tek;
                kol = 1;
            } else if (ans == tek) {
                kol++;
            }
        }
        timer++;
    }
    if (ans == 0) {
        kol = 0;
    }
    cout << ans << "\n" << kol;
    return 0;
}
