Это двухпроходная задача (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)$. Каждая вершина сохраняет присвоенное ей значение. Пусть $b_i$ — значение в вершине $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)$, что задаёт то же самое неориентированное ребро.

Пример иллюстрирует форматы входных и выходных данных. Выходные данные в нём корректны для приведённых графов и перестановок. Однако не гарантируется, что присвоенные в примере значения являются частью стратегии, работающей для любого корректного леса и любой перестановки.