Це двопрохідна задача (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)$, що подає те саме неорієнтоване ребро.

Приклад ілюструє формати вхідних і вихідних даних. Його відповіді є правильними для показаних графів і перестановок. Проте не гарантується, що присвоєння в прикладі є частиною стратегії, яка працює для кожного коректного лісу та кожної перестановки.