呢題係一道二次運行（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)$，代表同一條無向邊。

範例展示咗輸入同輸出格式。佢嘅輸出對於所展示嘅圖同排列係正確嘅。不過，範例入面嘅賦值唔保證屬於對每個合法森林同每個排列都有效嘅策略。