이 문제는 투스텝(multi-pass) 문제입니다.

VegiCat과 VegiDog은 $1$부터 $n$까지 번호가 매겨진 $n$개의 정점과 $m$개의 간선으로 이루어진 포레스트(forest)를 가지고 게임을 합니다. 포레스트는 사이클이 없는 무방향 그래프입니다. 포레스트는 연결 그래프일 필요가 없습니다.

첫 번째 단계에서 VegiCat은 각 정점 $u$에 정수 $a_u$ ($1 \le a_u \le 2n$)를 배정합니다. 값들은 중복될 수 있습니다.

VegiCat이 값 배정을 마치면 정점들의 번호가 다시 매겨집니다. $p_1, p_2, \ldots, p_n$을 $1$부터 $n$까지의 각 정수가 정확히 한 번씩 등장하는 $1, 2, \ldots, n$의 순열이라고 합시다. 각 $u$에 대해, 원래 번호가 $u$였던 정점은 이제 번호가 $p_u$가 됩니다.

각 간선 $(u, v)$는 $(p_u, p_v)$가 됩니다. 각 정점은 배정된 값을 그대로 유지합니다. 번호가 다시 매겨진 후 정점 $i$에 있는 값을 $b_i$라고 하면, $b_{p_u} = a_u$입니다.

두 번째 단계에서 VegiDog은 원래의 포레스트나 순열 $p$ 없이 오직 $n$과 $b_1, b_2, \ldots, b_n$만 받습니다. 그는 새로운 정점 번호를 사용하여 모든 간선을 복원해야 합니다.

모든 유효한 포레스트와 모든 순열 $p$에 대해 작동하는 두 플레이어의 전략을 설계하세요.

입력

당신의 프로그램은 두 번 실행됩니다: 첫 번째는 VegiCat으로, 두 번째는 VegiDog으로 실행됩니다. 테스트 케이스는 두 실행 모두에서 동일한 순서로 주어집니다.

첫 번째 실행. 첫 번째 줄에는 당신이 VegiCat 역할을 함을 나타내는 문자열 cat이 주어집니다.

두 번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $T$ ($1 \le T \le 10^4$)가 주어집니다. 이어서 테스트 케이스의 설명이 주어집니다.

각 테스트 케이스의 첫 번째 줄에는 정점의 수와 간선의 수를 나타내는 두 정수 $n$과 $m$ ($1 \le n \le 2 \cdot 10^5$, $0 \le m < n$)이 주어집니다.

다음 $m$개의 줄에는 각각 정점 $u$와 $v$ 사이의 무방향 간선을 나타내는 두 정수 $u$와 $v$ ($1 \le u, v \le n$, $u \ne v$)가 주어집니다.

그래프에 사이클이나 중복 간선이 없음이 보장됩니다.

모든 테스트 케이스에서 $n$의 합이 $2 \cdot 10^5$을 넘지 않음이 보장됩니다.

두 번째 실행. 첫 번째 줄에는 당신이 VegiDog 역할을 함을 나타내는 문자열 dog가 주어집니다.

두 번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $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)$로 출력하며, 이는 동일한 무방향 간선을 나타냅니다.

예제는 입력과 출력 형식을 보여줍니다. 예제의 출력은 제시된 그래프와 순열에 대해 올바른 결과입니다. 하지만 예제의 값 배정이 모든 유효한 포레스트와 모든 순열에 대해 작동하는 전략의 일부임이 보장되지는 않습니다.