P9319 [EGOI 2022] Social Engineering / 社会工程

Day 1 Problem C. 题面译自 [EGOI2022 socialengineering](https://stats.egoi.org/media/task_description/2022_socialengineering_en.pdf)。 [](https://creativecommons.org/licenses/by-sa/3.0/) **本题是一道 Grader 交互题。** 本题只支持 C++ 提交，提交时不需要包含 `socialengineering.h` 头文件，但需要在代码中包含 `GetMove` 和 `MakeMove` 函数的声明（见【交互方式】部分）。 请使用 C++14、C++17 等语言，**而不是 C++14 (GCC 9)**，因为一些未知原因这个语言下 SPJ 会 CE。 感谢 @[FFTotoro](https://www.luogu.com.cn/user/556366) 提供交互库和测试数据。

一个社交网络是一个 $n$ 点 $m$ 边的无向连通图组成，其中每个点代表一个人，如果两个人之间有边相连，他们就是朋友。 玛丽亚是这个社交网络的成员。她喜欢以各种事情挑战她的朋友。这意味着，她首先执行一些简单的任务，然后挑战她的一个朋友做同样的事情。这个朋友随后会挑战他的一个朋友，而被挑战的朋友会接着挑战他的另一个朋友，以此类推。同一个人可能会被挑战多次，但每一个无序朋友对最多进行一次挑战。（一旦 A 挑战了 B，那么 A 和 B 都不能再次挑战对方。）换句话说，挑战可以看作图中的一条路径，其中一条边至多经过一次。 如果轮到一个人，而他又不能挑战任何朋友，那么这个人就输了。挑战总是由玛丽亚开始，她很少输。现在其他 $n-1$ 人决定合作，以使玛丽亚输掉下一次挑战，请你帮助他们完成目标。 --- **交互方式** 你必须实现一个函数： ```cpp void SocialEngineering(int n, int m, vector edges); ``` 这个函数在 $n$ 点 $m$ 边的图上玩该游戏。这个函数会被交互库调用恰好一次。列表 `edges` 包含恰好 $m$ 对整数 $(u,v)$，表示有一条连接点 $u$ 和点 $v$ 的边。节点编号从 $1$ 到 $n$。玛丽亚永远是节点 $1$。你的函数可以调用以下函数： ```cpp int GetMove(); ``` 这个函数应当在玛丽亚的回合被调用，例如游戏的最开始。如果你在不是玛丽亚的回合调用这个函数，你会 WA。这个函数可以返回以下值之一： - 一个整数 $v$，其中 $2\le v\le n$。这意味着玛丽亚挑战编号为 $v$ 的人。保证这一步一定合法。 - $0$，如果玛丽亚认输。当玛丽亚没有合法操作时，她就会认输。当这发生时，你的程序应当使 `SocialEngineering` 函数返回，然后你会 AC。 ```cpp 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$ 分）：无特殊限制。 --- 感谢 @[FFTotoro](https://www.luogu.com.cn/user/556366) 提供交互库和测试数据。