To jest zadanie dwuprzebiegowe (multi-pass).

VegiCat i VegiDog grają w grę na lesie złożonym z $n$ wierzchołków, ponumerowanych od $1$ do $n$, oraz $m$ krawędzi. Las to graf nieskierowany bez cykli. Nie musi on być spójny.

W pierwszym etapie VegiCat przypisuje każdemu wierzchołkowi $u$ liczbę całkowitą $a_u$ ($1 \le a_u \le 2n$). Wartości mogą się powtarzać.

Gdy VegiCat zakończy przypisywanie wartości, wierzchołki zostają przenumerowane. Niech $p_1, p_2, \ldots, p_n$ będzie permutacją liczb $1, 2, \ldots, n$, w której każda liczba całkowita od $1$ do $n$ występuje dokładnie raz. Dla każdego $u$, wierzchołek pierwotnie oznaczony numerem $u$ otrzymuje teraz numer $p_u$.

Każda krawędź $(u, v)$ staje się krawędzią $(p_u, p_v)$. Każdy wierzchołek zachowuje przypisaną mu wartość. Niech $b_i$ oznacza wartość w wierzchołku $i$ po przenumerowaniu. Wówczas $b_{p_u} = a_u$.

W drugim etapie VegiDog otrzymuje jedynie $n$ oraz ciąg $b_1, b_2, \ldots, b_n$, bez pierwotnego lasu ani permutacji $p$. Musi on odtworzyć wszystkie krawędzie, używając nowych numerów wierzchołków.

Zaprojektuj strategie dla obu graczy, które działają poprawnie dla każdego poprawnego lasu i każdej permutacji $p$.

Wejście

Twój program zostanie uruchomiony dwukrotnie: najpierw jako VegiCat, a następnie jako VegiDog. Przypadki testowe pojawiają się w tej samej kolejności w obu uruchomieniach.

Pierwsze uruchomienie. Pierwszy wiersz zawiera napis cat, oznaczający, że grasz jako VegiCat.

Drugi wiersz zawiera liczbę całkowitą $T$ ($1 \le T \le 10^4$), oznaczającą liczbę przypadków testowych. Poniżej znajdują się opisy poszczególnych przypadków testowych.

Pierwszy wiersz każdego przypadku testowego zawiera dwie liczby całkowite $n$ oraz $m$ ($1 \le n \le 2 \cdot 10^5$, $0 \le m < n$), oznaczające liczbę wierzchołków i krawędzi.

Każdy z kolejnych $m$ wierszy zawiera dwie liczby całkowite $u$ oraz $v$ ($1 \le u, v \le n$, $u \ne v$), opisujące krawędź nieskierowaną pomiędzy wierzchołkami $u$ i $v$.

Zagwarantowane jest, że graf nie zawiera cykli ani krawędzi wielokrotnych.

Zagwarantowane jest, że suma wartości $n$ po wszystkich przypadkach testowych nie przekracza $2 \cdot 10^5$.

Drugie uruchomienie. Pierwszy wiersz zawiera napis dog, oznaczający, że grasz jako VegiDog.

Drugi wiersz zawiera liczbę całkowitą $T$ ($1 \le T \le 10^4$), oznaczającą liczbę przypadków testowych. Poniżej znajdują się opisy poszczególnych przypadków testowych.

Pierwszy wiersz każdego przypadku testowego zawiera liczbę całkowitą $n$ ($1 \le n \le 2 \cdot 10^5$), oznaczającą liczbę wierzchołków.

Drugi wiersz zawiera $n$ liczb całkowitych $b_1, b_2, \ldots, b_n$ ($1 \le b_i \le 2n$), oznaczających przypisane wartości w nowej kolejności wierzchołków.

Zagwarantowane jest, że suma wartości $n$ po wszystkich przypadkach testowych nie przekracza $2 \cdot 10^5$.

Wyjście

Pierwsze uruchomienie. Dla każdego przypadku testowego wypisz w jednym wierszu $n$ liczb całkowitych $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 2n$). Liczba całkowita $a_i$ to wartość przypisana wierzchołkowi $i$.

Drugie uruchomienie. Dla każdego przypadku testowego w pierwszym wierszu wypisz liczbę całkowitą $m$, oznaczającą liczbę krawędzi. Każdy z kolejnych $m$ wierszy musi zawierać dwie liczby całkowite $u$ oraz $v$ ($1 \le u, v \le n$, $u \ne v$), opisujące krawędź za pomocą nowych numerów wierzchołków.

Wypisz każdą krawędź dokładnie raz, w dowolnej kolejności. Dowolny z jej końców może wystąpić jako pierwszy. Jeśli $m = 0$, wypisz tylko $0$.

Przykład

Wejście 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

Wyjście 1

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

Wejście 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

Wyjście 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

Uwagi

W pierwszym przypadku testowym las ma jeden wierzchołek i nie ma żadnych krawędzi. VegiCat przypisuje temu wierzchołkowi wartość $1$, a VegiDog wypisuje $0$.

W ostatnim przypadku testowym permutacja to $p = [5, 3, 6, 4, 2, 9, 1, 8, 7, 10]$.

VegiCat przypisuje $a_7 = 16$. Ponieważ $p_7 = 1$, VegiDog otrzymuje $b_1 = 16$.

Pierwotna krawędź $(3, 7)$ staje się krawędzią $(p_3, p_7) = (6, 1)$.

Pierwotna krawędź $(4, 10)$ staje się krawędzią $(p_4, p_{10}) = (4, 10)$. W przykładzie krawędź ta jest wypisana jako $(10, 4)$, co reprezentuje tę samą krawędź nieskierowaną.

Przykład ilustruje format wejścia i wyjścia. Jego wyjścia są poprawne dla pokazanych grafów i permutacji. Nie ma jednak gwarancji, że przypisania z przykładu są częścią strategii działającej dla każdego poprawnego lasu i każdej permutacji.