흰개미 2

판자를 갉아 먹으며 두뇌 운동을 즐기는, 사이좋은 두 마리 흰개미를 기억하는가? 바이트랜드의 울타리를 거의 다 갉아 먹은 두 흰개미는 이제 트리에 입맛을 들였다.

트리는 정점이 $n$개이고 간선이 $n-1$개인 연결된 무방향 그래프이다. 두 흰개미는 정점을 하나씩 단조롭게 먹어 치우는 데 금방 싫증이 나서, 식사를 좀 더 재미있게 만들려고 게임을 하나 고안했다. 두 흰개미는 앞으로 먹어 치울 트리의 간선에 대해 순서 $(e_1, e_2, \ldots, e_{n-1})$을 정한다. 게임은 최대 $n-1$개의 라운드 동안 진행되며, 각 라운드마다 정확히 한 마리의 흰개미가 움직인다. 두 흰개미는 번갈아 움직이는데, 첫 번째 흰개미가 1라운드, 두 번째 흰개미가 2라운드, 다시 첫 번째 흰개미가 3라운드, 이런 식으로 이어진다. $k$번째 라운드에서 차례가 된 흰개미는 간선 $e_k$의 아직 먹지 않은 끝점 하나를 골라 먹어야 한다. 만약 그 흰개미가 움직이기 전에 $e_k$의 두 끝점이 모두 이미 먹힌 상태라면, 게임은 그 즉시 끝나고 그 흰개미가 진다. $n-1$개의 라운드가 모두 지나도 게임이 끝나지 않으면 무승부이다.

두 흰개미는 모두 실수 없이 완벽하게 둔다. 승리 전략을 가진 흰개미는 가능한 한 이른 라운드에 이기고 싶어 하고, 상대 흰개미는 자신의 패배를 최대한 미루려고 한다. 주어진 트리와 흰개미들이 정한 간선의 순서에 대해, 게임이 끝나는 라운드의 번호를 구하라.

첫째 줄에 트리의 정점 개수 $n$ ($2 \le n \le 500000$)이 주어진다. 다음 $n-1$개의 줄에는 흰개미들이 정한 순서대로 트리의 간선이 주어진다. 이 중 $i$번째 줄에는 간선 $e_i$의 두 끝점을 나타내는 정수 $u_i$와 $v_i$ ($1 \le u_i, v_i \le n$)가 주어진다.

게임이 끝나는 라운드의 번호를 정수 하나로 출력한다. 게임이 무승부로 끝나면 $-1$을 출력한다.

예제의 트리에서, 첫 번째 흰개미가 1라운드에 정점 3을, 3라운드에 정점 4를 먹는다고 하자. 그러면 상대 흰개미가 2라운드에 무엇을 하든, 4라운드에는 둘 수 있는 수가 없으므로 게임은 4라운드에서 끝난다.