트리와 K번째 지름

오늘 알고리즘 과목의 중간고사를 보는 메시는 시험장에 들어서자마자 감독관에게 가중치가 없는 트리를 받았다. 트리의 각 정점은 거리 1인 간선으로 이웃과 연결되어 있으며, 임의의 두 정점 사이의 최단 경로는 하나뿐이다. i번 정점에 쓰인 정수를 $J_i$라고 할 때, $J_i = i$이다. 이어서 이메이미 교수가 들어와 칠판에 다음 문제를 적었다.

"트리의 s번 정점에서 출발하여 e번 정점에 도착하는 최단 경로를 $10^9 \times J_s + J_e$라는 수로 인코딩한다. 주어진 트리에서 가장 긴 최단 경로(트리의 지름) 중 인코딩된 수가 K번째로 작은 것을 구하여라. 인코딩된 수가 다르면 서로 다른 지름으로 취급한다."

첫 줄에 트리의 정점 수 $N$과 쿼리의 수 $Q$가 공백으로 구분되어 주어진다.

둘째 줄부터 $N-1$개의 줄에 걸쳐 간선이 연결하는 두 정점의 번호 $a$, $b$가 공백으로 구분되어 주어진다.

$N+1$번째 줄에는 $K$가 주어진다. 처음 주어진 트리에서 K번째로 작은 지름을 구해야 한다는 뜻이다.

$N+2$번째 줄부터 $Q$개의 줄에 걸쳐 쿼리 $u$, $v$, $L$이 공백으로 구분되어 주어진다. $J_u$와 $J_v$를 서로 바꾼 뒤 L번째로 작은 지름을 구해야 한다는 뜻이다.

지름을 구하라는 쿼리가 들어올 때마다 인코딩된 수를 한 줄에 하나씩 출력한다. 조건을 만족하는 지름이 없으면 -1을 출력한다.

• $2 \le N \le 250{,}000$
• $0 \le Q \le 250{,}000$
• $1 \le K \le 10^{18}$
• 모든 쿼리에서 $1 \le u, v \le N$이고, $1 \le L \le 10^{18}$이다.