Đây là bài toán chạy hai lượt (multi-pass).

VegiCat và VegiDog chơi một trò chơi với một rừng gồm $n$ đỉnh, được đánh số từ $1$ đến $n$, và $m$ cạnh. Rừng là một đồ thị vô hướng không có chu trình. Nó không nhất thiết phải liên thông.

Ở giai đoạn đầu tiên, VegiCat gán một số nguyên $a_u$ ($1 \le a_u \le 2n$) cho mỗi đỉnh $u$. Các giá trị có thể trùng nhau.

Sau khi VegiCat hoàn tất việc gán giá trị, các đỉnh được đánh số lại. Gọi $p_1, p_2, \ldots, p_n$ là một hoán vị của $1, 2, \ldots, n$, trong đó mỗi số nguyên từ $1$ đến $n$ xuất hiện đúng một lần. Với mỗi $u$, đỉnh ban đầu có số hiệu $u$ nay được đánh số là $p_u$.

Mỗi cạnh $(u, v)$ trở thành $(p_u, p_v)$. Mỗi đỉnh giữ nguyên giá trị đã được gán. Gọi $b_i$ là giá trị tại đỉnh $i$ sau khi đánh số lại. Khi đó $b_{p_u} = a_u$.

Ở giai đoạn thứ hai, VegiDog chỉ nhận được $n$ và $b_1, b_2, \ldots, b_n$, mà không biết rừng ban đầu hay hoán vị $p$. Cậu ấy phải khôi phục tất cả các cạnh bằng cách sử dụng số hiệu đỉnh mới.

Hãy thiết kế chiến lược cho cả hai người chơi sao cho hoạt động đúng với mọi rừng hợp lệ và mọi hoán vị $p$.

Dữ liệu vào

Chương trình của bạn sẽ chạy hai lần: lần đầu trong vai VegiCat, lần sau trong vai VegiDog. Các bộ dữ liệu xuất hiện theo cùng một thứ tự ở cả hai lần chạy.

Lần chạy thứ nhất. Dòng đầu tiên chứa xâu cat, cho biết bạn đóng vai VegiCat.

Dòng thứ hai chứa một số nguyên $T$ ($1 \le T \le 10^4$), số lượng bộ dữ liệu. Mô tả của các bộ dữ liệu theo sau.

Dòng đầu tiên của mỗi bộ dữ liệu chứa hai số nguyên $n$ và $m$ ($1 \le n \le 2 \cdot 10^5$, $0 \le m < n$), số lượng đỉnh và cạnh.

Mỗi dòng trong $m$ dòng tiếp theo chứa hai số nguyên $u$ và $v$ ($1 \le u, v \le n$, $u \ne v$), mô tả một cạnh vô hướng giữa hai đỉnh $u$ và $v$.

Dữ liệu đảm bảo rằng đồ thị không có chu trình hoặc cạnh bội.

Dữ liệu đảm bảo rằng tổng của $n$ trên tất cả các bộ dữ liệu không vượt quá $2 \cdot 10^5$.

Lần chạy thứ hai. Dòng đầu tiên chứa xâu dog, cho biết bạn đóng vai VegiDog.

Dòng thứ hai chứa một số nguyên $T$ ($1 \le T \le 10^4$), số lượng bộ dữ liệu. Mô tả của các bộ dữ liệu theo sau.

Dòng đầu tiên của mỗi bộ dữ liệu chứa một số nguyên $n$ ($1 \le n \le 2 \cdot 10^5$), số lượng đỉnh.

Dòng thứ hai chứa $n$ số nguyên $b_1, b_2, \ldots, b_n$ ($1 \le b_i \le 2n$), các giá trị đã gán theo thứ tự đỉnh mới.

Dữ liệu đảm bảo rằng tổng của $n$ trên tất cả các bộ dữ liệu không vượt quá $2 \cdot 10^5$.

Dữ liệu ra

Lần chạy thứ nhất. Với mỗi bộ dữ liệu, hãy in ra $n$ số nguyên $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 2n$) trên một dòng. Số nguyên $a_i$ là giá trị được gán cho đỉnh $i$.

Lần chạy thứ hai. Với mỗi bộ dữ liệu, hãy in ra một số nguyên $m$ trên dòng đầu tiên, là số lượng cạnh. Mỗi dòng trong $m$ dòng tiếp theo phải chứa hai số nguyên $u$ và $v$ ($1 \le u, v \le n$, $u \ne v$), mô tả một cạnh bằng số hiệu đỉnh mới.

In ra mỗi cạnh một lần theo bất kỳ thứ tự nào. Đầu mút nào đứng trước cũng được. Nếu $m = 0$, chỉ cần in ra $0$.

Ví dụ

Dữ liệu vào 1

cat
4
1 0
4 3
1 2
4 3
2 3
7 2
6 4
7 1
10 7
10 9
7 9
10 5
4 8
3 7
4 10
1 2

Dữ liệu ra 1

1
2 5 8 5
11 11 4 11 3 7 2
10 13 12 5 3 2 16 6 19 3

Dữ liệu vào 2

dog
4
1
1
4
5 2 5 8
7
11 7 2 11 11 3 4
10
16 3 13 5 10 12 19 6 2 3

Dữ liệu ra 2

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

Ghi chú

Trong bộ dữ liệu đầu tiên, rừng có một đỉnh và không có cạnh nào. VegiCat gán giá trị $1$ cho đỉnh đó, và VegiDog in ra $0$.

Trong bộ dữ liệu cuối cùng, hoán vị là $p = [5, 3, 6, 4, 2, 9, 1, 8, 7, 10]$.

VegiCat gán $a_7 = 16$. Vì $p_7 = 1$, VegiDog nhận được $b_1 = 16$.

Cạnh ban đầu $(3, 7)$ trở thành $(p_3, p_7) = (6, 1)$.

Cạnh ban đầu $(4, 10)$ trở thành $(p_4, p_{10}) = (4, 10)$. Ví dụ in cạnh này là $(10, 4)$, biểu diễn cùng một cạnh vô hướng.

Ví dụ minh họa định dạng dữ liệu vào và dữ liệu ra. Kết quả của nó đúng với các đồ thị và hoán vị được trình bày. Tuy nhiên, các phép gán trong ví dụ không được đảm bảo là một phần của chiến lược hoạt động đúng cho mọi rừng hợp lệ và mọi hoán vị.