이 문제는 멀티 패스(multi-pass) 문제입니다.

키보토스(Kivotos)의 디지털 기록 보관소에서 플라나(Plana)는 이시점 로그(Bitemporal Logs)라고 알려진 신비로운 기록들을 발견했습니다. 각 로그는 $1$부터 $n$까지 번호가 매겨진 $n$개의 항목으로 구성되며, 하나의 루트가 있는 트리(rooted tree)를 형성합니다. 그러나 시간 흐름이 회고적(Logic A)인지 전망적(Logic B)인지에 따라 구조적 제약 조건이 다릅니다.

• Logic A: 트리의 루트는 항목 $1$입니다. 다른 모든 항목 $i$는 $p_i < i$를 만족하는 부모 $p_i$를 가집니다.
• Logic B: 트리의 루트는 항목 $n$입니다. 다른 모든 항목 $i$는 $q_i > i$를 만족하는 부모 $q_i$를 가집니다.

구조적 특성을 분석하기 위해 플라나는 두 가지 유형의 항목을 정의합니다.

• 터미널(Terminal): 다른 항목의 부모 역할을 하지 않는 항목입니다.
• 허브(Hub): 적어도 하나의 다른 항목의 부모 역할을 하는 항목입니다.

플라나는 '논리적 공명(Logical Resonance)'이라 불리는 완벽한 대칭성을 관찰했습니다. 이 속성은 Logic A 로그와 Logic B 로그 사이에 다음과 같은 경우에만 성립합니다.

모든 $i$에 대하여, 항목 $i$가 Logic A에서 터미널이다 $\iff$ 항목 $i$가 Logic B에서 허브이다.

플라나는 이 제약 조건 하에서 유효한 Logic A 로그와 Logic B 로그의 개수가 동일함을 수학적으로 증명했습니다. 이제 그녀는 한 로그 형식을 다른 형식으로 변환하는 전단사 함수(bijection)인 범용 변환 프로토콜(Universal Translation Protocol)을 설계하는 임무를 당신에게 맡겼습니다.

구현 세부사항

귀하의 솔루션은 각 테스트에서 두 번 실행됩니다. 첫 번째 실행에서 귀하의 솔루션은 각 Logic A 로그를 논리적 공명 조건을 만족하는 Logic B 로그로 변환해야 합니다. 두 번째 실행에서, 첫 번째 실행에서 생성된 Logic B 로그가 주어지면, 귀하의 솔루션은 원래의 Logic A 로그를 정확하게 복구해야 합니다.

두 번째 실행의 입력은 첫 번째 실행에서 귀하가 출력한 것과 동일한 Logic B 로그들로 구성되며, 순서는 다를 수 있습니다. 두 번째 실행의 각 입력 Logic B 로그에 대해, 그에 대응하는 Logic A 로그를 출력해야 합니다. 귀하의 솔루션은 모든 그러한 Logic B 로그에 대하여, 귀하의 출력이 첫 번째 실행에서 그것을 생성했던 원래의 Logic A 로그와 정확히 일치할 때 올바른 것으로 간주됩니다.

참고: 귀하의 솔루션은 두 번의 실행 중 어느 쪽에서든 인터랙티브 절차로 평가됩니다.

입력

첫 번째 줄에는 실행 번호 $r$ ($r \in \{1, 2\}$)와 테스트 케이스의 수 $T$ ($1 \le T \le 10^5$)가 주어집니다.

각 테스트 케이스의 첫 번째 줄에는 정수 $n$ ($2 \le n \le 10^3$)이 주어집니다.

$r = 1$인 경우, 두 번째 줄에는 Logic A 로그를 나타내는 $n$개의 정수 $p_1, p_2, \dots, p_n$이 주어집니다. $p_1 = 0$임이 보장되며, $2 \le i \le n$에 대하여 $1 \le p_i < i$는 항목 $i$가 부착된 항목입니다. 여기서 $0$은 항목이 부모를 가지지 않음(즉, 루트)을 나타냅니다.

그렇지 않고 $r = 2$인 경우, 두 번째 줄에는 Logic B 로그를 나타내는 $n$개의 정수 $q_1, q_2, \dots, q_n$이 주어집니다. $q_n = 0$임이 보장되며, $1 \le i \le n - 1$에 대하여 $i < q_i \le n$은 항목 $i$가 부착된 항목입니다.

모든 테스트 케이스에 대해 $n^2$의 합은 $10^7$을 넘지 않음이 보장됩니다.

출력

$r = 1$인 경우, 각 테스트 케이스에 대해 변환된 Logic B 로그를 나타내는 $n$개의 정수를 공백으로 구분하여 출력합니다. $q_n = 0$이어야 하며, $1 \le i \le n - 1$에 대하여 $i < q_i \le n$이어야 합니다. 논리적 공명 속성이 성립해야 합니다: 항목 $i$가 Logic A에서 터미널인 경우에만 항목 $i$가 Logic B에서 허브여야 합니다.

그렇지 않고 $r = 2$인 경우, 각 테스트 케이스에 대해 복구된 Logic A 로그를 나타내는 $n$개의 정수를 공백으로 구분하여 출력합니다.

예제

입력 1 (Pass 1)

1 3
4
0 1 1 2
4
0 1 2 1
4
0 1 1 1

출력 1 (Pass 1)

3 3 4 0
3 4 4 0
2 3 4 0

입력 2 (Pass 2)

2 3
4
2 3 4 0
4
3 3 4 0
4
3 4 4 0

출력 2 (Pass 2)

0 1 1 1
0 1 1 2
0 1 2 1

참고

예제 1에 대한 설명: 가능한 유효한 전단사 함수가 아래에 나타나 있습니다.

Logic A와 Logic B 사이의 대응 관계