一个社交网络由一个无向连通图组成，图中有 $n$ 个顶点和 $m$ 条边，其中每个顶点代表一个人，如果两个人之间有边，则他们是朋友。

Maria 是这个社交网络的成员。她喜欢挑战她的朋友去做各种事情。这意味着她首先执行一些简单的任务，然后挑战她的一位朋友去做同样的事情。这位朋友随后会挑战他们的一位朋友，后者又会挑战他们的一位朋友，依此类推。同一个人可能会被多次挑战，但每对无序的朋友关系最多只能参与一次挑战。（一旦 A 挑战了 B，那么 A 和 B 之间就不能再互相挑战了。）换句话说，挑战过程将是图中的一条路径，且每条边最多只能使用一次。

如果轮到某人时，他无法挑战任何朋友，那么他就输掉了挑战。挑战总是由 Maria 发起的，而且她很少输。现在，其余的 $n - 1$ 个人决定合作，试图让 Maria 在下一次挑战中失败，你的任务是协调这一努力。

实现细节

你必须实现以下函数：

void SocialEngineering(int n, int m, vector<pair<int,int>> edges);

该函数将在一个具有 $n$ 个顶点和 $m$ 条边的图上进行游戏。该函数会被评测系统调用一次。列表 edges 将包含恰好 $m$ 对整数 $(u, v)$，表示顶点 $u$ 和顶点 $v$ 之间有一条边。顶点编号从 $1$ 到 $n$。Maria 始终是顶点 $1$。你的函数可以调用以下函数：

int GetMove();

每当轮到 Maria 时（例如在游戏开始时），都应调用此方法。如果你在不该 Maria 行动时调用此方法，你将得到 Wrong Answer 的判决。该方法可以返回以下值之一：

• 一个整数 $v$，其中 $2 \le v \le n$。这意味着 Maria 挑战索引为 $v$ 的人。这始终是一个合法的移动。
• $0$，表示 Maria 认输。如果 Maria 没有合法的移动，她总是会认输。当这种情况发生时，你的程序应让 SocialEngineering 函数返回，你将得到 Accepted 的判决。

void MakeMove(int v);

每当不轮到 Maria 时，都应调用此方法。这意味着当前轮到的人挑战顶点 $v$。如果这不是一个合法的移动，或者在调用时轮到 Maria 行动，你将得到 Wrong Answer 的判决。

如果 Maria 在游戏开始时就拥有必胜策略，你的程序应在第一次调用 GetMove() 之前让 SocialEngineering 返回。你将得到 Accepted 的判决。

数据范围

• $2 \le n \le 2 \cdot 10^5$
• $1 \le m \le 4 \cdot 10^5$
• 图是连通的。每对无序顶点之间最多出现一条边，且每条边连接两个不同的顶点。

子任务

Maria 总是会完美地进行游戏，这意味着只要她有必胜策略，她就会做出获胜的移动。如果她没有必胜策略，她会尝试通过各种巧妙的方式诱导你的程序犯错。除非在子任务 3 中，否则她只有在没有合法移动时才会认输。

1. (15 分) $n, m \le 10$。
2. (15 分) 除 Maria 外，每个人最多有 2 个朋友。
3. (20 分) 除非 Maria 有必胜策略，否则她会立即认输。
4. (25 分) $n, m \le 100$。
5. (25 分) 无附加限制。

样例

样例 1

样例 2

说明

提供的样例评测程序 grader.cpp（位于 SocialEngineering.zip 附件中）通过标准输入读取数据，格式如下：

• 第一行包含顶点数 $n$ 和边数 $m$。
• 接下来的 $m$ 行包含两个整数 $u$ 和 $v$，表示 $u$ 和 $v$ 之间有一条边。

样例评测程序读取输入并调用用户代码中的 SocialEngineering 函数。注意，样例评测程序并未实现 Maria 的必胜策略，仅用于演示交互过程。

要将样例评测程序与你的代码一起编译，可以在终端中使用以下命令：

g++ -std=gnu++11 -O2 -o solution grader.cpp solution.cpp

其中 solution.cpp 是你提交给 CMS 的代码文件。要使用附件中提供的样例输入运行程序，请在终端中输入以下命令：

./solution < input.txt