{"raw_statement":[{"iden":"background","content":"Day 1 Problem C.\n\n题面译自 [EGOI2022 socialengineering](https://stats.egoi.org/media/task_description/2022_socialengineering_en.pdf)。\n\n[![CC BY-SA 3.0](https://licensebuttons.net/l/by-sa/3.0/80x15.png)](https://creativecommons.org/licenses/by-sa/3.0/)\n\n**本题是一道 Grader 交互题。**\n\n本题只支持 C++ 提交，提交时不需要包含 `socialengineering.h` 头文件，但需要在代码中包含 `GetMove` 和 `MakeMove` 函数的声明（见【交互方式】部分）。\n\n请使用 C++14、C++17 等语言，**而不是 C++14 (GCC 9)**，因为一些未知原因这个语言下 SPJ 会 CE。\n\n感谢 @[FFTotoro](https://www.luogu.com.cn/user/556366) 提供交互库和测试数据。"},{"iden":"statement","content":"一个社交网络是一个 $n$ 点 $m$ 边的无向连通图组成，其中每个点代表一个人，如果两个人之间有边相连，他们就是朋友。\n\n玛丽亚是这个社交网络的成员。她喜欢以各种事情挑战她的朋友。这意味着，她首先执行一些简单的任务，然后挑战她的一个朋友做同样的事情。这个朋友随后会挑战他的一个朋友，而被挑战的朋友会接着挑战他的另一个朋友，以此类推。同一个人可能会被挑战多次，但每一个无序朋友对最多进行一次挑战。（一旦 A 挑战了 B，那么 A 和 B 都不能再次挑战对方。）换句话说，挑战可以看作图中的一条路径，其中一条边至多经过一次。\n\n如果轮到一个人，而他又不能挑战任何朋友，那么这个人就输了。挑战总是由玛丽亚开始，她很少输。现在其他 $n-1$ 人决定合作，以使玛丽亚输掉下一次挑战，请你帮助他们完成目标。\n\n---\n\n**交互方式**\n\n你必须实现一个函数：\n\n```cpp\nvoid SocialEngineering(int n, int m, vector<pair<int,int>> edges);\n```\n\n这个函数在 $n$ 点 $m$ 边的图上玩该游戏。这个函数会被交互库调用恰好一次。列表 `edges` 包含恰好 $m$ 对整数 $(u,v)$，表示有一条连接点 $u$ 和点 $v$ 的边。节点编号从 $1$ 到 $n$。玛丽亚永远是节点 $1$。你的函数可以调用以下函数：\n\n```cpp\nint GetMove();\n```\n\n这个函数应当在玛丽亚的回合被调用，例如游戏的最开始。如果你在不是玛丽亚的回合调用这个函数，你会 WA。这个函数可以返回以下值之一：\n\n- 一个整数 $v$，其中 $2\\le v\\le n$。这意味着玛丽亚挑战编号为 $v$ 的人。保证这一步一定合法。\n- $0$，如果玛丽亚认输。当玛丽亚没有合法操作时，她就会认输。当这发生时，你的程序应当使 `SocialEngineering` 函数返回，然后你会 AC。\n\n```cpp\nvoid MakeMove(int v);\n```\n\n这个函数应当在不是玛丽亚的回合被调用。这意味着当前回合的人挑战第 $v$ 个人。如果这一步不合法，或者在玛丽亚的回合调用这个函数，你会 WA。如果在游戏开始时，玛丽亚有必胜策略，你的程序应当在第一次调用 `GetMove()` 前使 `SocialEngineering` 函数返回，然后你会 AC。"},{"iden":"input","content":"见【交互方式】部分。"},{"iden":"output","content":"见【交互方式】部分。"},{"iden":"note","content":"**样例交互过程 $1$**\n\n|你的操作|交互库的操作|解释说明|\n|:-|:-|:-|\n||`SocialEngineering(5, 6, {{1,4}, {1,5}, {2,4}, {2,5}, {2,3}, {3,5}})`|`SocialEngineering` 被调用，参数为一个 $5$ 点 $6$ 边的图。|\n|`GetMove()`|返回 $4$|玛丽亚挑战第 $4$ 个人。|\n|`MakeMove(2)`||第 $4$ 个人挑战第 $2$ 个人。|\n|`MakeMove(5)`||第 $2$ 个人挑战第 $5$ 个人。|\n|`MakeMove(1)`||第 $5$ 个人挑战玛丽亚。|\n|`GetMove()`|返回 $0$|玛丽亚没有合法操作，所以她认输。|\n|返回||你赢了游戏，应当使 `SocialEngineering` 函数返回。|\n\n---\n\n**样例交互过程 $2$**\n\n|你的操作|交互库的操作|解释说明|\n|:-|:-|:-|\n||`SocialEngineering(5, 1, {{1,2}})`|`SocialEngineering` 被调用，参数为一个 $2$ 点 $1$ 边的图。|\n|返回||玛丽亚有必胜策略，你的程序应当在未调用 `GetMove()` 前使 `SocialEngineering` 函数返回以认输。|\n\n---\n\n**数据范围**\n\n对于全部数据，$2\\le n\\le 2\\times 10^5$，$1\\le m\\le 4\\times 10^5$。保证图连通，每对无序点对至多作为边出现一次，每条边连接两个不同节点。\n\n当玛丽亚有必胜策略时，她会完美地执行必胜策略。如果她没有必胜策略，她会试图以各种聪明的手段引诱你的程序犯错误。除子任务三外，只有当玛丽亚没有合法操作时，她才会认输。\n\n- 子任务一（$15$ 分）：$n,m\\le 10$。\n- 子任务二（$15$ 分）：除玛丽亚外，每个人至多有 $2$ 个朋友。\n- 子任务三（$20$ 分）：除非玛丽亚有必胜策略，否则她会立即认输。\n- 子任务四（$25$ 分）：$n,m\\le 100$。\n- 子任务五（$25$ 分）：无特殊限制。\n\n---\n\n感谢 @[FFTotoro](https://www.luogu.com.cn/user/556366) 提供交互库和测试数据。"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}