AT_abc305_f [ABC305F] Dungeon Explore

题目描述

本题是一个交互式问题（你的程序需要与评测程序通过标准输入输出进行交互）。

有一个包含 $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$ 时的输入输出示例。此时图的结构如下图所示。

由 ChatGPT 4.1 翻译