Description

Gooli 是一家巨型公司，在一个丘陵地区拥有 $\mathbf{B}$ 栋编号为 1 到 $\mathbf{B}$ 的建筑。六年前，Gooli 修建了滑梯，允许员工从一栋建筑滑向另一栋建筑。每个滑梯只能从其出发建筑滑向目标建筑，而不能反向滑行。Gooli 的 CEO 对公司的滑梯系统非常自豪，并希望组织一场滑梯游戏。她将设计路线的任务交给了 Melek——Gooli 的交通主管兼解题爱好者。

CEO 对路线提出了以下要求：

• 路线必须从建筑 1（她的办公室所在地）出发并最终回到建筑 1。
• 每栋建筑的访问次数必须相同。起点位于建筑 1 不算作对建筑 1 的一次访问。
• 每条滑梯必须至少被使用一次。
• 路线长度不超过 $10^6$ 步。

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

Input Format

输入的第一行给出测试用例的数量 $\mathbf{T}$。随后是 $\mathbf{T}$ 个测试用例。每个测试用例的第一行包含两个整数 $\mathbf{B}$ 和 $\mathbf{S}$，分别表示建筑数量和滑梯数量。接下来的 $\mathbf{S}$ 行每行包含两个整数 $\mathbf{U}_i$ 和 $\mathbf{V}_i$，表示第 $i$ 条滑梯从建筑 $\mathbf{U}_i$ 通向建筑 $\mathbf{V}_i$。

Output Format

对于每个测试用例，输出一行 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 恰好多出现一次。

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

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

Hint

样例解释

在样例 #1 中，另一条可接受的路线是从建筑 1 滑到建筑 2 再返回，总步数为 2 步。

在样例 #2 中，没有滑梯通向建筑 1，因此不存在有效路线。

在样例 #3 中，样例输出展示的路线使每栋建筑被访问两次。

样例 #4 如下图所示：

样例 #5 是题目描述中图示的案例。在样例输出的路线中，从 2 到 3 和从 4 到 1 的滑梯被使用了两次，其余滑梯各使用一次。

限制条件

• $1 \leq \mathbf{T} \leq 100$。
• $1 \leq \mathbf{U}_i \leq \mathbf{B}$，对所有 $i$。
• $1 \leq \mathbf{V}_i \leq \mathbf{B}$，对所有 $i$。
• $\mathbf{U}_i \neq \mathbf{V}_i$，对所有 $i$。
• $(\mathbf{U}_i, \mathbf{V}_i) \neq (\mathbf{U}_j, \mathbf{V}_j)$，对所有 $i \neq j$。

测试集 1（11 分，可见判定）

• 时间限制：10 秒。
• $2 \leq \mathbf{B} \leq 10$。
• $2 \leq \mathbf{S} \leq 10$。

测试集 2（24 分，隐藏判定）

• 时间限制：20 秒。
• $2 \leq \mathbf{B} \leq 200$。
• $2 \leq \mathbf{S} \leq 5000$。

翻译由 DeepSeek V3 完成