트리와 쿼리 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 ≤ N ≤ 200,000)

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

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

다음 Q개의 줄에 두 정수 x, y가 주어진다. (1 ≤ x, y ≤ n, x ≠ y)

정수 x, y 에서 u, v 를 얻어내기 위해서는 다음과 같이 하면 된다. $last$ 를 직전 쿼리의 정답이라고 하자. (만약 첫 쿼리일 경우 $last = 0$), 이 때 $(u, v) = (((x + N - 1 + last) \text{ mod } N) + 1, ((y + N - 1 + last) \text{ mod } N) + 1)$ 이 성립한다.

Q개의 줄에 걸쳐 문제의 정답을 출력하라.