#include <bits/stdc++.h>
using namespace std;
#define int long long

struct DSU {
    vector < int > p, s;
    DSU(int n) {
        p.resize(n); iota(begin(p), end(p), 0);
        s.resize(n, 1);
    };
    int get(int v) { return (p[v] == v ? v : p[v] = get(p[v])); }
    bool unite(int a, int b) {
        a = get(a); b = get(b);
        if (a == b) return false;
        if (s[a] < s[b]) swap(a, b);
        s[a] += s[b];
        p[b] = a;
        return true;
    }
};

main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, m, g;
    cin >> n >> m >> g;
    vector < vector < pair < int , int > > > G(n), Gr(n);
    vector < pair < int , int > > ve;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v; u--; v--;
        G[u].push_back({v, i});
        Gr[v].push_back({u, i});
        ve.push_back({u, v});
    }

    function < vector < int > (int, int jj) > css = [&](int ii, int jj) {
        vector < int > cl(n, -1), top;
        vector < bool > mark(n);
        int U, V;
        if (jj != -1) {
            U = ve[jj].first, V = ve[jj].second;
        }
        function < void(int) > dfs1 = [&](int v) {
            mark[v] = 1;
            for (auto [u, idx] : G[v]) if (idx != ii && idx != jj)
                if (!mark[u]) dfs1(u);
            if (jj != -1 && v == V && !mark[U]) dfs1(U);
            top.push_back(v);
        };
        int T = -1;
        function < void(int) > dfs2 = [&](int v) {
            cl[v] = T;
            for (auto [u, idx] : Gr[v]) if (idx != ii && idx != jj)
                if (cl[u] == -1) dfs2(u);
            if (jj != -1 && v == U && cl[V] == -1) dfs2(V);
        };
        for (int i = 0; i < n; i++) if (!mark[i]) dfs1(i);
        reverse(begin(top), end(top));
        for (auto i : top) if (cl[i] == -1) {
            T++;
            dfs2(i);
        }

        vector < vector < int > > ps(T + 1);
        for (int i = 0; i < n; i++) ps[cl[i]].push_back(i);
        vector < int > color(n, -1);
        T = 0;
        for (int i = 0; i < n; i++) {
            if (color[i] != -1) continue;
            int tp = cl[i];
            mark[tp] = 1;
            for (auto u : ps[tp]) color[u] = T;
            T++;
        }
        return color;
    };

    vector < pair < int , int > > gd1, gd2;
    vector < int > color = css(-1, -1);
    int kk = 0;
    for (int i = 0; i < m; i++) {
        bool g = 0;
        if (ve[i].first + 1 == ve[i].second) g = 1;
        if (ve[i].first == n && ve[i].second == 1) g = 1;
        if (!g) continue;
        vector < int > c = css(i, -1);
        if (color != c) {
            gd1.push_back(ve[i]);
            continue;
        }
        c = css(-1, i);
        if (color != c) {
            gd2.push_back(ve[i]);
            continue;
        }
        kk++;
    }
    int ans = 0;
    ans += gd1.size() + gd2.size();
    cout << ans << '\n' << 1;
}
