#pragma GCC optimize("O3")
#include <bits/stdc++.h>
//#define int long long
#define all(x) (x).begin(), (x).end()
#define f first
#define s second
#define pi pair<int, int>


using namespace std;

vector<vector<int>> g, rg;
vector<int> was, tps, comp;

void dfs1(int u) {
    if (was[u]) return;
    was[u] = 1;
    for (auto& v : g[u]) {
        dfs1(v);
    }
    tps.push_back(u);
}

int c = 0;

void dfs2(int u) {
    if (was[u]) return;
    was[u] = 1;
    comp[u] = c;
    for (auto& v : rg[u]) {
        dfs2(v);
    }
}

void solve() {
    int n, m, grp;
    cin >> n >> m >> grp;
    g.assign(n, {});
    rg.assign(n, {});
    vector<pi> eds(m);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        eds[i] = {u, v};
        g[u].push_back(v);
        rg[v].push_back(u);
    }
    was.assign(n, 0);
    for (int i = 0; i < n; ++i) {
        if (!was[i]) dfs1(i);
    }
    reverse(all(tps));
    comp.assign(n, 0);
    was.assign(n, 0);
    for (auto& el : tps) {
        if (!was[el]) {
            dfs2(el);
            ++c;
        }
    }
    vector<int> cmp = comp;

    auto recalc = [&](vector<int>& comp) {
        vector<int> was(n);
        vector<vector<int>> cc(n);
        for (int i = 0; i < n; ++i) {
            cc[comp[i]].push_back(i);
        }
        int cr = 0;
        for (int i = 0; i < n; ++i) {
            if (was[comp[i]]) continue;
            int c = comp[i];
            for (auto& el : cc[cr]) {
                comp[el] = c;
            }
            for (auto& el : cc[c]) {
                comp[el] = cr;
            }
            swap(cc[cr], cc[c]);
            was[comp[i]] = 1;
            ++cr;
        }
    };

    recalc(cmp);

    vector<int> good(1 << m);
    vector<int> cnt(m + 1);
    cnt[0] = 1;
    for (int mask = 1; mask < (1 << m); ++mask) {
        for (int i = 0; i < m; ++i) {
            if (mask & (1 << i)) {
                good[mask] |= good[mask ^ (1ll << i)];
            }
        }
        g.assign(n, {});
        rg.assign(n, {});
        for (int i = 0; i < m; ++i) {
            auto [u, v] = eds[i];
            if (mask & (1 << i)) {
                g[v].push_back(u);
                rg[u].push_back(v);
            } else {
                g[u].push_back(v);
                rg[v].push_back(u);
            }
        }
        tps.clear();
        was.assign(n, 0);
        for (int i = 0; i < n; ++i) {
            if (!was[i]) dfs1(i);
        }
        reverse(all(tps));
        comp.assign(n, 0);
        was.assign(n, 0);
        c = 0;
        for (auto& el : tps) {
            if (!was[el]) {
                dfs2(el);
                ++c;
            }
        }
        recalc(comp);
        if (comp == cmp) good[mask] = 1;

        if (!good[mask]) {
            ++cnt[__builtin_popcount(mask)];
        }
    }

    for (int i = m; i >= 0; --i) {
        if (cnt[i]) {
            cout << i << "\n" << cnt[i] << "\n";
            return;
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
}
