Little Cyan Fish는 University of Cup에서 자료구조 마스터 클래스를 가르치고 있습니다. 전통적인 자료구조 문제에서는 여러분에게 수많은 쿼리를 주고 고정된 자료구조에서 복잡한 식을 평가하라고 요구했을 것입니다. 하지만 2026년에 누가 그런 일을 하고 싶겠습니까? Little Cyan Fish는 다른 것을 원합니다. 그는 여러분에게 직접 자료구조를 설계해 보라고 합니다.

여러분의 과제는 루트가 있는 이진 트리 $T$를 구성하는 것입니다.

• $T$의 모든 내부 정점(internal vertex)*은 정확히 두 개의 자식을 가집니다.
• $T$는 $1$부터 $m$까지 라벨이 붙은 정확히 $m$개의 잎(leaf)을 가집니다.

그림 1: $m=6$일 때의 유효한 $T$. 모든 내부 정점은 정확히 두 개의 자식을 가지며, 잎들은 $1, \dots, m$의 라벨을 임의의 순서로 가집니다. 여기서 깊이는 5입니다.

잎 라벨의 임의의 집합 $S$에 대하여, $T$에서의 비용을 $T$의 내부 정점 $v$ 중 그 서브트리가 다음 두 조건을 모두 만족하는 것의 개수로 정의합니다.

• $S$에 속하는 라벨을 가진 잎이 적어도 하나 존재함.
• $S$에 속하지 않는 라벨을 가진 잎이 적어도 하나 존재함.

Little Cyan Fish는 여러분에게 루트가 있는 두 개의 트리 $T_1$과 $T_2$를 줍니다. 두 트리 모두 정점은 $1$부터 $n$까지 라벨이 붙어 있으며, 각 트리의 루트는 정점 $1$입니다. 또한 그는 $m$개의 순서쌍 $(x_i, y_i)$를 주는데, 여기서 $x_i$는 $T_1$의 정점이고 $y_i$는 $T_2$의 정점입니다. $T$에서 라벨이 $\ell$인 잎은 값 $x_\ell$ 및 $y_\ell$과 연관되어 있습니다.

루트가 있는 트리 $T$와 정점 $x$에 대하여, $\text{path}(T, x)$를 $x$에서 $T$의 루트까지의 경로에 있는 정점들의 집합(양 끝점 포함)이라고 정의합니다.

Little Cyan Fish는 여러분이 다음을 알기를 원합니다. $T_1$의 각 정점 $u$에 대하여 $Q_1(u) = \{\ell \mid x_\ell \in \text{path}(T_1, u)\}$로 정의합니다. 마찬가지로 $T_2$의 각 정점 $u$에 대하여 $Q_2(u) = \{\ell \mid y_\ell \in \text{path}(T_2, u)\}$로 정의합니다. 각 $Q_i(u)$는 $T$의 잎 라벨들의 집합입니다.

*잎은 자식이 없는 정점이며, 내부 정점은 잎이 아닌 정점입니다.

그림 2: 집합 $\text{path}(T_i, x)$는 $x$에서 루트까지의 유일한 경로에 있는 모든 정점을 포함합니다(양 끝점 포함).

Little Cyan Fish가 확인하는 집합은 모든 $1 \le u \le n$에 대한 $Q_1(u)$와 $Q_2(u)$입니다. Little Cyan Fish는 여러분의 자료구조가 다음 두 요구사항을 모두 만족하면 이를 수락합니다.

• $T$의 모든 정점의 깊이는 최대 $100$입니다(루트의 깊이는 $1$).
• 확인하는 모든 $2n$개의 집합 중에서 최대 비용은 최대 $16\,666$입니다.

Little Cyan Fish에게 여러분이 진정한 자료구조의 마스터임을 보여주세요!

입력

첫 번째 줄에는 두 정수 $n$과 $m$ ($1 \le n, m \le 10^6$)이 주어집니다.

다음 줄에는 트리 $T_1$을 설명하는 $n-1$개의 정수 $p_2, p_3, \dots, p_n$ ($1 \le p_i < i$)이 주어집니다. 정수 $p_i$는 $T_1$에서 정점 $i$의 부모입니다.

다음 줄에는 트리 $T_2$를 설명하는 $n-1$개의 정수 $p'_2, p'_3, \dots, p'_n$ ($1 \le p'_i < i$)이 주어집니다. 정수 $p'_i$는 $T_2$에서 정점 $i$의 부모입니다.

다음 $m$개의 줄은 순서쌍을 설명합니다. 이 중 $i$번째 줄에는 두 정수 $x_i$와 $y_i$ ($1 \le x_i, y_i \le n$)가 주어집니다.

출력

여러분이 구성한 이진 트리 $T$를 설명하는 정수들의 수열을 한 줄에 출력합니다.

• 라벨이 $i$인 잎은 정수 $i$로 설명됩니다.
• 내부 정점은 정수 $0$으로 시작하며, 그 뒤에 왼쪽 서브트리에 대한 설명, 오른쪽 서브트리에 대한 설명이 차례로 옵니다.

이 인코딩 방식에서 $1$부터 $m$까지의 모든 정수는 정확히 한 번 나타나야 하며, $0$이 나타날 때마다 하나의 내부 정점을 나타냅니다.

예를 들어, 수열 0 1 0 2 3은 루트의 왼쪽 자식이 잎 $1$이고 오른쪽 자식이 내부 정점인 트리를 설명합니다. 그 내부 정점은 잎 $2$와 $3$을 자식으로 가집니다.

예제

예제 입력 1

1 1
1 1

예제 출력 1

1

예제 입력 2

3 3
1 1
1 2
1 1
2 2
3 3

예제 출력 2

0 1 0 2 3

예제 입력 3

5 8
1 2 3 4
1 1 1 1
1 1
2 1
3 2
4 2
5 3
5 5
1 5
3 4

예제 출력 3

0 0 1 0 0 3 8 0 2 7 0 4 0 5 6

참고

예제 1의 설명: 이 이진 트리는 라벨이 $1$인 단 하나의 잎을 가집니다. 깊이는 $1$이며, 가능한 모든 쿼리의 비용은 $0$입니다.