社交工程

注意事项

本题为 函数接口式交互题。由于语言限制，目前只支持以下语言提交：

• C++17 及以上。

提交代码开头必须包含：

#include "socialengineering.h"

选手只需要实现 SocialEngineering 函数，不需要、也不应该编写 main 函数，也不要直接读写标准输入输出。

在 Hydro OJ 上，评测系统会自动链接 socialengineering.h。该头文件会读取测试数据，调用你的 SocialEngineering 函数，并把你对 GetMove、MakeMove 的调用转换成交互协议与评测器通信。

你可以调用的函数只有：

int GetMove();
void MakeMove(int v);

题目描述

一个社交网络可以用一张无向连通图表示。图中有 $n$ 个顶点和 $m$ 条边。每个顶点代表一个人，如果两个人之间有一条边，就说明他们是朋友。

玛丽亚是这个社交网络中的一员，她的编号固定为 $1$。

玛丽亚喜欢挑战她的朋友们去做各种事情。她会先完成一个简单的任务，然后挑选一个朋友去做同样的事。被挑战的朋友会再挑选自己的一个朋友，以此类推，挑战会沿着朋友关系不断传下去。

同一个人可能会被多次挑战，但每对朋友之间的边最多只能在挑战过程中使用一次。也就是说，一旦 $A$ 挑战了 $B$，之后 $A$ 和 $B$ 之间这条边就不能再被使用。用图论语言来说，挑战过程形成一条迹，每条边最多经过一次。

如果轮到某个人挑战时，他已经没有可以挑战的朋友，那么这个人就输了。

挑战总是由玛丽亚开始。现在，网络中除了玛丽亚以外的 $n-1$ 个人决定联手，让玛丽亚在这场挑战游戏中失败。你的任务就是协调他们的行动。

玛丽亚会采用最佳策略：如果她存在必胜策略，她一定会赢；如果她没有必胜策略，她也会尽量用各种方式诱导你的程序出错。只有当玛丽亚轮到行动且没有任何合法移动时，她才会放弃。

提交接口

你需要实现如下函数：

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

该函数会被评测程序调用一次。

参数含义如下：

• $n$：社交网络中的人数，顶点编号为 $1$ 到 $n$；
• $m$：朋友关系数量；
• edges：长度为 $m$ 的数组，每个元素是一个二元组 $(u,v)$，表示 $u$ 和 $v$ 是朋友。

玛丽亚始终是编号为 $1$ 的顶点。

你的程序需要根据这张图判断玛丽亚是否有必胜策略，并按下面规则行动。

可调用函数

GetMove

int GetMove();

当且仅当轮到玛丽亚行动时，你应该调用该函数。

如果在不是玛丽亚的回合调用 GetMove()，将会得到 Wrong Answer。

该函数会返回以下两类值之一：

• 一个整数 $v$，满足 $2 \le v \le n$，表示玛丽亚选择挑战编号为 $v$ 的人。这个移动一定是当前局面下的合法移动。
• $0$，表示玛丽亚没有合法移动并放弃游戏。此时你应该直接让 SocialEngineering 函数返回。

MakeMove

void MakeMove(int v);

当轮到除玛丽亚以外的人行动时，你需要调用该函数，表示当前被挑战的人接下来挑战编号为 $v$ 的人。

如果该移动不合法，或者在轮到玛丽亚行动时调用 MakeMove，将会得到 Wrong Answer。

一个移动合法当且仅当：

• 当前行动的人与 $v$ 之间存在一条尚未使用过的边；
• 这条边此前没有在挑战过程中被使用过。

调用 MakeMove(v) 后，这条边会被标记为已使用，轮到 $v$ 行动。

你需要达成的目标

如果玛丽亚在初始局面下有必胜策略，你应该在第一次调用 GetMove() 之前直接从 SocialEngineering 函数返回。

如果玛丽亚没有必胜策略，你需要通过调用 GetMove() 和 MakeMove(v) 来进行游戏，并最终迫使玛丽亚没有合法移动。此时 GetMove() 会返回 $0$，随后你应该让 SocialEngineering 函数返回。

请注意：

• 不要输出任何内容；
• 不要读入任何内容；
• 不要手动输出 GetMove、MakeMove 或 Exit；
• 这些交互协议已经由 socialengineering.h 自动完成。

本地调试方式

以下内容仅用于本地调试。在 Hydro OJ 上提交时，只需要提交实现 SocialEngineering 函数的代码。

附件中的评测程序会从标准输入读取如下数据：

第一行包含两个整数：

n m

接下来 $m$ 行，每行两个整数 $u,v$，表示 $u$ 和 $v$ 之间有一条边。

评测程序会读取输入，调用你的 SocialEngineering 函数，并检查你的函数调用行为是否合法。

本地编译时，可以使用类似命令：

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

其中 solution.cpp 是你的解答代码。

样例 1

下面给出一次可能的交互过程。

程序行为	评测程序响应	说明
	SocialEngineering(5, 6, {{1,4}, {1,5}, {2,4}, {2,5}, {2,3}, {3,5}})	调用你的函数，图有 $5$ 个顶点和 $6$ 条边。
GetMove()	返回 4	玛丽亚挑战 $4$ 号。
MakeMove(2)		$4$ 号挑战 $2$ 号。
MakeMove(5)		$2$ 号挑战 $5$ 号。
MakeMove(1)		$5$ 号挑战玛丽亚。
GetMove()	返回 0	玛丽亚无合法移动并放弃。
return		你的函数返回，你获胜。

样例 2

程序行为	评测程序响应	说明
	SocialEngineering(2, 1, {{1,2}})	调用你的函数，图有 $2$ 个顶点和 $1$ 条边。
return		玛丽亚有必胜策略，你应该直接返回。

数据范围

对于所有测试数据，满足：

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

子任务

子任务	分值	附加限制
$1$	$15$	$n,m \le 10$
$2$		除了玛丽亚以外，每个人的朋友数量不超过 $2$
$3$	$20$	除非玛丽亚有必胜策略，否则她会立刻放弃
$4$	$25$	$n,m \le 100$
$5$		无附加限制

@下发的头文件