← 返回题目列表

AtCoder · abc305_f

I. 地下城探索

中文机器翻译题面 查看原题

分数: 525 点

问题陈述

这是一个 交互问题 (您的程序和判断程序通过标准输入和输出进行交互)。

有一个简单的连通无向图 N 顶点和 M 边缘。 顶点用整数编号 1 to 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 or OK,立即终止程序。

注释

  • 在每个输出中,在末尾插入换行符并刷新标准输出。否则,判决可能是 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 既然你已经到达顶点 4 内 8(=2\times4) 移动, OK 已通过。

如果您收到后立即终止程序,将被判定为正确 OK.