这是一道通信题。你的程序在每个测试点中将被运行两次。

第一次运行

给定一个包含 $n$ 个节点和 $m$ 条边的连通无向图。同时给定一个长度为 $k$ 的特殊序列，包含节点编号 $p_1, \dots, p_k$，满足图中存在一个简单环 $p_1 - p_2 - \dots - p_k - p_1$。你必须为图中的每条边指定一个方向。

第二次运行

在第二次运行之前，评测系统会打乱所有节点的编号，并打乱你在第一次运行中输出的边的顺序。你将得到打乱后生成的有向图。你的任务是找到第一次运行中的环在这个排列下的映射：你必须输出环上所有节点的新编号，可以从任意节点开始，但必须保持它们的顺序。

输入格式

第一行包含一个整数 $op$（$op \in \{1, 2\}$），表示运行的次数。

第二行包含两个整数 $n$ 和 $m$（$3 \le n \le m \le 5 \cdot 10^5$），表示给定的图的节点数和边数。如果 $op = 1$，图是无向的；如果 $op = 2$，图是有向的。图是连通的，且没有自环或重边。

接下来的 $m$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$），表示图中的边。如果图是有向的，则方向为 $u \to v$。

如果 $op = 1$，下一行包含一个整数 $k$（$3 \le k \le n$），表示环的长度。接下来的一行包含 $k$ 个整数 $p_1, \dots, p_k$，按顺序表示环上的节点。这个环存在于上面给出的图中：即存在边 $(p_1, p_2), (p_2, p_3), \dots, (p_k, p_1)$。

输出格式

如果 $op = 1$，你必须为每条边指定一个方向。输出 $m$ 行，每行包含两个整数 $u$ 和 $v$，表示一条有向边 $u \to v$。你可以以任意顺序输出这些边，但必须将输入中的每条边恰好输出一次（使用其两个可能方向中的一个）。

如果 $op = 2$，你必须输出第一次运行中的环上的节点，使用打乱后的新编号，并保持环的顺序。

请注意，你的输出应保留给定的环的方向。例如，假设第一次运行中给定的序列是 1 2 3 4，在打乱节点编号后，它变成了 3 1 4 2。那么输出 3 1 4 2 和 4 2 3 1 都将被接受，因为它们表示同一个有向环的循环移位。另一方面，输出 2 4 1 3 将被拒绝，因为它对应于相反的方向。

样例

输入 1

1
5 6
1 2
2 5
2 3
3 4
3 5
4 5
4
2 3 4 5

输出 1

2 3
3 4
5 2
3 5
4 5
1 2

输入 2

2
5 6
3 5
2 1
4 5
5 2
2 4
1 4

输出 2

1 4 5 2

说明

样例展示了某个特定解法在样例上的两次运行。在第一次运行之后，节点 $1, 2, 3, 4, 5$ 的编号被排列成了 $3, 5, 2, 1, 4$。在评测你的程序时，排列方式可能会有所不同。