#include <bits/stdc++.h>
#pragma GCC optimize("Ofast", "inline")
#include <ext/pb_ds/assoc_container.hpp>

#define pii pair <int, int>
#define fi first
#define se second
#define pb push_back
#define int int64_t
#define pw(x) (int64_t(1)<<x)

using namespace std;
using namespace __gnu_pbds;

typedef tree <int, null_type, less_equal <int>, rb_tree_tag, tree_order_statistics_node_update> oset;

mt19937 gen(time(0));

const int N = 2e3 + 50;

int fup[N], tin[N], timer = 1;
set <pii> ban;
vector <int> g[N];

vector <int> order;
bool used[N];
vector <int> gr[N];

void topsort (int v) {
    used[v] = 1;
    for (auto to : g[v]) {
        if (!used[to]) {
            topsort(to);
        }
    }
    order.pb(v);
}

int cl[N], color = 1;

void DFS (int v) {
    cl[v] = color;
    for (auto to : gr[v]) {
        if (!cl[to]) {
            DFS(to);
        }
    }
}

int32_t main () {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif // LOCAL
    int n, m, group;
    cin >> n >> m >> group;
    vector <pii> edges;
    for (int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        g[x].pb(y);
        gr[y].pb(x);
        edges.pb({x, y});
    }
    for (int i = 0; i < n; ++i) {
        if (!used[i]) {
            topsort(i);
        }
    }
    reverse(order.begin(), order.end());
    for (int i : order) {
        if (!cl[i]) {
            DFS(i);
            color++;
        }
    }
    set <vector <int>> v1;
    {
        vector <int> v[color];
        for (int i = 0; i < n; ++i) {
            v[cl[i]].pb(i);
        }
        for (int i = 0; i < color; ++i) {
            if (!v[i].empty()) {
                v1.insert(v[i]);
            }
        }
    }
    int ans = 0;
    for (int msk = 0; msk < pw(m); msk++) {
        int sub = msk;
        bool bad = 1;
        int ways = 0;
        for (int sub = 0; sub <= msk; ++sub) {
            if ((sub&msk) != sub) continue;
            for (int i = 0; i < n; ++i) g[i].clear();
            for (int i = 0; i < m; ++i) {
                if (sub & pw(i)) {
                    g[edges[i].se].pb(edges[i].fi);
                } else {
                    g[edges[i].fi].pb(edges[i].se);
                }
            }
            fill(used, used + n, 0);
            fill(cl, cl + n, 0);
            order = {};
            for (int i = 0; i < n; ++i) {
                gr[i].clear();
            }
            for (int i = 0; i < n; ++i) {
                for (auto to : g[i]) {
                    gr[to].pb(i);
                }
            }
            for (int i = 0; i < n; ++i) {
                if (!used[i]) {
                    topsort(i);
                }
            }
            reverse(order.begin(), order.end());
            color = 1;
            for (int i : order) {
                if (!cl[i]) {
                    DFS(i);
                    color++;
                }
            }
            vector <int> v[color];
            for (int i = 0; i < n; ++i) {
                v[cl[i]].pb(i);
            }
            bool have = 1;
            for (int i = 0; i < color; ++i) {
                if (!v[i].empty()) {
                    if (!v1.count(v[i])) have = 0;
                }
            }
            if (have) {
                ways++;
            }
//            if (sub == 0) break;
//            sub = ((sub - 1) & msk);
        }
        if (ways == 1) ans = max(ans, (int)__builtin_popcount(msk));
    }
    cout << ans << '\n' << -1;
}
