题意理解

我们有一个 n 个点 m 条边 的无向连通图，节点 1 是 Maria。
游戏规则：

• Maria 先行动，选择一个朋友发出挑战；
• 被挑战的人必须再选择一个自己的朋友（且两人之间的这条边之前没被用过）继续挑战；
• 同一个人可能被多次挑战，但同一对朋友之间只能挑战一次（即每条边只能用一次）；
• 如果轮到某人时没有可用的边去挑战别人，这个人就输；
• 除了 Maria 外，其他 n-1 个人可以合作，目标是让 Maria 输。

交互方式

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

可以调用：

• int GetMove()：当轮到 Maria 行动时调用，返回 Maria 选择的挑战对象编号（2~n）或 0（Maria 放弃）。
• void MakeMove(int v)：当轮到其他人行动时，你选择挑战对象 v。

如果 Maria 有必胜策略，你应该在第一次调用 GetMove() 之前直接返回（这样判为 Accepted）。

核心问题

这是一个 在图上沿未用过的边移动的博弈，实际上等价于在图上走 边不重复的路径（类似欧拉路径问题）。

关键点：

• 游戏结束当某人无法选择未用过的边去挑战别人；
• 因为每条边只能用一次，所以整个游戏过程是图上的一条轨迹（不一定简单）；
• 如果从 Maria（节点 1）出发，存在一种方式使得其他玩家可以迫使 Maria 无路可走，则我们（其他玩家）能赢；
• 否则 Maria 有必胜策略。

图的度数与胜负条件

这个问题其实是一个经典博弈模型：每个顶点是一个位置，每条边是一个可用的移动，边用过就删除。
这等价于 Undirected Edge Geography 游戏。

已知结论（在连通无向图上）：

• 如果节点 1 的度数为 0，Maria 立刻输（但题中图连通且 n≥2，所以不会出现）；
• 否则，Maria 有必胜策略当且仅当存在一个包含节点 1 的奇环，或者更一般地，图的某个一般化奇偶条件。

实际上，这个游戏在一般图上的胜负判定是：

设图 G 的某个最大匹配 M。如果存在一个不匹配节点 1 的最大匹配，则玩家 2（其他玩家）有必胜策略；否则玩家 1（Maria）必胜。

代码思路

Check(g) 函数判断：能否将 Maria 的邻居两两配对，并且路径不冲突：

• 标记与 Maria 相邻的点为 w[i]=true；
• 对每个不与 Maria 相邻的连通分量（去掉 Maria 后），检查该分量中与 Maria 相邻的点数是否为偶数；
• 如果存在某个分量的这种点数为奇数，则返回 false（直接返回，即 Maria 必胜？这里逻辑要确认）。

如果 Check(g) 返回 false，意味着 Maria 有必胜策略，所以直接返回；
否则，我们进入游戏循环，根据预先计算的路径 p[id[x]] 来应对 Maria 的每一步。

路径构建逻辑

在 Check 通过后，构建了一个路径集合 p：

• 对每个去掉 Maria 后的连通分量，做 DFS，把与 Maria 相邻的点（w[u]=true）两两配对，形成一条路径，路径中间经过的节点是分量内节点；
• 这样，当 Maria 走到某个邻居 x 时，我们就能用预先算好的路径 p[id[x]] 把挑战传回 Maria，并且用掉对应的边。

游戏循环

在循环中：

1. 调用 GetMove() 得到 Maria 的选择 move；
2. 如果 move=0，Maria 放弃，我们赢；
3. 否则，找到对应的路径 p[id[x]]，沿着路径依次 MakeMove，最后一步挑战 Maria（MakeMove(1)）；
4. 如果路径方向不对，就反转路径。

代码的安全措施

• 最大回合数限制，防止无限循环；
• 对 id[x] 的边界检查，避免越界；
• 如果找不到路径，就随便选一个邻居移动，保证程序不崩溃。

总结

这道题的关键是：

1. 判断 Maria 是否必胜 —— 用图的最大匹配性质或等价奇偶条件；
2. 如果 Maria 不胜，则构造一个应对策略，使得无论 Maria 怎么走，都能把挑战传回给她，并且用完所有可能的边，让她最终无路可走。