#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<vector<int>> gr;
vector<int> vst;
vector<int> tp;
int ans = 0;
void dfs(int v, int ok, int z) {
    vst[v] = 1;
    ans += ok;
    for (auto x : gr[v]) {
        if (!vst[x]) dfs(x, 1, z);
    }
    if (z) tp.push_back(v);
}
const int N = 2001;
int p[N];
int h[N];
int get(int v) {
    if (v == p[v]) return v;
    return p[v] = get(p[v]);
}
void unite(int u, int v) {
    if (h[u] < h[v]) swap(u, v);
    h[u] = max(h[u], h[v] + 1);
    p[v] = u;
}
void dfs(int v) {
    vst[v] = 1;
    for (auto x : gr[v]) {
        if (!vst[x]) dfs(x);
    }
}
int r[N][N];
map<pair<int, int>, vector<pair<int, int>>> gg;
map<pair<int, int>, int> vs;
void dfs2(pair<int, int> e) {
    vs[e] = 1;
    for (auto x :gg[e]) {
        if (!vs[x]) dfs2(x);
    }
}
signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int n, m, g; cin >> n >> m >> g;
    vector<vector<int>> iz(n), in(n);
    for (int i = 0; i < n; i++) {
        p[i] = i;
        h[i] = 1;
    }
    gr.resize(n); vst.resize(n);
    vector<int> deg1(n), deg2(n);
    vector<pair<int, int>> reb;
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >>v;
        u--; v--;
        gr[u].push_back(v);
        deg1[u]++; deg2[v]++;
        iz[u].push_back(i);
        in[v].push_back(i);
        reb.push_back({u, v});
    }
    set<int> s;
    vector<pair<vector<int>, int>> e;
    for (int i = 0; i < n; i++) {
        if (iz[i].size() == 1) {
            s.insert(iz[i][0]);
            for (auto y : in[i]) {
                s.insert(y);
            }
            e.push_back({in[i], iz[i][0]});
        }
        if (in[i].size() == 1) {
            s.insert(in[i][0]);
            for (auto y : iz[i]) {
                s.insert(y);
            }
            e.push_back({iz[i], in[i][0]});
        }
    }
    vector<int> ss;
    int answer = 0;
    for (auto x : s) ss.push_back(x);
    for (int i = 0; i < (1 << ss.size()); i++) {
        set<int> vst;
        int izn = 0;
        for (int j = 0; j < ss.size(); j++) {
            if ((i >> j) & 1) {
                vst.insert(ss[j]);
                izn++;
            }

        }
        for (int it = 0; it < m; it++) {
            for (int j = 0; j < e.size(); j++) {
                bool ok = true;
                for (auto x:  e[j].first) {
                    if (vst.find(x) == vst.end()) {
                        ok = false; break;
                    }
                }
                if (ok) vst.insert(e[j].second);
            }
        }
        answer = max(answer, (int)vst.size() - izn);
    }
    cout << answer << '\n';
    cout << 1 << '\n';
    return 0;
}
