問題一覧 > 通常問題

No.1865 Make Cycle

レベル : / AI推定難易度 : 1175 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 99
作問者 : NaHCO314 / テスター : ぷら shiomusubi496 MtSaka
お気に入りにしたユーザー ProblemId : 7763 / 自分の提出
問題文最終更新日: 2022-03-04 21:08:08
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 334 (順位表) の他の問題:

Problem Statement

There is a graph with $N$ vertices and $0$ edges, and $Q$ operations are performed on this graph. In the $i$-th operation, a directed edge from $A_i$ to $B_i$ is added.

When the $Q$ operations are performed in order, output when a cycle first appears in the graph. Strictly speaking, output the smallest $i$ such that the graph contains a cycle after performing the $j(1\leq j\leq i)$-th operations.
If no such $i$ exists, output $-1$.

Input

$N$ $Q$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_Q$ $B_Q$
  • All inputs are integers.
  • $1 \leq N \leq 10^5$
  • $1 \leq Q \leq 10^5$
  • $1 \leq A_i, B_i \leq N$ $(1 \leq i \leq Q)$
  • $A_i \neq B_i$ $(1 \leq i \leq Q)$

Output

Print a newline at the end.

Sample

Sample 1
Input
4 5
1 2
2 3
1 4
3 1
4 3
Output
4

After performing the operations up to the $4$-th one, a cycle $1\to2\to3\to1$ is formed. No cycle is formed by the operations up to the $3$-rd one, so output $4$.

Sample 2
Input
5 10
3 2
3 4
1 4
1 5
5 2
3 5
1 2
4 2
4 5
3 1
Output
-1

No cycle is formed even after all edges are added.

Sample 3
Input
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
Output
18
Sample 4
Input
33 4
33 4
33 4
33 4
33 4
Output
-1

Note that there may be multiple edges.

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