Questo è un problema multi-pass (a due esecuzioni).

VegiCat e VegiDog giocano a un gioco con una foresta di $n$ vertici, numerati da $1$ a $n$, e $m$ archi. Una foresta è un grafo non orientato privo di cicli. Non è necessariamente connessa.

Nella prima fase, VegiCat assegna un intero $a_u$ ($1 \le a_u \le 2n$) a ciascun vertice $u$. I valori possono ripetersi.

Dopo che VegiCat ha terminato di assegnare i valori, i vertici vengono rinumerati. Sia $p_1, p_2, \ldots, p_n$ una permutazione di $1, 2, \ldots, n$, in cui ogni intero da $1$ a $n$ compare esattamente una volta. Per ciascun $u$, il vertice originariamente numerato $u$ ora riceve il numero $p_u$.

Ogni arco $(u, v)$ diventa $(p_u, p_v)$. Ciascun vertice mantiene il valore che gli è stato assegnato. Sia $b_i$ il valore nel vertice $i$ dopo la rinumerazione. Allora $b_{p_u} = a_u$.

Nella seconda fase, VegiDog riceve solamente $n$ e $b_1, b_2, \ldots, b_n$, senza conoscere la foresta originale o $p$. Deve ricostruire tutti gli archi utilizzando i nuovi numeri dei vertici.

Progetta strategie per entrambi i giocatori che funzionino per ogni foresta valida e per ogni permutazione $p$.

Input

Il tuo programma verrà eseguito due volte: prima nel ruolo di VegiCat, poi nel ruolo di VegiDog. I casi di test compaiono nello stesso ordine in entrambe le esecuzioni.

Prima esecuzione. La prima riga contiene la stringa cat, che indica che giochi come VegiCat.

La seconda riga contiene un intero $T$ ($1 \le T \le 10^4$), il numero di casi di test. Segue la descrizione dei casi di test.

La prima riga di ciascun caso di test contiene due interi $n$ e $m$ ($1 \le n \le 2 \cdot 10^5$, $0 \le m < n$), il numero di vertici e di archi.

Ciascuna delle successive $m$ righe contiene due interi $u$ e $v$ ($1 \le u, v \le n$, $u \ne v$), che descrivono un arco non orientato tra i vertici $u$ e $v$.

È garantito che il grafo non contenga cicli né archi multipli.

È garantito che la somma di $n$ su tutti i casi di test non supera $2 \cdot 10^5$.

Seconda esecuzione. La prima riga contiene la stringa dog, che indica che giochi come VegiDog.

La seconda riga contiene un intero $T$ ($1 \le T \le 10^4$), il numero di casi di test. Segue la descrizione dei casi di test.

La prima riga di ciascun caso di test contiene un intero $n$ ($1 \le n \le 2 \cdot 10^5$), il numero di vertici.

La seconda riga contiene $n$ interi $b_1, b_2, \ldots, b_n$ ($1 \le b_i \le 2n$), i valori assegnati secondo il nuovo ordine dei vertici.

È garantito che la somma di $n$ su tutti i casi di test non supera $2 \cdot 10^5$.

Output

Prima esecuzione. Per ciascun caso di test, stampa $n$ interi $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 2n$) su una riga. L'intero $a_i$ è il valore assegnato al vertice $i$.

Seconda esecuzione. Per ciascun caso di test, stampa sulla prima riga un intero $m$, il numero di archi. Ciascuna delle successive $m$ righe deve contenere due interi $u$ e $v$ ($1 \le u, v \le n$, $u \ne v$), che descrivono un arco utilizzando i nuovi numeri dei vertici.

Stampa ciascun arco una sola volta, in qualsiasi ordine. Uno qualsiasi dei due estremi può essere stampato per primo. Se $m = 0$, stampa solo $0$.

Esempi

Input 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

Output 1

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

Input 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

Output 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

Note

Nel primo caso di test, la foresta ha un solo vertice e nessun arco. VegiCat assegna il valore $1$ al vertice, e VegiDog stampa $0$.

Nell'ultimo caso di test, la permutazione è $p = [5, 3, 6, 4, 2, 9, 1, 8, 7, 10]$.

VegiCat assegna $a_7 = 16$. Poiché $p_7 = 1$, VegiDog riceve $b_1 = 16$.

L'arco originale $(3, 7)$ diventa $(p_3, p_7) = (6, 1)$.

L'arco originale $(4, 10)$ diventa $(p_4, p_{10}) = (4, 10)$. L'esempio stampa questo arco come $(10, 4)$, che rappresenta lo stesso arco non orientato.

L'esempio illustra i formati di input e di output. I suoi output sono corretti per i grafi e le permutazioni mostrati. Tuttavia, non è garantito che le assegnazioni dell'esempio facciano parte di una strategia valida per ogni foresta valida e ogni permutazione.