103055: [Atcoder]ABC305 F - Dungeon Explore
Description
Score : $525$ points
Problem Statement
This is an interactive problem (where your program and the judge program interact through Standard Input and Output).
There is a simple connected undirected graph with $N$ vertices and $M$ edges. The vertices are numbered with integers from $1$ to $N$.
Initially, you are at vertex $1$. Repeat moving to an adjacent vertex at most $2N$ times to reach vertex $N$.
Here, you do not initially know all edges of the graph, but you will be informed of the vertices adjacent to the vertex you are at.
Constraints
- $2\leq N\leq100$
- $N-1\leq M\leq\dfrac{N(N-1)}2$
- The graph is simple and connected.
- All input values are integers.
Input and Output
First, receive the number of vertices $N$ and the number of edges $M$ in the graph from Standard Input:
$N$ $M$
Next, you get to repeat the operation described in the problem statement at most $2N$ times against the judge.
At the beginning of each operation, the vertices adjacent to the vertex you are currently at are given from Standard Input in the following format:
$k$ $v _ 1$ $v _ 2$ $\ldots$ $v _ k$
Here, $v _ i\ (1\leq i\leq k)$ are integers between $1$ and $N$ such that $v _ 1\lt v _ 2\lt\cdots\lt v _ k$.
Choose one of $v _ i\ (1\leq i\leq k)$ and print it to Standard Output in the following format:
$v _ i$
After this operation, you will be at vertex $v _ i$.
If you perform more than $2N$ operations or print invalid output, the judge will send -1 to Standard Input.
If the destination of a move is vertex $N$, the judge will send OK to Standard Input and terminate.
When receiving -1 or OK, immediately terminate the program.
Notes
- In each output, insert a newline at the end and flush Standard Output. Otherwise, the verdict may be TLE
Input
题意翻译
**本题为交互题。** 给定一张 $N$ 个点（编号为 $1 \sim N$），$M$ 条边的无向连通图，保证无重边无自环，但是起初这张图的所有边是未知的。 起初你在 $1$ 号点。在交互开始或者每次完成操作的时候，交互库会告诉你从当前点出发的边连向哪些点。在此之后，你需要进行一次操作：走到其中的一个点。 你需要执行不超过 $2N$ 次操作到达点 $N$。 以下为交互流程： 1. 首先读入一行两个正整数 $N,M$。 2. 接下来： - 如果操作次数大于 $2N$ 或者刚刚执行了不合法的操作，交互库会返回 `-1` 到标准输入中。你需要立即结束程序。 - 否则，如果刚刚执行的操作使得你到达了点 $N$，那么交互库会返回 `OK` 到标准输入中并结束程序。 - 否则，交互库会返回 $K+1$ 个非负整数到标准输入中：第一个是 $K$，接下来是 $K$ 个互不相同的正整数 $v_1,v_2,\cdots,v_k$，代表从当前点出发的边连向的点的集合。 3. 你需要从其中选择一个 $v_i$ 输出，此后返回到第 2 步直到程序结束。Output
问题描述
这是一个交互式问题（你的程序和裁判程序通过标准输入和输出进行交互）。
有一个简单的包含 $N$ 个顶点和 $M$ 条边的无向图。顶点用从1到$N$的整数进行编号。
最初，你位于顶点1。重复最多移动到相邻顶点$2N$次以到达顶点$N$。
在这里，你最初不知道图中所有的边，但你会被通知你当前所在的顶点相邻的顶点。
约束
- $2\leq N\leq100$
- $N-1\leq M\leq\dfrac{N(N-1)}2$
- 图是简单且连通的。
- 所有的输入值都是整数。
输入和输出
首先，从标准输入接收图中的顶点数$N$和边数$M$：
$N$ $M$
接下来，你最多可以对裁判进行$2N$次问题描述中的操作。
在每次操作的开始，你当前所在的顶点相邻的顶点从标准输入给出以下格式：
$k$ $v _ 1$ $v _ 2$ $\ldots$ $v _ k$
这里，$v _ i\ (1\leq i\leq k)$ 是介于1和$N$之间的整数，使得$v _ 1\lt v _ 2\lt\cdots\lt v _ k$。
选择一个$v _ i\ (1\leq i\leq k)$ 并将其以以下格式打印到标准输出：
$v _ i$
执行此操作后，你将位于顶点$v _ i$。
如果你进行了超过$2N$次操作或打印了无效输出，裁判将向标准输入发送-1。
如果移动的目的地是顶点$N$，裁判将向标准输入发送OK并终止。
接收到-1或OK时，立即终止程序。
注释
- 在每个输出后插入一个换行符并刷新标准输出。否则，判决可能会是