AT_abc305_f [ABC305F] Dungeon Explore

[problemUrl]: https://atcoder.jp/contests/abc305/tasks/abc305_f 本题是一个**交互式问题**（你的程序需要与评测程序通过标准输入输出进行交互）。 有一个包含 $N$ 个顶点和 $M$ 条边的连通且简单的无向图。顶点编号为 $1$ 到 $N$ 的整数。 你一开始位于顶点 $1$。你可以最多进行 $2N$ 次移动，每次可以移动到相邻的顶点，目标是到达顶点 $N$。 但是，起初你并不知道图中所有的边。你只能知道当前所在顶点与其相邻的顶点的信息。

首先，你需要从标准输入读取图的顶点数 $N$ 和边数 $M$。 > $N$ $M$ 接下来，你可以与评测程序进行最多 $2N$ 次交互操作。 每次操作开始时，你会从标准输入获得当前所在顶点的相邻顶点的信息，格式如下： > $k$ $v_1$ $v_2$ $\ldots$ $v_k$ 其中，$v_i\ (1\leq i\leq k)$ 是 $1$ 到 $N$ 之间的整数，满足 $v_1 < v_2 < \cdots < v_k$。 你需要从 $v_1, v_2, \ldots, v_k$ 中选择一个顶点，并将其编号输出到标准输出： > $v_i$ 这样你就会移动到顶点 $v_i$。 如果你的移动次数超过 $2N$ 次，或者输出不合法，评测机会向标准输入输出 `-1`。 如果你移动到的顶点是 $N$，评测机会向标准输入输出 `OK`，并结束交互。 当你收到 `-1` 或 `OK` 时，请立即终止你的程序。

每次移动时，输出你选择要移动到的顶点编号，并换行，随后刷新标准输出。

## 限制条件 - $2 \leq N \leq 100$ - $N-1 \leq M \leq \dfrac{N(N-1)}{2}$ - 图是连通且简单的 - 所有输入均为整数 ## 注意事项 - **每次输出后请在末尾加上换行，并刷新标准输出。如果不这样做，可能会导致评测结果为 TLE。** - **如果在交互过程中输出不合法，或者程序中途退出，评测结果不确定。** - 到达顶点 $N$ 后请立即终止程序，否则评测结果不确定。 - **本题的评测是自适应的。也就是说，在不与限制条件和你之前的输出矛盾的前提下，图的结构可能会发生变化。** ## 输入输出样例 以下是 $N=4, M=5$ 时的输入输出示例。此时图的结构如下图所示。  | 输入 | 输出 | 说明 | | :--- | :--- | :--- | | `4 5` | | 给出 $N$ 和 $M$。 | | `2 2 3` | | 一开始你在顶点 $1$，给出与顶点 $1$ 相邻的顶点。 | | | `3` | 选择移动到顶点 $v_2=3$。 | | `3 1 2 4` | | 给出顶点 $3$ 的相邻顶点。 | | | `2` | 选择移动到顶点 $v_2=2$。 | | `3 1 3 4` | | 给出顶点 $2$ 的相邻顶点。 | | | `4` | 选择移动到顶点 $v_3=4$。 | | `OK` | | 在 $8(=2\times4)$ 次以内到达顶点 $4$，收到 `OK`。| | `OK` | | 收到 `OK` 后立即终止程序即可判定为正确。 | 由 ChatGPT 4.1 翻译