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

using namespace std;

vector<vector<int>> g, rg;
vector<pair<int, int>> edg;
vector<int> topsort;
vector<int> used;
int timer = 1;
int curmask;

void dfs(int v) {
    if (used[v] == timer)
        return;
    used[v] = timer;
    for (auto toid : g[v]) {
        auto [u, to] = edg[toid];
        if (!(curmask & (1 << toid)))
            swap(u, to);
        if (u == 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 toid : rg[v]) {
        auto [to, u] = edg[toid];
        if (!(curmask & (1 << toid)))
            swap(u, to);
        if (u == v)
            paint(to, col);
    }
}

signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n, m, G;
    cin >> n >> m >> G;
    edg.resize(m);
    g.resize(n), rg.resize(n);
    int curid = 0;
    for (auto& [u, v] : edg) {
        cin >> u >> v;
        --u, --v;
        g[u].push_back(curid);
        g[v].push_back(curid);
        rg[u].push_back(curid);
        rg[v].push_back(curid);
        curid += 1;
    }
    used.assign(n, 0);
    auto condense = [&](int mask) {
        curmask = mask;
        topsort.clear();
        topsort.reserve(n);
        for (int i = 0; i < n; ++i) {
            if (used[i] != timer)
                dfs(i);
        }
        timer += 1;
        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<int32_t> 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) {
            int32_t cur = mask;
            while (cur) {
                smth[cur] += 1;
                cur = (mask & (cur - 1));
            }
            smth[0] += 1;
        }
    }
    int mn = m;
    int32_t cnt = 1;
    for (int32_t 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;
}