프랙털 트리

프랙털 트리 $F_i$를 다음과 같이 정의한다. 먼저 정점이 2개 이상인 루트 트리 $F_0$이 주어진다. $i \ge 1$인 $F_i$는 재귀적으로 만든다. $F_{i-1}$에서 잎인 정점의 집합을 $S$라 하자. $S$에 속하는 각 정점 $v$를 $F_0$의 복사본으로 바꾸고, 이때 $v$가 그 복사본의 루트가 된다.

정수 $k$가 주어질 때 트리 $F_k$에서 깊이 우선 탐색을 한다. 각 정점에서는 가장 왼쪽 자식의 서브트리를 모두 방문한 다음 두 번째 자식의 서브트리를 방문하고, 이런 식으로 왼쪽부터 차례로 모든 자식의 서브트리를 방문한다. 방문한 순서대로 정점에 1부터 시작하는 정수 번호를 붙인다. 아래 그림이 그 예이다.

(a) 트리 $F_0$	(b) 트리 $F_1$	(c) $F_1$의 깊이 우선 탐색 번호

정점 두 개로 이루어진 질의가 주어진다. 각 질의마다 두 정점 사이의 거리를 구하라. 거리는 두 정점을 잇는 유일한 단순 경로의 간선 개수이다.

첫째 줄에 $F_0$의 정점 개수 $n$이 주어진다 ($2 \le n \le 100\,000$). 정점 번호는 0부터 $n-1$까지이며 0번이 루트이다. 둘째 줄에 $n-1$개의 정수 $p_1, \dots, p_{n-1}$이 주어진다. $1 \le i \le n-1$에서 $p_i$는 $F_0$에서 정점 $i$의 부모이고 $p_i < i$이다. 한 정점의 자식은 번호가 작을수록 왼쪽에 온다.

셋째 줄에 정수 $k$가 주어진다 ($0 \le k < 2^{30}$). 넷째 줄에 질의 개수 $q$가 주어진다 ($1 \le q \le 100\,000$). 다음 $q$개의 줄에는 질의가 한 줄에 하나씩 주어진다. 각 질의는 서로 다른 두 정수 $a$와 $b$로 이루어지고, 둘 다 $F_k$에 있는 정점의 번호이다. $a$와 $b$는 항상 유효한 번호, 즉 1 이상 $F_k$의 정점 개수 이하이며, 둘 다 $2^{30}$ 이하이다.

각 질의 $(a, b)$마다 $F_k$에서 번호가 $a$인 정점과 번호가 $b$인 정점 사이의 거리를, 입력에 주어진 순서대로 한 줄에 하나씩 출력한다.