Background

Day 1 Problem C.

Translated from EGOI2022 socialengineering。

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

ing the interaction library and testdata。

Problem Description

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:

void SocialEngineering(int n, int m, vector<pair<int,int>> 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:

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.

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.

Input Format

See the “Interaction” section.

Output Format

See the “Interaction” section.

Hint

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

ing the interaction library and testdata。

Translated by ChatGPT 5