대화방이 처음 이어진 순간

문제

사내 메신저에는 1번부터 N번까지 번호가 붙은 N명의 사원이 있고, 처음에는 모두 각자 혼자만 있는 대화방에 속해 있다. 운영 기록에는 M개의 합류 이벤트가 시간 순서대로 1번부터 M번까지 번호가 매겨져 있다. i번 이벤트 'a b'는 사원 a가 속한 대화방과 사원 b가 속한 대화방이 하나의 대화방으로 합쳐졌다는 뜻이다. 두 사원이 이미 같은 대화방에 속해 있다면 아무 일도 일어나지 않는다. 대화방은 합쳐지기만 하고 나뉘는 일은 없다.\n기록이 모두 끝난 뒤 Q개의 조회가 주어진다. 각 조회 'a b'는 사원 a와 사원 b가 처음으로 같은 대화방에 속하게 된 이벤트의 번호를 묻는다. 즉 1번부터 x번까지의 이벤트만 적용했을 때 두 사원이 같은 대화방에 속하는 가장 작은 x를 구한다. a와 b가 같은 사원이면 이벤트가 필요 없으므로 0을 출력하고, 모든 이벤트를 적용해도 같은 대화방에 속하지 못하면 -1을 출력한다. 조회끼리는 서로 영향을 주지 않으며, 조회의 개수가 많으므로 각 조회를 빠르게 처리해야 한다.

입력

첫 줄에 N, M, Q가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 200000, 1 ≤ M ≤ 200000, 1 ≤ Q ≤ 200000) 다음 M줄에 각각 이벤트 a b가 주어진다. (1 ≤ a, b ≤ N, a = b도 가능하며 이때는 아무 일도 일어나지 않는다) 다음 Q줄에 각각 조회 a b가 주어진다. (1 ≤ a, b ≤ N)

출력

각 조회의 답을 입력 순서대로 한 줄에 하나씩 출력한다.

5 4 4
1 2
3 4
2 3
1 2
1 4
1 5
2 2
3 4

3
-1
0
2

3 2 2
2 3
1 2
1 3
2 3

2
1

출처: Devin.KR 자체 제작