즐거운 행로

자카르타에서 가장 큰 놀이동산에는 0부터 $N-1$까지 번호가 매겨진 $N$가지 놀이기구가 있습니다. 놀이기구들은 $N-1$개의 양방향 도로로 연결되어 있어서, 어떤 두 놀이기구를 골라도 이를 잇는 경로가 유일하게 하나 있습니다. 도로는 0부터 $N-2$까지 번호가 매겨져 있습니다. $i$번 도로는 놀이기구 $A[i]$와 $B[i]$를 연결하며, 이 도로를 걸어서 이동하는 데 한 시간이 걸립니다. 혼잡을 막기 위해 모든 놀이기구는 최대 3개의 도로와 연결되어 있습니다.

모든 놀이기구를 정확히 한 번씩 방문하는 행로(tour)를 만들려고 합니다. 한 놀이기구에서 다른 놀이기구로 갈 때 도로를 여러 개 지나가는 것은 지루합니다. 즐거운 행로를 만들려면 놀이기구의 방문 순서를 정해서, 다음 놀이기구로 이동하는 데 걸리는 시간이 직전 이동 시간보다 길지 않아야 합니다. 즉, 0부터 $N-1$까지 모든 정수가 정확히 한 번씩 나오는 순열 $P[0], P[1], \dots, P[N-1]$을 찾아야 하며, 모든 $0 < i < N-1$에 대해 $P[i]$에서 $P[i+1]$로 이동하는 시간이 $P[i-1]$에서 $P[i]$로 이동하는 시간보다 길지 않아야 합니다.

전체 지도는 주어지지 않습니다. 따라서 안내센터에 질문을 여러 번 해야 합니다. 최대 $Q$번까지 질문할 수 있으며, 각 질문은 $0 \le X, Y < N$인 두 파라미터 $X$와 $Y$로 이루어집니다. 각 질문은 다음 두 가지 중 하나입니다.

• 놀이기구 $X$에서 놀이기구 $Y$로 이동하는 데 몇 시간이 걸립니까? $X = Y$이면 답은 0입니다.
• 놀이기구 $X$와 $Y$가 주어졌을 때, 놀이기구 $X$에서 놀이기구 $Z$로 이동하려면 반드시 놀이기구 $Y$를 거쳐야 하는 놀이기구 $Z$는 몇 개입니까? $Y$도 포함합니다. $X = Y$이면 답은 $N$입니다.

• $2 \le N \le 100000$
• $Q = 400000$
• 어떤 두 놀이기구든 도로를 통해 서로 이동할 수 있습니다.
• 각 놀이기구는 최대 3개의 도로와 연결되어 있습니다. (즉, 최대 3개 도로의 끝점입니다.)