목표 달성 시점

$1$번부터 $N$번까지 번호가 붙은 정점이 있다. 처음에는 간선이 없으며 $M$개의 간선이 순서대로 추가된다.

$Q$개의 질문에 대해 두 정점이 처음으로 같은 연결 요소에 속하게 되는 간선 번호를 출력하라. 끝까지 같은 연결 요소에 속하지 않는다면 -1을 출력한다.

첫 번째 줄에 정점의 개수 $N$, 추가되는 간선의 개수 $M$, 질문의 개수 $Q$가 주어진다. $(2 \leq N \leq 200\,000,\ 1 \leq M,Q \leq 200\,000)$

두 번째 줄부터 $M$개의 줄에 걸쳐 추가되는 간선의 양 끝 정점 $u$, $v$가 순서대로 주어진다. $(1 \leq u,v \leq N,\ u \neq v)$

그 다음 줄부터 $Q$개의 줄에 걸쳐 질문을 나타내는 두 정점 $a$, $b$가 주어진다. $(1 \leq a,b \leq N,\ a \neq b)$

이미 같은 연결 요소에 속한 두 정점을 잇는 간선이 추가될 수 있다.

각 질문마다 두 정점이 처음으로 같은 연결 요소에 속하게 되는 간선 번호를 한 줄에 하나씩 출력한다.