#include <bits/stdc++.h>

using namespace std;
const int MAXN = 2001;
vector<int> g[MAXN], t[MAXN];
pair<int, int> E[MAXN];

void topsort(int u, vector<char> &used, vector<int> &order) {
    used[u] = 1;
    for (int v: g[u]) {
        if (!used[v]) {
            topsort(v, used, order);
        }
    }
    order.push_back(u);
}

void dfs(int u, int c, vector<char> &used, vector<int> &color) {
    used[u] = 1;
    color[u] = c;
    for (int v: t[u]) {
        if (!used[v]) {
            dfs(v, c, used, color);
        }
    }
}

vector<int> find_colors(int n) {
    vector<char> used(n + 1);
    vector<int> order, color(n + 1);
    for (int i = 1; i <= n; i++) {
        if (!used[i]) {
            topsort(i, used, order);
        }
    }
    used.assign(n + 1, false);
    reverse(order.begin(), order.end());
    int cnt = 1;
    for (int i: order) {
        if (!used[i]) {
            dfs(i, cnt, used, color);
            cnt++;
        }
    }
    return color;
}


int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    vector<int> color = find_colors(n);
    int cnt_good = 0;
    for (int i = 0; i < m; i++) {
        auto [u, v] = E[i];
        g[u].erase(find(g[u].begin(), g[u].end(), v));
        t[v].erase(find(t[v].begin(), t[v].end(), u));
        g[v].push_back(u);
        t[u].push_back(v);
        if (find_colors(n) != color) {
            cnt_good++;
        }
        g[v].erase(find(g[v].begin(), g[v].end(), u));
        t[u].erase(find(t[u].begin(), t[u].end(), v));
        g[u].push_back(v);
        t[v].push_back(u);
    }
    cout << min(cnt_good, n - 1) << "\n" << -1;
    return 0;
}