시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 50 25 21 47.727%

문제

알고리즘에 푹 빠진 동관이가 트리에 심취한 나머지 트리에서 외심을 정의하려 한다. 트리란, 모든 정점이 연결되어 있으면서 사이클이 존재하지 않는 그래프이다. 하지만 동관이는 트리에서 외심을 정의하기 위해서는 "트리에서 두 정점 사이의 거리"도 정의해야 한다는 사실을 깨달았다!

트리에서 두 정점 사이의 거리는 한 정점에서 다른 정점으로 가기 위해 거쳐야 하는 최소한의 간선의 개수로 정의된다. 이 때 트리의 세 정점에 대해, 트리의 외심은 세 정점으로부터 거리가 같으면서, 그 거리를 최소로 하는 정점이 존재한다면 해당 정점으로 정의된다. 수학적으로 트리의 세 정점에 대해 외심이 존재한다면, 유일하다는 것을 보일 수 있다.

자명하게도, 외심을 정의하는 3개의 정점이 달라지면 같은 트리라 해도 외심이 달라진다. 동관이는 다양한 외심들을 찾아보고 싶지만 코딩에 귀찮음을 겪고 있다......동관이를 위해 여러분들이 대신 코드를 짜주도록 하자.

입력

첫 번째 줄에 정점의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 이 트리는 1번 정점, 2번 정점, ..., N번 정점으로 구성된다.

두 번째 줄부터 N번째 줄까지, 트리의 간선 정보를 의미하는 두 자연수 X, Y가 공백으로 구분되어 주어진다. 이는 X번 정점과 Y번 정점이 연결되어있음을 의미한다. (1 ≤ X, YN, X Y)

주어지는 연결관계는 트리를 구성한다.

N+1 번째 줄에는 쿼리의 개수 Q가 주어진다. (1 ≤ Q ≤ 100,000)

다음 Q개의 줄에 걸쳐, 외심을 정의하기 위한 세 개의 정점 번호를 뜻하는 세 자연수 A, B, C가 공백으로 구분되어 주어진다. (1 ≤ A, B, CN

출력

Q개의 줄에 걸쳐 각 쿼리마다 입력으로 주어진 세 정점에 대해 트리의 외심이 존재하면 외심의 정점 번호를, 존재하지 않으면 -1을 출력한다.

예제 입력 1

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

예제 출력 1

1
-1

예제 입력 2

2
1 2
2
1 1 2
2 2 2

예제 출력 2

-1
2

예제 입력 3

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

예제 출력 3

3