注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 17 及以上）

请在提交源代码前添加 #include "socialengineering.h"。

题目描述

题目译自 EGOI2022 Day1 T3. Social Engineering

一个社交网络可以用一个无向连通图表示，图中有 $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();

当轮到玛丽亚行动时（比如游戏刚开始时），你应该调用这个函数。如果在不是玛丽亚的回合调用它，你会得到「Wrong Answer」的评测结果。这个函数可能返回以下值之一：

• 一个整数 $v$ $(2 \leq v \leq n)$，表示玛丽亚挑战编号为 $v$ 的人。这个移动总是合法的。
• $0$，表示玛丽亚放弃游戏。如果玛丽亚没有合法的移动，她会放弃。这时，你的程序应该让 SocialEngineering 函数返回，你会得到「Accepted」的评测结果。

void MakeMove(int v);

当轮到其他人行动时，你需要调用这个函数，表示当前回合的人挑战编号为 $v$ 的人。如果这个移动不合法，或者调用时是玛丽亚的回合，你会得到「Wrong Answer」的评测结果。

如果游戏开始时玛丽亚有必胜策略，你的程序应该在第一次调用 GetMove() 之前让 SocialEngineering 返回，你会得到「Accepted」的评测结果。

示例评测程序

任务附件 SocialEngineering.zip 中提供了样例评测程序 grader.cpp，它从标准输入读取以下格式的输入：

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

样例评测程序会读取输入并调用你实现的 SocialEngineering 函数。注意，样例评测程序并未实现玛丽亚的必胜策略，仅用于演示交互过程。

要将你的解决方案与样例评测程序一起编译，可以在终端输入以下命令：

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

其中 solution.cpp 是你要提交到 CMS 的解决方案文件。要用附件中的样例输入运行程序，请在终端输入：

./solution < input.txt

样例 1

样例 2

数据范围与提示

对于所有输入数据，满足：

• $2 \leq n \leq 2 \cdot 10^{5}$
• $1 \leq m \leq 4 \cdot 10^{5}$
• 图是连通的。每对顶点（无序）最多只出现一次作为一条边，每条边连接的都是不同的顶点。

玛丽亚总是以最佳策略行动：只要有必胜策略，她就会赢。如果没有必胜策略，她会用各种巧妙的方式诱导你的程序出错。她只有在没有合法移动时才会放弃（子任务 3 除外）。

详细子任务附加限制及分值如下表所示。