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

const int N = 2005;
int n, m, group;
bool reachable[N][N], reach[N][N], is_edge[N][N];
vector<int> g[N];
vector<pair<int, int>> edges;

bool vis[N];
void visit(int v, int id = -1){
    vis[v] = 1;
    for (int e : g[v]){
        if (e == id) continue;
        int u = edges[e].first + edges[e].second - v;
        if (!vis[u]) visit(u);
    }
}

int main(){
    memset(is_edge, -1, sizeof is_edge);

    cin >> n >> m >> group;
    for (int i = 0; i < m; i ++){
        int u, v;
        cin >> u >> v;
        g[u].push_back(i);
        is_edge[u][v] = i;
        edges.push_back({u, v});
    }

    for (int v = 1; v <= n; v ++){
        visit(v);
        for (int u = 1; u <= n; u ++)
            reachable[v][u] = vis[u];
        memset(vis, 0, sizeof vis);
    }

    int ans = 0;
    for (int e = 0; e < m; e ++){
        auto [v, u] = edges[e];
        visit(v, e);
        if (vis[u]) reach[v][u] = 1;
        memset(vis, 0, sizeof vis);
        ans += reach[v][u];
    }

    cout << m - 1 << endl << 1 << endl;
}