P13003 [GCJ 2022 Finals] Slide Parade

**Gooli** 是一家巨型公司，在一个丘陵地区拥有 $\mathbf{B}$ 栋编号为 1 到 $\mathbf{B}$ 的建筑。六年前，Gooli 修建了滑梯，允许员工从一栋建筑滑向另一栋建筑。每个滑梯只能从其出发建筑滑向目标建筑，而不能反向滑行。Gooli 的 CEO 对公司的滑梯系统非常自豪，并希望组织一场滑梯游戏。她将设计路线的任务交给了 **Melek**——Gooli 的交通主管兼解题爱好者。  CEO 对路线提出了以下要求： * 路线必须从建筑 1（她的办公室所在地）出发并最终回到建筑 1。 * 每栋建筑的访问次数必须相同。起点位于建筑 1 不算作对建筑 1 的一次访问。 * 每条滑梯必须至少被使用一次。 * 路线长度不超过 $10^6$ 步。 给定建筑和滑梯的布局，帮助 Melek 找到一条满足 CEO 所有要求的路线（如果存在）。

输入的第一行给出测试用例的数量 $\mathbf{T}$。随后是 $\mathbf{T}$ 个测试用例。每个测试用例的第一行包含两个整数 $\mathbf{B}$ 和 $\mathbf{S}$，分别表示建筑数量和滑梯数量。接下来的 $\mathbf{S}$ 行每行包含两个整数 $\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 中，另一条可接受的路线是从建筑 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 完成