Đây là một bài toán tương tác. Giải pháp của bạn sẽ được đánh giá trong hai lượt chạy riêng biệt.

Trong kho lưu trữ kỹ thuật số của Kivotos, Plana đã phát hiện ra một tập hợp các bản ghi bí ẩn được gọi là Bitemporal Logs. Mỗi bản ghi bao gồm $n$ mục được đánh số từ $1$ đến $n$ tạo thành một cây có gốc. Tuy nhiên, các ràng buộc cấu trúc khác nhau tùy thuộc vào việc dòng thời gian là hồi tưởng (Logic A) hay tương lai (Logic B):

• Logic A: Cây có gốc tại mục $1$; mỗi mục $i$ khác có một mục cha $p_i$ sao cho $p_i < i$.
• Logic B: Cây có gốc tại mục $n$; mỗi mục $i$ khác có một mục cha $q_i$ sao cho $q_i > i$.

Để phân tích các đặc tính cấu trúc, Plana định nghĩa hai loại mục:

• Terminal (Điểm cuối): Một mục không đóng vai trò là cha của bất kỳ mục nào khác.
• Hub (Điểm trung tâm): Một mục đóng vai trò là cha của ít nhất một mục khác.

Plana đã quan sát thấy một sự đối xứng hoàn hảo gọi là Cộng hưởng Logic (Logical Resonance). Đặc tính này tồn tại giữa một bản ghi Logic A và một bản ghi Logic B khi và chỉ khi:

Với mọi $i$, mục $i$ là một Terminal trong Logic A $\iff$ mục $i$ là một Hub trong Logic B.

Plana đã chứng minh về mặt toán học rằng số lượng bản ghi Logic A và Logic B hợp lệ theo ràng buộc này là như nhau. Bây giờ, cô ấy giao cho bạn nhiệm vụ thiết kế một Giao thức Dịch thuật Phổ quát — một song ánh — để chuyển đổi định dạng bản ghi này sang định dạng kia.

Đánh giá tính đúng đắn

Giải pháp của bạn được thực thi hai lần cho mỗi bộ kiểm thử. Trong lượt chạy đầu tiên, giải pháp của bạn cần chuyển đổi mỗi bản ghi Logic A thành một bản ghi Logic B thỏa mãn điều kiện Cộng hưởng Logic. Trong lượt chạy thứ hai, với một bản ghi Logic B được tạo ra bởi lượt chạy đầu tiên của bạn, giải pháp của bạn cần khôi phục chính xác bản ghi Logic A ban đầu.

Dữ liệu đầu vào của lượt chạy thứ hai bao gồm các bản ghi Logic B giống như đầu ra của bạn từ lượt chạy đầu tiên, có thể theo một thứ tự khác. Đối với mỗi bản ghi Logic B đầu vào trong lượt chạy thứ hai, bạn cần xuất ra bản ghi Logic A tương ứng của nó. Giải pháp của bạn được coi là đúng nếu, với mỗi bản ghi Logic B như vậy, đầu ra của bạn chính xác là bản ghi Logic A đã tạo ra nó trong lượt chạy đầu tiên.

Một công cụ kiểm thử được cung cấp để giúp bạn phát triển và kiểm tra giải pháp của mình.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa hai số nguyên $r$ ($r \in \{1, 2\}$) và $T$ ($1 \le T \le 10^5$), đại diện cho số lượt chạy và số lượng bộ kiểm thử.

Đối với mỗi bộ kiểm thử, dòng đầu tiên chứa một số nguyên $n$ ($2 \le n \le 10^3$).

Nếu $r = 1$, dòng thứ hai chứa $n$ số nguyên $p_1, p_2, \dots, p_n$ đại diện cho bản ghi Logic A. Đảm bảo rằng $p_1 = 0$, và với $2 \le i \le n$, $1 \le p_i < i$ là mục mà mục $i$ được gắn vào. Ở đây chúng ta sử dụng $0$ để biểu thị rằng một mục không có cha (tức là gốc).

Ngược lại, nếu $r = 2$, dòng thứ hai chứa $n$ số nguyên $q_1, q_2, \dots, q_n$ đại diện cho bản ghi Logic B. Đảm bảo rằng $q_n = 0$, và với $1 \le i \le n - 1$, $i < q_i \le n$ là mục mà mục $i$ được gắn vào.

Đảm bảo rằng tổng của $n^2$ trên tất cả các bộ kiểm thử không vượt quá $10^7$.

Dữ liệu ra

Nếu $r = 1$, với mỗi bộ kiểm thử, hãy xuất ra $n$ số nguyên cách nhau bởi dấu cách, $q_1, q_2, \dots, q_n$, đại diện cho bản ghi Logic B đã chuyển đổi. Phải đảm bảo rằng $q_n = 0$, và với $1 \le i \le n - 1$, $i < q_i \le n$. Đặc tính Cộng hưởng Logic phải thỏa mãn: mục $i$ là một Terminal trong Logic A khi và chỉ khi mục $i$ là một Hub trong Logic B.

Ngược lại, nếu $r = 2$, với mỗi bộ kiểm thử, hãy xuất ra $n$ số nguyên cách nhau bởi dấu cách, $p_1, p_2, \dots, p_n$, đại diện cho bản ghi Logic A đã khôi phục.

Ví dụ

Ví dụ 1 (Lượt chạy 1)

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

Ví dụ 1 (Kết quả lượt chạy 1)

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

Ví dụ 1 (Lượt chạy 2)

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

Ví dụ 1 (Kết quả lượt chạy 2)

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

Ghi chú

Giải thích của Ví dụ 1: Một song ánh hợp lệ có thể có được thể hiện dưới đây.

Logic A và Logic B