Gooli 是一家大型公司，在丘陵地区拥有 $\mathbf{B}$ 座建筑，编号为 $1$ 到 $\mathbf{B}$。六年前，Gooli 建造了滑梯，允许员工从一座建筑前往另一座建筑。 每条滑梯允许任何人从滑梯的起点建筑前往终点建筑，但不能反向通行。 Gooli 的首席执行官对这些滑梯感到非常自豪，并希望组织一场穿过这些滑梯的游行。 她指派 Gooli 交通部门负责人、问题解决爱好者 Melek 来设计游行路线。

她对游行路线有一些要求：

• 路线必须从她的办公室所在的建筑 $1$ 出发，并回到建筑 $1$ 结束。
• 路线必须访问每座建筑相同次数。在路线开始时位于建筑 $1$ 不计作一次访问。
• 路线必须至少使用每条滑梯一次。
• 路线的步数最多为 $10^6$ 步。

给定建筑和滑梯的布局，请帮助 Melek 找到一条满足首席执行官所有要求的路线（如果存在的话）。

输入格式

输入的第一行包含测试用例的数量 $\mathbf{T}$。接下来是 $\mathbf{T}$ 个测试用例。 每个测试用例的第一行包含两个整数 $\mathbf{B}$ 和 $\mathbf{S}$，分别代表建筑的数量和滑梯的数量。 随后有 $\mathbf{S}$ 行，其中第 $i$ 行包含两个整数 $\mathbf{U_i}$ 和 $\mathbf{V_i}$，表示第 $i$ 条滑梯从建筑 $\mathbf{U_i}$ 通往建筑 $\mathbf{V_i}$。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始）。如果不存在满足所有要求的路线，则 $y$ 必须为 IMPOSSIBLE。如果存在，则 $y$ 必须是一个介于 $\mathbf{S}+1$ 和 $10^6+1$（含）之间的整数，代表你所展示的路线长度。在这种情况下，输出另一行，包含 $y$ 个整数 $z_1\ z_2\ \dots\ z_y$，其中 $z_j$ 是你提议的路线中的第 $j$ 座建筑。注意 $z_1 = z_y = 1$，且除了建筑 $1$ 之外，每座建筑在 $z_j$ 中出现的次数必须相同；建筑 $1$ 出现的次数必须恰好多一次。

数据范围

• $1 \le \mathbf{T} \le 100$
• $1 \le \mathbf{U_i} \le \mathbf{B}$，对于所有 $i$
• $1 \le \mathbf{V_i} \le \mathbf{B}$，对于所有 $i$
• $\mathbf{U_i} \ne \mathbf{V_i}$，对于所有 $i$
• $(\mathbf{U_i}, \mathbf{V_i}) \neq (\mathbf{U_j}, \mathbf{V_j})$，对于所有 $i \neq j$

测试集 1

• $2 \le \mathbf{B} \le 10$
• $2 \le \mathbf{S} \le 10$

测试集 2

• $2 \le \mathbf{B} \le 200$
• $2 \le \mathbf{S} \le 5000$

样例

输入 1

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

输出 1

Case #1: 7
1 2 1 2 1 2 1
Case #2: IMPOSSIBLE
Case #3: 7
1 2 3 1 3 2 1
Case #4: IMPOSSIBLE
Case #5: 9
1 4 1 2 3 2 3 4 1

说明

在样例 1 中，另一种可接受的游行路线是从建筑 $1$ 到建筑 $2$ 再返回，总共 $2$ 步。

在样例 2 中，没有通往建筑 $1$ 的滑梯，因此不存在有效的游行路线。

在样例 3 中，样例输出展示的游行路线经过了每座建筑两次。

样例 4 如下图所示。

样例 5 即题目描述中展示的例子。在样例输出的游行路线中，从 $2$ 到 $3$ 以及从 $4$ 到 $1$ 的滑梯被使用了两次，而其余滑梯各只使用了一次。