No.1865 Make Cycle
タグ : / 解いたユーザー数 99
作問者 :
ぷら
shiomusubi496
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もしくは右上の雲マークをクリックしてアカウントを作成してください。