#include #include #define rep(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++) using namespace atcoder; using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector u(m), v(m); rep(i, 0, m) cin >> u[i] >> v[i], u[i]--, v[i]--; int ac = 0, wa = m + 1; while (wa - ac > 1) { scc_graph gr(n); int mid = (ac + wa) / 2; rep(i, 0, mid) gr.add_edge(u[i], v[i]); auto scc = gr.scc(); if ((int)scc.size() == n) { ac = mid; } else { wa = mid; } } int ans = (wa == m + 1) ? -1 : wa; cout << ans << endl; }