P9319 [EGOI 2022] Social Engineering / Social Engineering

Day 1 Problem C. Translated from [EGOI2022 socialengineering](https://stats.egoi.org/media/task_description/2022_socialengineering_en.pdf)。 [](https://creativecommons.org/licenses/by-sa/3.0/) **This is a grader interactive problem.** This problem only supports C++ submissions. You do not need to include the `socialengineering.h` header when submitting, but you need to declare the functions `GetMove` and `MakeMove` in your code (see the “Interaction” section). Please use C++14, C++17, etc., **instead of C++14 (GCC 9)**, because for some unknown reason the SPJ will get a compile error under that language option. Thanks to @[FFTotoro](https://www.luogu.com.cn/user/556366) for providing the interaction library and testdata。

A social network is an undirected connected graph with $n$ vertices and $m$ edges, where each vertex represents a person. If two people are connected by an edge, they are friends. Maria is a member of this social network. She likes to challenge her friends with various tasks. This means that she first performs some simple task and then challenges one of her friends to do the same. That friend will then challenge one of their friends, and the challenged friend will then challenge another one of their friends, and so on. The same person may be challenged multiple times, but each unordered pair of friends can be involved in a challenge at most once. (Once A challenges B, then neither A nor B can challenge each other again.) In other words, the challenge can be seen as a path in the graph, where each edge is traversed at most once. If it is a person’s turn and they cannot challenge any friend, then that person loses. The challenge always starts with Maria, and she rarely loses. Now the other $n-1$ people decide to cooperate to make Maria lose the next challenge. Please help them achieve this goal. --- **Interaction** You must implement a function: ```cpp void SocialEngineering(int n, int m, vector edges); ``` This function plays the game on a graph with $n$ vertices and $m$ edges. This function will be called by the interaction library exactly once. The list `edges` contains exactly $m$ pairs of integers $(u,v)$, meaning there is an edge connecting vertex $u$ and vertex $v$. Vertices are numbered from $1$ to $n$. Maria is always vertex $1$. Your function may call the following functions: ```cpp int GetMove(); ``` This function must be called on Maria’s turn, for example at the start of the game. If you call this function when it is not Maria’s turn, you will get WA. This function can return one of the following values: - An integer $v$, where $2\le v\le n$. This means Maria challenges person $v$. This move is guaranteed to be legal. - $0$, if Maria gives up. When Maria has no legal moves, she will give up. When this happens, your program should make the `SocialEngineering` function return, and you will get AC. ```cpp void MakeMove(int v); ``` This function must be called when it is not Maria’s turn. This means the person whose turn it currently is challenges person $v$. If this move is illegal, or if you call this function on Maria’s turn, you will get WA. If, at the start of the game, Maria has a winning strategy, your program should make the `SocialEngineering` function return before the first call to `GetMove()`, and you will get AC.

See the “Interaction” section.

See the “Interaction” section.

**Sample interaction 1** |Your action|Interaction library action|Explanation| |:-|:-|:-| ||`SocialEngineering(5, 6, {{1,4}, {1,5}, {2,4}, {2,5}, {2,3}, {3,5}})`|`SocialEngineering` is called with a graph with $5$ vertices and $6$ edges.| |`GetMove()`|returns $4$|Maria challenges person $4$.| |`MakeMove(2)`||Person $4$ challenges person $2$.| |`MakeMove(5)`||Person $2$ challenges person $5$.| |`MakeMove(1)`||Person $5$ challenges Maria.| |`GetMove()`|returns $0$|Maria has no legal moves, so she gives up.| |return||You win the game, and you should make the `SocialEngineering` function return.| --- **Sample interaction 2** |Your action|Interaction library action|Explanation| |:-|:-|:-| ||`SocialEngineering(5, 1, {{1,2}})`|`SocialEngineering` is called with a graph with $2$ vertices and $1$ edge.| |return||Maria has a winning strategy, and your program should make the `SocialEngineering` function return (give up) before calling `GetMove()`.| --- **Constraints** For all testdata, $2\le n\le 2\times 10^5$, $1\le m\le 4\times 10^5$. The graph is guaranteed to be connected. Each unordered pair of vertices appears as an edge at most once, and each edge connects two different vertices. When Maria has a winning strategy, she will execute it perfectly. If she does not have a winning strategy, she will try to use various clever tricks to lure your program into making mistakes. Except for subtask 3, she will only give up when she has no legal moves. - Subtask 1 ($15$ points): $n,m\le 10$. - Subtask 2 ($15$ points): Except for Maria, each person has at most $2$ friends. - Subtask 3 ($20$ points): Unless Maria has a winning strategy, she will give up immediately. - Subtask 4 ($25$ points): $n,m\le 100$. - Subtask 5 ($25$ points): No special constraints. --- Thanks to @[FFTotoro](https://www.luogu.com.cn/user/556366) for providing the interaction library and testdata。 Translated by ChatGPT 5