これはマルチパス（2 回実行）問題です。

VegiCat と VegiDog は、$1$ から $n$ までの番号が付けられた $n$ 個の頂点と $m$ 本の辺からなる森を使ってゲームをします。森とは閉路を持たない無向グラフのことです。森は連結であるとは限りません。

第 $1$ 段階では、VegiCat が各頂点 $u$ に整数 $a_u$（$1 \le a_u \le 2n$）を割り当てます。値は重複しても構いません。

VegiCat が値の割り当てを終えた後、頂点の番号が振り直されます。$p_1, p_2, \ldots, p_n$ を $1, 2, \ldots, n$ の順列（$1$ から $n$ までの各整数がちょうど $1$ 回ずつ現れる列）とします。各 $u$ について、元々番号 $u$ だった頂点は新たに番号 $p_u$ となります。

各辺 $(u, v)$ は $(p_u, p_v)$ になります。各頂点は割り当てられた値をそのまま保持します。番号の振り直し後の頂点 $i$ における値を $b_i$ とすると、$b_{p_u} = a_u$ が成り立ちます。

第 $2$ 段階では、VegiDog は元の森や $p$ を知らされず、$n$ と $b_1, b_2, \ldots, b_n$ のみを受け取ります。彼は新しい頂点番号を用いてすべての辺を復元しなければなりません。

すべての有効な森およびすべての順列 $p$ に対して正しく機能するような、両プレイヤーの戦略を設計してください。

入力

あなたのプログラムは、最初に VegiCat として、次に VegiDog として、合計 $2$ 回実行されます。テストケースは両方の実行で同じ順序で現れます。

1 回目の実行。 最初の行には、あなたが VegiCat を担当することを示す文字列 cat が与えられます。

$2$ 行目には、テストケースの個数を表す整数 $T$（$1 \le T \le 10^4$）が与えられます。続いて各テストケースの説明が与えられます。

各テストケースの最初の行には、頂点数と辺数を表す $2$ つの整数 $n$ と $m$（$1 \le n \le 2 \cdot 10^5$, $0 \le m < n$）が与えられます。

続く $m$ 行にはそれぞれ $2$ つの整数 $u$ と $v$（$1 \le u, v \le n$, $u \ne v$）が与えられ、頂点 $u$ と $v$ を結ぶ無向辺を表します。

グラフに閉路や多重辺がないことが保証されています。

すべてのテストケースにわたる $n$ の総和は $2 \cdot 10^5$ を超えないことが保証されています。

2 回目の実行。 最初の行には、あなたが VegiDog を担当することを示す文字列 dog が与えられます。

$2$ 行目には、テストケースの個数を表す整数 $T$（$1 \le T \le 10^4$）が与えられます。続いて各テストケースの説明が与えられます。

各テストケースの最初の行には、頂点数を表す整数 $n$（$1 \le n \le 2 \cdot 10^5$）が与えられます。

$2$ 行目には、新しい頂点順での割り当てられた値を表す $n$ 個の整数 $b_1, b_2, \ldots, b_n$（$1 \le b_i \le 2n$）が与えられます。

すべてのテストケースにわたる $n$ の総和は $2 \cdot 10^5$ を超えないことが保証されています。

出力

1 回目の実行。 各テストケースについて、$n$ 個の整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 2n$）を $1$ 行に出力してください。整数 $a_i$ は頂点 $i$ に割り当てられた値です。

2 回目の実行。 各テストケースについて、最初の行に辺の本数を表す整数 $m$ を出力してください。続く $m$ 行にはそれぞれ、新しい頂点番号を用いて辺を表す $2$ つの整数 $u$ と $v$（$1 \le u, v \le n$, $u \ne v$）を出力してください。

各辺は任意の順序で $1$ 回ずつ出力してください。どちらの端点を先に出力しても構いません。$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

注記

最初のテストケースでは、森は $1$ つの頂点のみを持ち、辺はありません。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)$ として出力していますが、これは同じ無向辺を表します。

入出力例は入力および出力の形式を説明するためのものです。その出力は示されたグラフと順列に対して正しいものですが、入出力例における値の割り当てが、すべての有効な森とすべての順列に対して機能する戦略の一部であるとは限りません。