CF1340E.Nastya and Bees

Unfortunately, a mistake was found in the proof of the author's solution to this problem. Currently, we don't know the absolutely correct solution. However, you can solve this task, but if your solution passes all the tests, it is not guaranteed to be correct. If your solution has passed all the tests and you are sure that it is correct, you can write to one of the contest authors about it.

Surely you all read the book "Alice in Wonderland". In this task, Nastya got to the country of Three strange Bees. The bees are strange because their honeycombs are pentagonal. Nastya got there illegally, so she wants bees not to catch her. Help the bees punish the intruder!

This is an interactive problem.

A beehive is a connected undirected graph where bees and Nastya can move along the edges. A graph satisfies two properties:

• The degree of any of its vertex is no more than $3$.
• For each edge, there exists a cycle of length not greater than $5$ passing through this edge.

There are three bees and Nastya. You play for bees. Firstly, you choose the vertices where you put the bees. Then Nastya chooses another vertex in which she will initially appear. One move is first moving the bees, then Nastya, in turn:

1. For each of your bees, you can either move each one along some edge from the vertex they are currently staying or leave it in place.
2. Then Nastya will necessarily move along some edge of the graph from the vertex she is currently staying/.

You win if at least one of the bees and Nastya are in the same vertex at any time of the game.

If this situation does not occur after $n$ moves, then you lose.

Several bees can be in the same vertex.

不幸的是，该题作者解法的证明中被发现存在一处错误。目前我们尚不清楚绝对正确的解法。然而，你仍然可以尝试解决本题；但即使你的解法通过了所有测试用例，也不能保证其正确性。如果你的解法已通过全部测试，并且你确信它是正确的，欢迎联系本次比赛的任意一位出题人。

想必大家都读过《爱丽丝梦游仙境》这本书。在本题中，娜斯佳来到了“三只奇异蜜蜂之国”。这些蜜蜂之所以奇异，是因为它们的蜂巢呈五边形结构。娜斯佳是非法闯入此地的，因此她希望不被蜜蜂发现。请帮助蜜蜂们惩罚这位入侵者！

这是一道交互式问题。

蜂巢是一个连通的无向图，蜜蜂与娜斯佳均可沿图中的边移动。该图满足如下两条性质：

• 图中任意顶点的度数至多为 $3$；
• 对于图中的每一条边，均存在一个长度不超过 $5$ 的环，且该环经过这条边。

图中有三只蜜蜂和娜斯佳。你扮演蜜蜂一方。首先，你需要选定三个顶点，将三只蜜蜂分别放置于其上。随后，娜斯佳将选择图中另一个顶点作为她的初始位置。游戏按轮进行，每轮包含以下两个步骤（先蜜蜂行动，后娜斯佳行动）：

1. 对于每一只蜜蜂，你可以选择将其沿当前所在顶点的一条邻边移动，或令其保持不动；
2. 接着，娜斯佳必须沿当前所在顶点的一条邻边移动。

若在游戏过程中的任意时刻，至少有一只蜜蜂与娜斯佳位于同一顶点，则你获胜。

若经过 $n$ 轮后仍未出现上述情况，则你失败。

允许多只蜜蜂同时位于同一顶点。

The first line contains two integers $n$ $(4 \leq n \leq 5000)$ and $m$ $(n \leq m \leq 3n)$ — the number of vertices and edges in the graph.

Each of the next $m$ lines contains two integers $v$ and $u$ $(1 \leq v, u \leq n)$, which mean that there is an edge between the vertices $v$ and $u$. It is guaranteed that the graph is connected, does not contain loops that the degree of any vertex does not exceed $3$ and a cycle of length no more than $5$ passes through each edge. Note that the graph may contain multiple edges.

第一行包含两个整数 $n$（$4 \leq n \leq 5000$）和 $m$（$n \leq m \leq 3n$），分别表示图中的顶点数和边数。

接下来的 $m$ 行，每行包含两个整数 $v$ 和 $u$（$1 \leq v, u \leq n$），表示顶点 $v$ 与顶点 $u$ 之间存在一条边。保证该图是连通的，不含自环，且任意顶点的度数不超过 $3$；此外，每条边都位于某个长度不超过 $5$ 的环中。注意：图中可能包含重边。

Let Nastya be a green chip, and three numbered red ones are three bees.

In the first test, the movement of the heroes looks like this.

After selecting the starting vertices.

The first move after the bees move.

The first move after the Nastya's move. The first bee caught Nastya.

In the second test, the movement of the heroes looks like this.

After selecting the starting vertices.

The first move after the bees move.

The first move after the Nastya's move.

The second move after the bees move. The first bee caught Nastya.

设娜斯佳为一枚绿色棋子，三枚编号的红色棋子则代表三只蜜蜂。

在第一个测试用例中，角色的移动过程如下所示：

选定起始顶点后。

蜜蜂移动后的第一步。

娜斯佳移动后的第一步。第一只蜜蜂捕获了娜斯佳。

在第二个测试用例中，角色的移动过程如下所示：

选定起始顶点后。

蜜蜂移动后的第一步。

娜斯佳移动后的第一步。

蜜蜂移动后的第二步。第一只蜜蜂捕获了娜斯佳。