트리와 쿼리 22

$N$개의 정점으로 이루어진 트리가 있다. 정점은 $1$번부터 $N$번까지 번호가 매겨져 있다. $i$번 정점에는 숫자 $a_i$가 쓰여 있다. 초기에는 $a_i = i$로 설정되어 있다.

$f(u, v)$를 $u$에서 $v$로 가는 경로 $p_0 = u, p_1, p_2, \ldots, p_t = v$ 위에 있는 숫자 $a_{p_0}, a_{p_1}, \ldots, a_{p_t}$를 순서대로 늘어 쓴 수열이라고 하자.

다음과 같은 쿼리를 수행해야 한다.

• u v: $a_u$와 $a_v$를 바꾼다. 그 후, $f(u, w)$를 최대화하는 $w$를 출력한다. 수열은 사전순으로 비교한다.

쿼리는 온라인으로 주어진다. 자세한 내용은 입력 부분을 참고하면 된다.

첫째 줄에 트리의 크기 $N$이 주어진다. ($2 \le N \le 200,000$)

다음 $N-1$개의 줄에 두 정수 $u$, $v$가 주어진다. 두 정점 $u$, $v$를 잇는 간선이 존재함을 뜻한다. ($1 \le u, v \le N$)

다음 줄에 쿼리의 개수 $Q$가 주어진다. ($1 \le Q \le 200,000$)

다음 $Q$개의 줄에 두 정수 $x$, $y$가 주어진다. ($1 \le x, y \le N$, $x \ne y$)

$last$를 직전 쿼리의 정답이라고 하자. 첫 쿼리라면 $last = 0$이다. 이때 $u$와 $v$는 다음과 같이 구한다.

$(u, v) = \left(((x + N - 1 + last) \text{ mod } N) + 1, ((y + N - 1 + last) \text{ mod } N) + 1\right)$

$Q$개의 줄에 걸쳐 각 쿼리의 정답을 출력한다.