#include <bits/stdc++.h>

using namespace std;

constexpr int MOD = 1e9 + 7;

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

void color(int v, int color_nw, vector<int> &colors, vector<vector<int>> &_g) {
    colors[v] = color_nw;
    for (auto u : _g[v]) {
        if (colors[u] == -1) {
            color(u, color_nw, colors, _g);
        }
    }
}

pair<int, vector<int>> get_dug(int n, vector<vector<int>> g) {
    vector<int> used(n);
    vector<int> ord;
    for (int i = 0; i < n; ++i) {
        if (!used[i]) {
            dfs(i, used, g, ord);
        }
    }
    vector<vector<int>> _g(n);
    for (int i = 0; i < n; ++i) {
        for (auto j : g[i]) {
            _g[j].push_back(i);
        }
    }
    reverse(ord.begin(), ord.end());
    vector<int> colors(n, -1);
    int cnt_colors = 0;
    for (auto v : ord) {
        if (colors[v] == -1) {
            color(v, cnt_colors, colors, _g);
            cnt_colors++;
        }
    }
    return make_pair(cnt_colors, colors);
}

vector<int> get_normal_colors(int n, int cnt_colors, vector<int> colors) {
    vector<int> val(cnt_colors, -1);
    int pos = 0;
    for (int i = 0; i < n; ++i) {
        if (val[colors[i]] == -1) {
            val[colors[i]] = pos;
            pos++;
        }
        colors[i] = val[colors[i]];
    }
    return colors;
}

void solve() {
    int n, m, subtask;
    cin >> n >> m >> subtask;
    vector<vector<int>> g(n);
    vector<pair<int, int>> edges(m);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        g[u].push_back(v);
        edges[i] = make_pair(u, v);
    }
    auto [cnt_colors, colors] = get_dug(n, g);
    colors = get_normal_colors(n, cnt_colors, colors);
    int ans1 = 0;
    for (int mask = 1; mask < (1 << m); ++mask) {
        int cnt_nw = 0;
        for (int i = 0; i < m; ++i) {
            if (mask & (1 << i)) {
                cnt_nw++;
            }
        }
        if (cnt_nw <= ans1) {
            continue;
        }
        bool check = true;
        for (int mask2 = 1; mask2 < (1 << cnt_nw); ++mask2) {
            int pos = 0;
            vector<vector<int>> g2(n);
            for (int i = 0; i < m; ++i) {
                if (mask & (1 << i)) {
                    if (mask2 & (1 << pos)) {
                        g2[edges[i].second].push_back(edges[i].first);
                    } else {
                        g2[edges[i].first].push_back(edges[i].second);
                    }
                    pos++;
                } else {
                    g2[edges[i].first].push_back(edges[i].second);
                }
            }
            auto [cnt_colors_nw, colors_nw] = get_dug(n, g2);
            colors_nw = get_normal_colors(n, cnt_colors_nw, colors_nw);
            if (colors == colors_nw) {
                check = false;
                break;
            }
        }
        if (check) {
            ans1 = cnt_nw;
        }
    }
    cout << ans1 << '\n';
    cout << -1 << '\n';
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}
