這是一道二次執行（multi-pass）題。

VegiCat 與 VegiDog 在一個有 $n$ 個頂點（編號從 $1$ 到 $n$）和 $m$ 條邊的森林上玩遊戲。森林是一個沒有環的無向圖。它不一定連通。

在第一階段，VegiCat 為每個頂點 $u$ 指派一個整數 $a_u$（$1 \le a_u \le 2n$）。這些數值可以重複。

在 VegiCat 完成數值指派後，頂點會被重新編號。令 $p_1, p_2, \ldots, p_n$ 為 $1, 2, \ldots, n$ 的一個排列，其中從 $1$ 到 $n$ 的每個整數恰好出現一次。對於每個 $u$，原本編號為 $u$ 的頂點現在編號為 $p_u$。

每條邊 $(u, v)$ 變為 $(p_u, p_v)$。每個頂點保留其被指派的數值。令重新編號後頂點 $i$ 處的數值為 $b_i$，則 $b_{p_u} = a_u$。

在第二階段，VegiDog 只會收到 $n$ 與 $b_1, b_2, \ldots, b_n$，而不知道原始森林或排列 $p$。他必須使用新的頂點編號還原出所有的邊。

請為兩位玩家設計策略，使其對每一個合法的森林與每一個排列 $p$ 皆有效。

輸入格式

你的程式將執行兩次：第一次扮演 VegiCat，第二次扮演 VegiDog。在兩次執行中，各組測試資料以相同的順序出現。

第一次執行。 第一行包含字串 cat，代表你扮演 VegiCat。

第二行包含一個整數 $T$（$1 \le T \le 10^4$），代表測試資料的組數。接下來是各組測試資料的描述。

每組測試資料的第一行包含兩個整數 $n$ 與 $m$（$1 \le n \le 2 \cdot 10^5$，$0 \le m < n$），分別代表頂點數與邊數。

接下來的 $m$ 行，每行包含兩個整數 $u$ 與 $v$（$1 \le u, v \le n$，$u \ne v$），描述頂點 $u$ 與 $v$ 之間的一條無向邊。

保證圖中沒有環或重邊。

保證所有測試資料中 $n$ 的總和不會超過 $2 \cdot 10^5$。

第二次執行。 第一行包含字串 dog，代表你扮演 VegiDog。

第二行包含一個整數 $T$（$1 \le T \le 10^4$），代表測試資料的組數。接下來是各組測試資料的描述。

每組測試資料的第一行包含一個整數 $n$（$1 \le n \le 2 \cdot 10^5$），代表頂點數。

第二行包含 $n$ 個整數 $b_1, b_2, \ldots, b_n$（$1 \le b_i \le 2n$），代表按新頂點順序排列的指派數值。

保證所有測試資料中 $n$ 的總和不會超過 $2 \cdot 10^5$。

輸出格式

第一次執行。 對於每組測試資料，在一行中輸出 $n$ 個整數 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 2n$）。整數 $a_i$ 是指派給頂點 $i$ 的數值。

第二次執行。 對於每組測試資料，於第一行輸出一個整數 $m$，代表邊數。接下來的 $m$ 行，每行必須包含兩個整數 $u$ 與 $v$（$1 \le u, v \le n$，$u \ne v$），使用新的頂點編號描述一條邊。

每條邊輸出一次，順序不拘。任一端點皆可先輸出。若 $m = 0$，則僅輸出 $0$。

範例

輸入格式 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

輸出格式 1

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

輸入格式 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

輸出格式 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

說明

在第一組測試資料中，森林只有一個頂點且沒有邊。VegiCat 將數值 $1$ 指派給該頂點，而 VegiDog 輸出 $0$。

在最後一組測試資料中，排列為 $p = [5, 3, 6, 4, 2, 9, 1, 8, 7, 10]$。

VegiCat 指派 $a_7 = 16$。由於 $p_7 = 1$，VegiDog 收到 $b_1 = 16$。

原始邊 $(3, 7)$ 變為 $(p_3, p_7) = (6, 1)$。

原始邊 $(4, 10)$ 變為 $(p_4, p_{10}) = (4, 10)$。範例將這條邊輸出為 $(10, 4)$，代表同一條無向邊。

範例展示了輸入與輸出格式。其輸出對於所展示的圖與排列是正確的。然而，範例中的數值指派並不保證屬於對每個合法森林與每個排列都有效的策略。