Dies ist ein Multi-Pass-Problem (Zwei-Phasen-Problem).

VegiCat und VegiDog spielen ein Spiel mit einem Wald aus $n$ Knoten, die von $1$ bis $n$ nummeriert sind, und $m$ Kanten. Ein Wald ist ein ungerichteter Graph ohne Kreise. Er ist nicht notwendigerweise zusammenhängend.

In der ersten Phase weist VegiCat jedem Knoten $u$ eine ganze Zahl $a_u$ ($1 \le a_u \le 2n$) zu. Die Werte dürfen sich wiederholen.

Nachdem VegiCat die Zuweisung der Werte abgeschlossen hat, werden die Knoten neu nummeriert. Sei $p_1, p_2, \ldots, p_n$ eine Permutation von $1, 2, \ldots, n$, in der jede ganze Zahl von $1$ bis $n$ genau einmal vorkommt. Für jedes $u$ erhält der ursprünglich mit $u$ nummerierte Knoten nun die Nummer $p_u$.

Jede Kante $(u, v)$ wird zu $(p_u, p_v)$. Jeder Knoten behält seinen zugewiesenen Wert. Sei $b_i$ der Wert am Knoten $i$ nach der Umnummerierung. Dann gilt $b_{p_u} = a_u$.

In der zweiten Phase erhält VegiDog nur $n$ sowie $b_1, b_2, \ldots, b_n$, ohne den ursprünglichen Wald oder $p$ zu kennen. Er muss alle Kanten unter Verwendung der neuen Knotennummern rekonstruieren.

Entwirf Strategien für beide Spieler, die für jeden gültigen Wald und jede Permutation $p$ funktionieren.

Eingabe

Dein Programm wird zweimal ausgeführt: zuerst als VegiCat, dann als VegiDog. Die Testfälle erscheinen in beiden Durchläufen in derselben Reihenfolge.

Erster Durchlauf. Die erste Zeile enthält die Zeichenkette cat, was angibt, dass du VegiCat spielst.

Die zweite Zeile enthält eine ganze Zahl $T$ ($1 \le T \le 10^4$), die Anzahl der Testfälle. Es folgt die Beschreibung der Testfälle.

Die erste Zeile jedes Testfalls enthält zwei ganze Zahlen $n$ und $m$ ($1 \le n \le 2 \cdot 10^5$, $0 \le m < n$), die Anzahl der Knoten und Kanten.

Jede der nächsten $m$ Zeilen enthält zwei ganze Zahlen $u$ und $v$ ($1 \le u, v \le n$, $u \ne v$), die eine ungerichtete Kante zwischen den Knoten $u$ und $v$ beschreiben.

Es wird garantiert, dass der Graph keine Kreise oder Mehrfachkanten enthält.

Es wird garantiert, dass die Summe von $n$ über alle Testfälle $2 \cdot 10^5$ nicht überschreitet.

Zweiter Durchlauf. Die erste Zeile enthält die Zeichenkette dog, was angibt, dass du VegiDog spielst.

Die zweite Zeile enthält eine ganze Zahl $T$ ($1 \le T \le 10^4$), die Anzahl der Testfälle. Es folgt die Beschreibung der Testfälle.

Die erste Zeile jedes Testfalls enthält eine ganze Zahl $n$ ($1 \le n \le 2 \cdot 10^5$), die Anzahl der Knoten.

Die zweite Zeile enthält $n$ ganze Zahlen $b_1, b_2, \ldots, b_n$ ($1 \le b_i \le 2n$), die zugewiesenen Werte in der neuen Knotenreihenfolge.

Es wird garantiert, dass die Summe von $n$ über alle Testfälle $2 \cdot 10^5$ nicht überschreitet.

Ausgabe

Erster Durchlauf. Gib für jeden Testfall $n$ ganze Zahlen $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 2n$) in einer Zeile aus. Die ganze Zahl $a_i$ ist der dem Knoten $i$ zugewiesene Wert.

Zweiter Durchlauf. Gib für jeden Testfall in der ersten Zeile eine ganze Zahl $m$ aus, die Anzahl der Kanten. Jede der nächsten $m$ Zeilen muss zwei ganze Zahlen $u$ und $v$ ($1 \le u, v \le n$, $u \ne v$) enthalten, die eine Kante unter Verwendung der neuen Knotennummern beschreiben.

Gib jede Kante einmal in beliebiger Reihenfolge aus. Welcher Endpunkt zuerst genannt wird, spielt keine Rolle. Falls $m = 0$ ist, gib nur $0$ aus.

Beispiele

Eingabe 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

Ausgabe 1

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

Eingabe 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

Ausgabe 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

Hinweis

Im ersten Testfall hat der Wald einen Knoten und keine Kanten. VegiCat weist dem Knoten den Wert $1$ zu, und VegiDog gibt $0$ aus.

Im letzten Testfall lautet die Permutation $p = [5, 3, 6, 4, 2, 9, 1, 8, 7, 10]$.

VegiCat weist $a_7 = 16$ zu. Da $p_7 = 1$ gilt, erhält VegiDog $b_1 = 16$.

Die ursprüngliche Kante $(3, 7)$ wird zu $(p_3, p_7) = (6, 1)$.

Die ursprüngliche Kante $(4, 10)$ wird zu $(p_4, p_{10}) = (4, 10)$. Das Beispiel gibt diese Kante als $(10, 4)$ aus, was dieselbe ungerichtete Kante darstellt.

Das Beispiel veranschaulicht das Eingabe- und Ausgabeformat. Seine Ausgaben sind für die gezeigten Graphen und Permutationen korrekt. Es wird jedoch nicht garantiert, dass die Zuweisungen im Beispiel Teil einer Strategie sind, die für jeden gültigen Wald und jede Permutation funktioniert.