즐거운 행로

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

모든 놀이기구를 정확하게 한 번 방문하는 행로(tour)를 만들려고 한다. 한 놀이기구에서 다른 놀이기구로 이동할 때 여러 도로를 지나가는 것은 지루하다. 즐거운 행로를 만들려면, 모든 놀이기구에 대해서 순서 관계를 정해서, 다음 놀이기구를 방문하는데 필요한 시간이 직전 놀이기구를 방문하는데 필요한 시간보다 길지 않게 하고 싶다. 다른 말로 하면, 0부터 N - 1까지 모든 정수가 정확하게 한 번씩 나오는 순열 P[0], P[1], …, P[N − 1]을 찾으려 하는데, 모든 0 < i < N − 1에 대해서 놀이기구 P[i]에서 놀이기구 P[i + 1]로 이동하는데 걸리는 시간이 놀이기구 P[i - 1]에서 놀이기구 P[i]로 이동하는데 걸리는 시간보다 길지 않다.

당신은 놀이기구의 전체 지도를 가지고 있지 않다. 따라서, 즐거운 행로를 만들려면 안내센터에 질문을 여러번 해야 한다. 최대 Q번 질문할 수 있고, 각각의 질문은 두 파라미터 X와 Y로 이루어지는데, 0 ≤ X, Y < N이다. 각 질문은 다음 둘 중 하나이다.  

• 놀이기구 X에서 놀이기구 Y로 이동하는데 몇 시간 걸리는가? 특히 X = Y일 때, 답은 0이다.
• 놀이기구 X와 놀이기구 Y가 주어졌을 때, 다음 조건을 만족하는 놀이기구 Z가 몇 개 있는가? 놀이기구 X에서 놀이기구 Z로 이동하려면 놀이기구 Y를 반드시 방문해야 한다. 놀이기구 Y도 포함된다. 특히 X = Y일 때, 답은 N이다.

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