Nastya and Bees

题意翻译

## 题目背景 **非常的不幸，出题人对这个问题的题解的证明中发现了一个错误。目前，我们还不知道正确的解决方案。不过，您可以解决这道题，但如果您的程序通过了所有的测试点，这也不能保证您的算法是正确的。如果您的程序通过了所有的测试点，并且您确信它是正确的，那么您可以将您的算法写信给出题人。** ## 题目描述 大家肯定都读过《爱丽丝梦游仙境》这本书。在这道题中，娜斯提亚到达了一个有着三只奇怪蜜蜂的国家。这些蜜蜂很奇怪，因为它们的蜂巢是五边形的。娜斯提亚是非法来的，所以她不想让蜜蜂抓到她。让我们帮助蜜蜂惩罚入侵者！ **这是一道交互题** 蜂巢是一个无向连通图，蜜蜂和娜斯提亚可以沿着边缘移动。这张图满足下面两个性质: - 这张图上任意一个节点的度数 $\le3$。 - 对于每条边，都存在一个长度 $\le5$ 的环包含这条边。 有三只蜜蜂和娜斯提亚。你要作为蜜蜂来完成这次任务。首先，你要选择放置蜜蜂的那些顶点。然后娜斯提亚会选择另一个顶点作为她初始时将出现的位置。第一次是你移动蜜蜂，然后是娜斯提亚移动，依次轮流移动，移动要满足下面的条件： 1. 对于每一只蜜蜂，你可以将它沿着它当前停留的顶点的某条出边移动它，也可以将它留在原地。 2. 然后娜斯提亚**必然**会从她当前停留的顶点沿着图的某条边移动。 当任何时刻有至少一只蜜蜂与娜斯提亚在同一个顶点你就赢了。 如果 $n$ 次移动后依然没有出现这样的情况，那么你就输了。 **可以有多只蜜蜂出现在同一个节点里。** ## 输入格式 第一行包括两个正整数 $n(4\le n\le 5000)$ 和 $m(n\le m\le 3n)$，分别表示图的点数 $n$ 和图的边数 $m$。 接下来的 $m$ 行，每行包括两个正整数 $v$ 和 $u\ (1\le v,u\le n)$ ，表示有一条连接 $v$ 和 $u$ 的边。数据保证：这张图是一张连通图，且任意一个节点的度数 $\le3$。对于每条边，都存在一个长度 $\le5$ 的环包含这条边。注意：这张图**可能**含有重边。 ## 输出格式 在每一轮，你必须输出恰好三个顶点 $a,b,c\ (1\le a,b,c\le n)$。第一次输出的 $3$ 个顶点表示你最初放置蜜蜂的顶点。作为回应，你将收到娜斯提亚所处位置的顶点。接下来的每一行的 $3$ 个顶点表示你将把三只蜜蜂分别移到哪个顶点。每只蜜蜂的移动不被其他蜜蜂的移动影响。输出 $3$ 个顶点后，你会得到娜斯提亚去往的新顶点的编号。 一旦其中一只蜜蜂与娜斯提亚处于同一顶点或你已达到移动次数的限制，你的程序应该停止工作。也就是说，如果你采取了行动之后，其中一只蜜蜂与娜斯提亚位于同一顶点，则你的程序必须停止工作，或者如果娜斯提亚采取行动并最终与其中一只蜜蜂位于同一顶点，你不应该采取行动，程序应停止工作。 如果移动次数超过限制（ 图的节点数 $n$ ），你会得到答案错误的评测结果。 如果你不输出任何内容或忘记刷新输出缓冲区，你可能会收到 `Idleness Limit Exceeded` 的评测结果。 要刷新输出缓冲区，你需要在输出查询的结果之后立即执行以下操作： - C++ 中的 `fflush(stdout)` 或 `cout.flush()`。 - Java 中的 `System.out.flush()` - Pascal 中的 `flush(output)`。 - Python 中的 `stdout.flush()`。 在这个问题中，交互者是**自适应的**。这意味着根据你之前的所有移动，娜斯提亚的行为可能会发生变化。 你不能 hack 这道题。

题目描述

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.

输入输出格式

输入格式

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.

输出格式

At each turn, you must output exactly three vertices $ a, b, c $ $ (1 \leq a, b, c \leq n) $ . For the first time, $ 3 $ vertices displayed will indicate which vertices you originally placed bees on. In response, you will receive the vertex where the jury placed Nastya. Each next $ 3 $ vertices will indicate where the $ 3 $ bees move at your turn. Each of the bees can, regardless of other bees, both remain at the current vertex and move along the edge. After the next output of $ 3 $ vertices, in response, you get the number of the new vertex to which Nastya went. As soon as one of the bees is at the same vertex with Nastya or you have reached the limit on the number of moves, your program should stop working. That is if you made a move, and one of the bees ended up at the same vertex with Nastya, your program must stop working, or if Nastya made a move and ended up at the same vertex with one of the bees, you should not make your move and the program should stop working. If the number of moves exceeds limit ( $ n $ , where $ n $ is the number of vertices), you will get the Wrong Answer verdict. Your solution may receive the verdict Idleness Limit Exceeded if you don't output anything or forget to flush the output buffer. To flush the output buffer, you need to do the following immediately after printing the query and the line end: - fflush(stdout) or cout.flush() in C++; - System.out.flush() in Java; - flush(output) in Pascal; - stdout.flush() in Python; - for other languages see documentation. In this problem interactor is adaptive. This means that depending on all your previous moves, Nastya's behavior may change. Hacks are not available for this problem.

输入输出样例

输入样例 #1

5 5
1 2
2 3
3 4
4 5
5 1
4
5

输出样例 #1

1 1 2
1 5 3

输入样例 #2

8 9
1 2
2 3
3 4
4 5
5 1
5 6
6 7
7 8
8 4
1
5

输出样例 #2

7 3 3
6 2 2
5 3 1

说明

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.