#include using namespace std; // clang-format off //#include //using namespace atcoder; using ll = long long; using ld = long double; using pii = pair; using pll = pair; using pdd = pair; using vii = vector; using vll = vector; using vdd = vector; using vvii = vector>; using vvll = vector>; using vvdd = vector>; using vvvii = vector>>; using vvvll = vector>>; using vvvdd = vector>>; template using P = pair; template using V1 = vector; template using V2 = vector>; template using V3 = vector>>; template using pque = priority_queue, greater>; #define _overload3(_1, _2, _3, name, ...) name #define rep1(n) for (ll i = 0; i < (n); i++) #define rep2(i, n) for (ll i = 0; i < (n); i++) #define rep3(i, a, b) for (ll i = (a); i < (b); i++) #define rep(...) _overload3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__) #define rrep1(n) for (ll i = (n) - 1; i >= 0; i--) #define rrep2(i, n) for (ll i = (n) - 1; i >= 0; i--) #define rrep3(i, a, b) for (ll i = (b) - 1; i >= (a); i--) #define rrep(...) _overload3(__VA_ARGS__, rrep3, rrep2, rrep1)(__VA_ARGS__) #define all(x) (x).begin(), (x).end() #define sz(x) ((int)(x).size()) #define fi first #define se second #define pb push_back #define endl '\n' #define popcnt(x) __builtin_popcountll(x) #define uniq(x) (x).erase(unique((x).begin(), (x).end()), (x).end()); #define IOS ios::sync_with_stdio(false); cin.tie(nullptr); const int inf = 1 << 30; const ll INF = 1ll << 60; const ld DINF = numeric_limits::infinity(); const ll mod = 1000000007; //const ll mod = 998244353; const ld EPS = 1e-9; const ld PI = 3.1415926535897932; const ll dx[8] = {1, 0, -1, 0, 1, -1, -1, 1}; const ll dy[8] = {0, 1, 0, -1, 1, 1, -1, -1}; template bool chmax(T &a, const T &b) { if (a bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; } template T min(const vector &x) { return *min_element(all(x)); } template T max(const vector &x) { return *max_element(all(x)); } template ostream &operator<<(ostream &os, const pair &p) { return os << "(" << p.fi << ", " << p.se << ")"; } template ostream &operator<<(ostream &os, const vector &v) { os << "[ "; for (auto &z : v) os << z << " "; os << "]"; return os; } #ifdef _DEBUG #define show(x) cout << #x << " = " << x << endl; #else #define show(x) #endif ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; } ll rem(ll a, ll b) { return (a % b + b) % b; } // clang-format on // using mint = modint998244353; ll modpow(ll A, ll N, ll mod) { ll RES = 1; // 例えば3=101(2)なので、下位bitから順に1ならa倍する while (N) { if (N & 1) RES = RES * A % mod; A = A * A % mod; N >>= 1; } return RES; } vector tsort(vector> &G, int V) { vector DEG(V, 0); // 入次数をメモ for (int i = 0; i < V; i++) { for (int T : G[i]) DEG[T]++; } // 入次数0の点の集合を作成 queue QUE; for (int i = 0; i < V; i++) { if (DEG[i] == 0) QUE.push(i); } vector RES; while (QUE.size()) { int T = QUE.front(); QUE.pop(); RES.push_back(T); for (int NX : G[T]) { // 入次数を減らす DEG[NX]--; // 新たな入次数0の点を追加 if (DEG[NX] == 0) QUE.push(NX); } } return RES; } int main() { IOS; ll n, k; cin >> n >> k; vii r(k), c(k), deg(n, 0); vvii g(n); rep(k) { cin >> r[i] >> c[i]; r[i]--, c[i]--; g[r[i]].pb(c[i]); deg[c[i]]++; } queue q; rep(n) { if (deg[i] == 0) q.push(i); } vii res; while (!q.empty()) { int nex = q.front(); q.pop(); res.pb(nex); for (int x : g[nex]) { deg[x]--; if (deg[x] == 0) q.push(x); } } if (sz(res) == 0) { // 自己ループ cout << -1 << endl; return 0; } vll dp(n, 0), dis(n, 0); for (int v : res) { for (int nex : g[v]) chmax(dp[nex], dp[v] + 1); } ll ans = 0; rep(n) chmax(ans, dp[i]); show(dp); show(dis); cout << ans + 1 << endl; return 0; } /* メモ C=AB(行列の掛け算)に対し c_{i,j}=\sum_{k} a_{i,k}b_{k,j} より、A^2はi->どこか->jの経路数になる そこから再帰的に解説に書いてることが言える(と思う…) */