F - Dungeon Explore Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 525 点

問題文

この問題は インタラクティブな問題（あなたが作成したプログラムとジャッジプログラムが標準入出力を介して対話を行う形式の問題）です。

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) を 1 つ選んで以下の形式で標準出力へ出力してください。

v _ i

この操作をすることで、あなたは頂点 v _ i へ移動します。

移動回数が 2N 回を上回ったり、不正な出力を行った場合、ジャッジは標準入力に -1 を送ります。

移動する先の頂点が頂点 N である場合、ジャッジは標準入力に OK を送り、終了します。

-1 もしくは OK を受け取った場合、ただちにあなたのプログラムを終了させてください。

注意点

  • 出力を行うたびに、末尾に改行を入れて標準出力を flush してください。そうしなかった場合、ジャッジ結果が 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 を受け取ったあと、ただちにプログラムを終了することで正解と判定されます。

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.
  • The verdict will be indeterminate if the program prints invalid output or quits prematurely in the middle of the interaction.
  • Terminate the program immediately after reaching vertex N. Otherwise, the verdict will be indeterminate.
  • The judge for this problem is adaptive. This means that the graph may change without contradicting the constraints or previous outputs.

Sample Interaction

In the following sample interaction, we have N=4, M=5, and the graph in the figure below.

Input Output Description
4 5 N and M are given.
2 2 3 You start at vertex 1. The vertices adjacent to vertex 1 are given.
3 You choose to go to vertex v _ 2=3.
3 1 2 4 The vertices adjacent to vertex 3 are given.
2 You choose to go to vertex v _ 2=2.
3 1 3 4 The vertices adjacent to vertex 2 are given.
4 You choose to go to vertex v _ 3=4.
OK Since you have reached vertex 4 within 8(=2\times4) moves, OK is passed.

You will be judged as correct if you immediately terminate the program after receiving OK.