这是一道通信（二次运行）题。
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)$。每个顶点保留其被分配的数值。设重新编号后顶点 $i$ 处的数值为 $b_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)$，表示同一条无向边。
样例展示了输入和输出格式。其输出对于所展示的图和排列是正确的。但是，样例中的赋值并不保证属于对每个合法森林和每个排列都有效的策略。