题目背景

Day 1 Problem C.

题面译自 EGOI2022 socialengineering。

本题是一道 Grader 交互题。

本题只支持 C++ 提交，提交时不需要包含 socialengineering.h 头文件，但需要在代码中包含 GetMove 和 MakeMove 函数的声明（见【交互方式】部分）。

请使用 C++14、C++17 等语言，而不是 C++14 (GCC 9)，因为一些未知原因这个语言下 SPJ 会 CE。

感谢

互库和测试数据。

题目描述

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

玛丽亚是这个社交网络的成员。她喜欢以各种事情挑战她的朋友。这意味着，她首先执行一些简单的任务，然后挑战她的一个朋友做同样的事情。这个朋友随后会挑战他的一个朋友，而被挑战的朋友会接着挑战他的另一个朋友，以此类推。同一个人可能会被挑战多次，但每一个无序朋友对最多进行一次挑战。（一旦 A 挑战了 B，那么 A 和 B 都不能再次挑战对方。）换句话说，挑战可以看作图中的一条路径，其中一条边至多经过一次。

如果轮到一个人，而他又不能挑战任何朋友，那么这个人就输了。挑战总是由玛丽亚开始，她很少输。现在其他 $n-1$ 人决定合作，以使玛丽亚输掉下一次挑战，请你帮助他们完成目标。

---

交互方式

你必须实现一个函数：

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

这个函数在 $n$ 点 $m$ 边的图上玩该游戏。这个函数会被交互库调用恰好一次。列表 edges 包含恰好 $m$ 对整数 $(u,v)$，表示有一条连接点 $u$ 和点 $v$ 的边。节点编号从 $1$ 到 $n$。玛丽亚永远是节点 $1$。你的函数可以调用以下函数：

int GetMove();

这个函数应当在玛丽亚的回合被调用，例如游戏的最开始。如果你在不是玛丽亚的回合调用这个函数，你会 WA。这个函数可以返回以下值之一：

• 一个整数 $v$，其中 $2\le v\le n$。这意味着玛丽亚挑战编号为 $v$ 的人。保证这一步一定合法。
• $0$，如果玛丽亚认输。当玛丽亚没有合法操作时，她就会认输。当这发生时，你的程序应当使 SocialEngineering 函数返回，然后你会 AC。

void MakeMove(int v);

这个函数应当在不是玛丽亚的回合被调用。这意味着当前回合的人挑战第 $v$ 个人。如果这一步不合法，或者在玛丽亚的回合调用这个函数，你会 WA。如果在游戏开始时，玛丽亚有必胜策略，你的程序应当在第一次调用 GetMove() 前使 SocialEngineering 函数返回，然后你会 AC。

输入格式

见【交互方式】部分。

输出格式

见【交互方式】部分。

提示

样例交互过程 $1$

你的操作	交互库的操作	解释说明
	SocialEngineering(5, 6, {{1,4}, {1,5}, {2,4}, {2,5}, {2,3}, {3,5}})	SocialEngineering 被调用，参数为一个 $5$ 点 $6$ 边的图。
GetMove()	返回 $4$	玛丽亚挑战第 $4$ 个人。
MakeMove(2)		第 $4$ 个人挑战第 $2$ 个人。
MakeMove(5)		第 $2$ 个人挑战第 $5$ 个人。
MakeMove(1)		第 $5$ 个人挑战玛丽亚。
GetMove()	返回 $0$	玛丽亚没有合法操作，所以她认输。
返回		你赢了游戏，应当使 SocialEngineering 函数返回。

---

样例交互过程 $2$

你的操作	交互库的操作	解释说明
	SocialEngineering(5, 1, {{1,2}})	SocialEngineering 被调用，参数为一个 $2$ 点 $1$ 边的图。
返回		玛丽亚有必胜策略，你的程序应当在未调用 GetMove() 前使 SocialEngineering 函数返回以认输。

---

数据范围

对于全部数据，$2\le n\le 2\times 10^5$，$1\le m\le 4\times 10^5$。保证图连通，每对无序点对至多作为边出现一次，每条边连接两个不同节点。

当玛丽亚有必胜策略时，她会完美地执行必胜策略。如果她没有必胜策略，她会试图以各种聪明的手段引诱你的程序犯错误。除子任务三外，只有当玛丽亚没有合法操作时，她才会认输。

• 子任务一（$15$ 分）：$n,m\le 10$。
• 子任务二（$15$ 分）：除玛丽亚外，每个人至多有 $2$ 个朋友。
• 子任务三（$20$ 分）：除非玛丽亚有必胜策略，否则她会立即认输。
• 子任务四（$25$ 分）：$n,m\le 100$。
• 子任务五（$25$ 分）：无特殊限制。

---

感谢

互库和测试数据。