はじめに
ei1821は筍派(急進派)である。
$N$の人がいます。
わんぱくな彼らは鬼ごっこをしたくなりました。
鬼ごっこは足の速さや体力が関係してきます。
彼らは絶対に手を抜かず、気を抜かずに全力で鬼ごっこに取り組みます。
なので、当てられる相手とどうしても当てられない相手が生まれてしまいます。
当てる、とは"鬼役が$x$から$y$へ移る"ことを意味します。
当てられる相手はいつでも当てられて、当てられない相手には絶対に当てることが出来ません。
また、彼らは出来るだけ鬼ごっこで楽しみたいです。
彼らは鬼ごっこの楽しさを"鬼役が移動する回数"で定義しました。
鬼役が1回動いたとき楽しさは1です。
鬼は誰から始めてもかまいません。
誰が誰にあてることが出来るかの情報が与えられるので、鬼ごっこの楽しさの最大を教えてください。また、鬼ごっこが永遠に終わらない状況も生まれているかどうかも教えてください。
問題
人数$N$と関係性が$M$ある。
関係性とは、$x$と$y$について"$x$は$y$に当てることが出来る"というものである。
関係性$x$と$y$が$M$個与えられる。
その関係から、鬼ごっこが一生続く状況が生まれれば-1を、
そうでなければ鬼ごっこの楽しさの最大を一行で出力せよ。
入力
N M x1 y1 x2 y2 ... xM yM最後の改行を忘れずに。
制約
- 1 ≤ $N$ ≤ 105
- 0 ≤ $M$ ≤ min($N$($N$-1),105)
- 1 ≤ $x$i,$y$i ≤ $N$
- $x$i ≠ $y$i
- $x$i,$y$i ≠ $x$j,$y$j (i ≠ j)
入出力例
例1
入力
3 3 1 2 1 3 2 3
出力
21は2と3に、2は3にあてることができるため、1が鬼の状態でスタートすることで鬼が1→2→3と遷移し、これが最大の楽しさとなります。
例2
入力
3 3 1 2 2 3 3 1
出力
-1三すくみの状態になっています。
永遠に鬼ごっこはおわりません。
例3
入力
6 6 1 2 2 3 2 4 3 4 5 6 6 5
出力
-11を鬼役で開始すれば1→2→3→4と遷移して鬼ごっこは終わるが、5と6のどちらかから鬼ごっこが開始すれば永遠に終わらないため、-1を出力する。