#include <bits/stdc++.h>
#pragma GCC target("avx2,popcnt")
#pragma GCC optimize("Ofast,unroll-loops,inline,fast-math,no-stack-protector")
#define int short

using namespace std;

vector<vector<int>> g, rg;
vector<int> topsort;
vector<int> used;

void dfs(int v) {
    if (used[v])
        return;
    used[v] = true;
    for (auto to : g[v]) {
        dfs(to);
    }
    topsort.push_back(v);
}

vector<int> comp;

void paint(int v, int col) {
    if (comp[v] != -1)
        return;
    comp[v] = col;
    for (auto to : rg[v])
        paint(to, col);
}

signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n, m, G;
    cin >> n >> m >> G;
    vector<pair<int, int>> edg(m);
    for (auto& [u, v] : edg) {
        cin >> u >> v;
        --u, --v;
    }
    auto condense = [&](int mask) {
        g.assign(n, {}), rg.assign(n, {});
        for (int i = 0; i < m; ++i) {
            auto [u, v] = edg[i];
            if (mask & (1 << i)) {
                g[u].push_back(v);
                rg[v].push_back(u);
            } else {
                rg[u].push_back(v);
                g[v].push_back(u);
            }
        }
        used.assign(n, 0);
        topsort.clear();
        for (int i = 0; i < n; ++i) {
            if (!used[i])
                dfs(i);
        }
        reverse(topsort.begin(), topsort.end());
        comp.assign(n, -1);
        int cur = 0;
        for (int i = 0; i < n; ++i) {
            if (comp[topsort[i]] == -1) {
                paint(topsort[i], cur++);
            }
        }
        return comp;
        };
    auto renum = [&](vector<int>& comps) {
        vector<int> cl(n, -1);
        for (int i = 0; i < n; ++i) {
            if (cl[comps[i]] == -1)
                cl[comps[i]] = i;
            comps[i] = cl[comps[i]];
        }
        };
    auto begcomp = condense((1 << m) - 1);
    renum(begcomp);
    vector<int> smth((1 << m));
    for (int32_t mask = 0; mask < (1 << m) - 1; ++mask) {
        auto curcomp = condense(mask);
        bool flag = true;
        vector<int> cl(n, -1);
        for (int i = 0; i < n; ++i) {
            if (cl[curcomp[i]] == -1)
                cl[curcomp[i]] = i;
            if (cl[curcomp[i]] != begcomp[i]) {
                flag = false;
                break;
            }
        }
        if (flag) {
            int cur = mask;
            while (cur) {
                smth[cur] += 1;
                cur = (mask & (cur - 1));
            }
            smth[0] += 1;
        }
    }
    int mn = m;
    int32_t cnt = 1;
    for (int mask = 0; mask < (1 << m) - 1; ++mask) {
        if (smth[mask])
            continue;
        int tmp = __builtin_popcount(mask);
        if (tmp == mn)
            cnt += 1;
        else if (tmp < mn) {
            mn = tmp;
            cnt = 1;
        }
    }
    cout << m - mn << '\n' << cnt;
}