입자 가속기

시간 제한5초메모리 제한2048 MB

요약

방 N개와 통로 N-1개로 이루어진 트리가 주어지고, 서로 다른 방 번호 v를 인자로 하는 generate 함수를 Q번 호출합니다. generate가 무엇을 반환해야 하는지는 본문에 없습니다.

문제

KOI 연구소는 입자 가속기를 이용해 연구를 진행하고 있다. 이 입자 가속기는 $N$ 개의 방과, 방들을 잇는 $N-1$ 개의 양방향 통로로 이루어져 있다. 서로 다른 두 방은 통로만 사용해 오갈 수 있으므로, 입자 가속기는 트리 구조를 이룬다.

방에는 $0$ 부터 $N-1$ 까지 서로 다른 번호가 붙어 있고, 통로에는 $0$ 부터 $N-2$ 까지 서로 다른 번호가 붙어 있다. 모든 $0 \le i \le N-2$ 에 대해 $i$ 번 통로는 $A[i]$ 번 방과 $B[i]$ 번 방을 잇는다.

$2 \le Q \le N \le 200\,000$
입자 가속기는 트리 구조를 이룬다.
모든 $i$ 에 대해 $0 \le A[i], B[i] \le N-1$ 이고 $A[i] \neq B[i]$ 이다 ( $0 \le i \le N - 2$ ).
모든 generate 함수 호출에 대해 $0 \le v \le N-1$ 이며, $v$ 는 서로 다른 값이다.