트리의 외심

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

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

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

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

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

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

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

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

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