European Girls'
Olympiad in Informatics
EGOI - 2022

SocialEngineering
Day1 Tasks
English (ISC)

Antalya / TürkiyeSocial Engineering
Problem Name

Social Engineering

Input ﬁleInteractive task

Output ﬁleInteractive task

Time limit

5 seconds

Memory limit

256 megabytes

A social network consists of an undirected connected graph with n vertices and m edges, whereeach vertex is a person, and two people are friends, if there is an edge between them.
Maria is a member of this social network. She likes challenging her friends to do various things.
This means that she ﬁrst performs some simple task, and then challenges one of her friends to dothe same. This friend will then challenge one of their friends, who will challenge one of theirfriends, and so on. It could happen that the same person gets challenged more than once, buteach unordered pair of friends can only take part in the challenge at most once. (Once a person A
challenges a person B, then neither person A nor person B can challenge the other again.) In otherwords, the challenges will be a walk in the graph that never uses an edge more than once.
A person loses the challenge if it is their turn and they cannot challenge any of their friends. Thechallenges are always started by Maria, and she rarely loses. Now the remaining n − 1 people havedecided to collaborate in order to make Maria lose the next challenge, and it is your job tocoordinate this eﬀort.

Implementation
You must implement a function:
void SocialEngineering(int n, int m, vector<pair<int,int>> edges);that plays the game on a graph with n vertices and m edges. This function will be called once by
the grader. The list edges will contain exactly m pairs of integers (u, v), meaning that an edge goes
between vertex u and vertex v. Vertices are numbered from 1 to n. Maria is always vertex 1. Yourfunction can make calls to the following functions:int GetMove();
This method should be called whenever it is Maria’s turn, such as in the beginning of the game. If

SocialEngineering (1 of 4)

you call this method when it is not Maria’s turn, you will get the verdict Wrong Answer. The
method can return one of the following values:
an integer v, where 2 ≤ v ≤ n. This means that Maria challenges the person with index v. This
will always be a legal move.
0, if Maria resigns the game. Maria will always resign, if she has no legal moves. When thishappens, your program should let the function SocialEngineering return, and you will
get the verdict Accepted.
void MakeMove(int v);
This method should be called whenever it is not Maria’s turn. This means that the person with theturn challenges the person v. If this is not a legal move or if it is Maria’s turn at the time of the call,then you will get the verdict Wrong Answer.
If Maria has a winning strategy at the start of the game, your program should let
SocialEngineering return before the ﬁrst call to GetMove(). You will then get the verdictAccepted.

Constraints
2 ≤ n ≤ 2 ⋅ 105.
1 ≤ m ≤ 4 ⋅ 105.
The graph is connected. Every unordered pair of vertices will appear at most once as anedge, and every edge will go between two diﬀerent vertices.

Subtasks
Maria will always play perfectly in the sense that she will make winning moves whenever she has awinning strategy. If she does not have a winning strategy, then she will try to lure your program
into making a mistake, in various clever ways. She will only resign if she has no legal moves, except
in Subtask 3.
1. (15 points) n, m ≤ 10.
2. (15 points) Everyone except Maria has at most 2 friends.
3. (20 points) Maria will resign immediately unless she has a winning strategy.
4. (25 points) n, m ≤ 100.
5. (25 points) No further constraints.

SocialEngineering (2 of 4)

Sample Interaction
Your action

Grader action

ExplanationSocialEngineering(5, 6, {{1,4},SocialEngineering is called{1,5}, {2,4}, {2,5}, {2,3},

with a graph with 5 vertices and 6{3,5}})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
resigns.
You have won the game, andshould let SocialEngineering-Returns

return.
Youraction-Returns

Grader action

Explanation

SocialEngineering(2,SocialEngineering is called with a graph with 21, {{1,2}})vertices and 1 edge.

-Maria has a winning strategy on this graph, so you
should return without making any GetMove() calls toresign.

Sample Grader
The provided sample grader, grader.cpp, in the task attachment SocialEngineering.zip,
reads the input from the standard input in the following format:
The ﬁrst line contains the number of vertices, n, and the number of edges, m in the graph.
The following m lines contains two integers u and v, indicating that there is an edge betweenu and v.
Sample grader reads the input and calls the SocialEngineering function in user’s solution. Notethat the sample grader does not implement Maria’s winning strategy and provided only for asample interaction.
To compile the sample grader with your solution, you may use the following command at theSocialEngineering (3 of 4)

terminal prompt:
g++ -std=gnu++11 -O2 -o solution grader.cpp solution.cpp
where solution.cpp is your solution ﬁle to be submitted to CMS. To run the program with thesample input provided in the attachment, type the following command into the terminal prompt:./solution < input.txt

SocialEngineering (4 of 4)