問題一覧 > 通常問題

No.1865 Make Cycle

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 96
作問者 : NaHCO314 / テスター : ぷら shiomusubi496 MtSaka
8 ProblemId : 7763 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-03-04 21:08:08

問題文

N 頂点 0 辺のグラフがあり、このグラフに Q 回の操作を行います。 i 回目の操作では、 Ai から Bi への有向辺を追加します。

Q 回の操作を順に行っていったとき、グラフに最初に閉路ができるのはいつか出力してください。厳密には、 j(1≤j≤i) 回目の操作を行ったときグラフに閉路が存在するような最小の i を出力してください。
ただし、そのような i が存在しない場合は −1 を出力してください。

入力

N Q
A1 B1
A2 B2
⋮
AQ BQ
  • 入力はすべて整数
  • 1≤N≤105
  • 1≤Q≤105
  • 1≤Ai,Bi≤N (1≤i≤Q)
  • Ai≠Bi (1≤i≤Q)

出力

最後に改行してください。

サンプル

サンプル1
入力
4 5
1 2
2 3
1 4
3 1
4 3
出力
4

4 回目までの操作を行うと、 1→2→3→1 で閉路ができます。 3 回目までの操作では閉路ができないので、 4 を出力します。

サンプル2
入力
5 10
3 2
3 4
1 4
1 5
5 2
3 5
1 2
4 2
4 5
3 1
出力
-1

すべての辺を追加しても、閉路はできません。

サンプル3
入力
16 20
2 6
8 1
2 5
12 8
4 11
15 12
9 13
9 12
8 7
12 11
8 10
14 8
15 14
16 3
15 12
15 11
15 13
3 16
1 7
5 6
出力
18
サンプル4
入力
33 4
33 4
33 4
33 4
33 4
出力
-1

多重辺が存在する場合があるので注意してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。