Background

Translated from Problem C of NERC 2018.

If you want to make an array problem harder, solve it on a tree; if you want to make a tree problem harder, solve it on a cactus.

Problem Description

In the past few years, many people have proposed problems about cacti: connected undirected graphs in which each edge belongs to at most one simple cycle. More intuitively, a cactus is a generalization of a tree, where some cycles are allowed. The picture below shows an example of a cactus.

You and Chloe are playing a game on a cactus. You have a cactus, but the naughty Chloe secretly takes away one vertex $v$. You must guess $v$ within $10$ guesses. If you guess $v$, you win. If you guess another vertex $u$, Chloe will tell you a vertex $w$ such that the number of edges on the path from $w$ to $v$ is strictly smaller than that from $u$ to $v$.

Input Format

First, the first line contains two integers $n$ and $m$. Here, $n$ is the number of vertices. The edges of the graph are given by a set of paths with distinct edges, and $m$ is the number of such paths.

Next comes one line describing $m$ paths. For each path, an integer $k_i$ is given first, meaning this path goes through $k_i$ vertices, and then $k_i$ integers follow, describing the vertices on the path in order (no vertex is visited more than once). The graph in the input is a cactus.

For each guess, the judge returns a response. If it is FOUND, it means you guessed correctly; otherwise it is GO w, meaning that the number of edges on the path from $w$ to $v$ is strictly smaller than the number of edges on the path from your guessed vertex to $v$. Your program is allowed to make at most $10$ guesses for each query. If the number of guesses is $> 10$, you will fail that test.

In addition, to avoid winning by pure luck, there will be $n$ queries. After you successfully guess in one query, you immediately proceed to the next query. After finishing all $n$ queries, your program should exit.

Output Format

For each query, you need to output one integer $u$ to standard output, representing your guess, and then flush the output buffer.

You may flush the output buffer using the following statements:

• For C/C++: fflush(stdout);
• For C++: std::cout << std::flush;
• For Java: System.out.flush();
• For Python: stdout.flush();
• For Pascal: flush(output);
• For other languages, please refer to the documentation of the corresponding language.

5 2
5 1 2 3 4 5
2 1 3

FOUND
GO 4
FOUND
GO 2
FOUND
GO 1
FOUND
GO 4
GO 5
FOUND

3
3
4
3
2
3
1
3
4
5

Hint

Constraints: $1 \leq n \leq 500$, $0 \leq m \leq 500$, $1 \leq k_i \leq 500$.

Note: For easier comparison, some blank lines are added in the sample input and output for alignment, but there are no blank lines in the actual input and output.

Translated by ChatGPT 5