#include <bits/stdc++.h>

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> goodmask;
    for (int mask = 0; mask < (1 << m) - 1; ++mask) {
        auto curcomp = condense(mask);
        renum(curcomp);
        bool flag = true;
        for (int i = 0; i < n; ++i) {
            if (begcomp[i] != curcomp[i]) {
                flag = false;
                break;
            }
        }
        if (flag)
            goodmask.push_back(mask);
    }
    vector<int> smth((1 << m));
    for (auto el : goodmask) {
        int cur = el;
        while (cur) {
            smth[cur] += 1;
            cur = (el & (cur - 1));
        }
        smth[0] += 1;
    }
    int mn = m;
    int cnt = 1;
    for (int mask = 0; mask < (1 << m) - 1; ++mask) {
        if (__builtin_popcount(mask) > mn)
            continue;
        bool flag = smth[mask];
        if (!flag) {
            if (__builtin_popcount(mask) == mn)
                cnt += 1;
            else {
                mn = __builtin_popcount(mask);
                cnt = 1;
            }
        }
    }
    cout << m - mn << '\n' << cnt;
}