#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

//#pragma GCC optimize("Ofast, unroll-loops, fast-math, no-stack-protector, inline")
//#pragma GCC target("avx2")

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using ld = long double;
using ull = unsigned long long;
#define int long long

const ll INF = 1e18 + 228;
const ll mod = 1e9 + 7;
const ld eps = 1e-8;

random_device rd;
mt19937 rnd(rd() + 228 + 57 - 179);

vector<vector<int>> g;
vector<int> used;

pair<int, int> ban;

bool dfs(int v, int f, int s) {
    if (used[v] == f) return 0;
    if (used[v] == s) return 1;
    used[v] = f;
    int ogo = 1;
    if (v == ban.second) {
        ogo &= dfs(ban.first, f, s);
    }
    for (auto i : g[v]) {
        if (v == ban.first && i == ban.second) continue;
        ogo &= dfs(i, f, s);
    }
    used[v] = s;
    return ogo;
}

void solve() {
    int n, m, gg;
    cin >> n >> m >> gg;
    g.resize(n);
    used.resize(n);
    vector<pair<int, int>> e;
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        g[--a].push_back(--b);
        e.emplace_back(a, b);
    }
    int ans = 0;
    for (int i = 0; i < m; ++i) {
        ban = e[i];
        ll ogo = 1;
        for (int j = 0; j < n; ++j) {
            ogo &= dfs(j, 2 * i + 1, 2 * i + 2);
        }
        ans += !ogo;
    }
    cout << ans << '\n' << 1;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int tt = 1;
    //cin >> tt;
    while (tt--) solve();
    return 0;
}
