Social Engineering in a Graph

A social network is modeled as an undirected connected graph with \(n\) nodes and \(m\) edges. Each node represents a person and an edge between two nodes means they are friends.

Maria is node \(1\) in this network. She loves to challenge her friends with simple tasks. The game plays as follows: Maria performs a task and then challenges one of her friends. That friend in turn challenges one of his friends, and so on. A person may be challenged multiple times, but each unordered pair of friends may be used for a challenge at most once (i.e. if person A challenges person B, then A and B cannot challenge each other again). Equivalently, the challenge can be viewed as a path in the graph in which each edge appears at most once.

If it is a person’s turn and they have no legal challenge (i.e. no unused edge incident to them), that person loses. The game always starts with Maria. In typical play Maria rarely loses. However, the other \(n-1\) people have decided to cooperate in order to force Maria to lose the next round. Your task is to help them achieve that goal.

In addition, if Maria actually has a winning strategy from the very beginning, your program should immediately stop (before calling any function to get her move) and let the interactor decide the outcome.

Interaction Protocol

You must implement a function with the following signature:

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

This function will be called exactly once with the graph data. The list edges contains exactly \(m\) pairs of integers \((u,v)\) representing an edge between nodes \(u\) and \(v\). Nodes are numbered from \(1\) to \(n\), and Maria is always node \(1\).

Your function can call two helper functions:

• int GetMove(); — This function is to be called on Maria's turn. When called, it returns:
  • An integer \(v\) (with \(2 \le v \le n\)), meaning that Maria challenges person \(v\). It is guaranteed that this move is legal.
  • 0, if Maria concedes (this happens only when she has no legal move). In this case your SocialEngineering function should return.
• void MakeMove(int v); — This function is to be called on a turn that does not belong to Maria. It indicates that the current player challenges person \(v\). Calling this function on Maria's turn or making an illegal move will result in a wrong answer.

Note: If at the start Maria has a winning strategy, you must return from SocialEngineering before calling GetMove(), and you will be awarded AC.

Game Summary: The game is played on the graph with the following rules:

• The game starts at node \(1\) (Maria).
• In each turn, the current player selects an edge incident to the current node that has not been used before, and challenges the friend at the other end. That edge is then considered used.
• If a player is to move but has no unused edge incident to the current node, they lose.

The cooperating players (nodes other than \(1\)) aim to force the game to end on Maria's turn with no legal moves.

inputFormat

The input begins with a line containing two integers \(n\) and \(m\) — the number of nodes and edges in the graph. The following \(m\) lines each contain two integers \(u\) and \(v\), representing an undirected edge between nodes \(u\) and \(v\). After the graph description, additional lines provide Maria's moves when required by the interaction (each move is an integer). You may assume that the graph is connected and Maria is always node \(1\).

outputFormat

Your program should simulate the interactive game. On each turn that is not Maria's, call MakeMove(v) to output your chosen move (for example, by printing the move to standard output). When the game ends, output a final line: if Maria loses, print Maria loses; otherwise, print Maria wins. (Note that in a real interactive problem you would not typically output the final line, but for offline simulation it is used to verify the outcome.)

sample

3 2
1 2
2 3
2

3
Maria loses

</p>