Problem G
Memento

Unfortunately, Loke’s memory is very bad. Sometimes, he may even completely forget that he’s seen a given graph. To avoid this public embarassment, he’s going to need a system. Every time he sees a graph, he can add at most $30$ edges to it. However, the next time he sees it, he needs to be able to identify that he’s seen it before based on the change. To make matters even worse, the graph is very large- it has $1000$ vertices and between $3500$ and $4500$ edges. To make things easier for him, he has asked you to write a computer program to help him.

More specifically, you’re asked to implement a computer program that roughly does the following:

1. Gets an undirected graph.

2. Determines whether the program has seen the graph before.

3. If it hasn’t seen it before, signal the $30$ edges to be added and exit.

4. If it has seen it before, it should simply exit.

To explain the process more exactly, the judge will do the following for each testcase:

1. The judge will generate a graph (exactly how is described below).

2. The judge will start your program and give it the graph. If your program incorrectly claims that it’s seen the graph before, you will receive a “Wrong Answer” verdict. Otherwise, the $30$ edges will be added to the graph.

3. The judge will then shuffle the vertex labels (i.e. node $1$ might be changed to $5$, but the new graph will be isomorphic to the one before the shuffle). The order in which edges are given, in addition to the order between the vertices of the edge will also be shuffled (i.e. the edge $4$ $2$ may be changed to $2$ $4$).

4. The judge will then start your program and give it the shuffled graph. If it correctly identifies that it’s seen the graph before, you have solved this testcase. Otherwise, you will receive a “Wrong Answer” verdict.

The method for generating the initial graph is as follows:

G = empty graph with 1000 nodes
choose M = random number between 3500 and 4500
for i between 1...M:
  add a random edge to G that doesn't already exist and connects two distinct vertices

All random values are generated uniformly at random ¹.

Example judges implementing these procedures are available to download in attachments.

Implementation

Your solution to the problem must be written in either C++ or Python. Reference implementations for both languages can be downloaded at the bottom of the page at attachments.

C++: You must not create a main function. Instead, you should implement the following function:

• std::vector<std::pair<int,int>> run(std::vector<std::pair<int,int>> edges);
  

  • The parameter edges is the graph. Its length is between $3500$ and $4530$. Each pair<int,int> contains two integers $a$ and $b$ ($0 \leq a,b \leq 999$, $a \neq b$), meaning that there is an edge between the nodes with index $a$ and $b$. Additionally, there will be at most one edge between any pair of vertices.

  • If you think you have already seen the graph before, return an empty vector.
    Otherwise, return a vector of length 30 containing the new edges that should be added. Each pair should contain two integers $a$ and $b$ ($0 \leq a,b \leq 999$, $a \neq b$), meaning that you want to add an edge between the nodes with index $a$ and $b$. In addition, after all edges have been added, there must not exist a pair of nodes with more than one edge between them.

Python: Your code should only contain the implementation of the following function:

• def run(edges)
  

  • The parameter edges is the graph. It is a list of lists and its length is between $3500$ and $4530$. Each inner list contains exactly two ints $a$ and $b$ ($0 \leq a,b \leq 999$, $a \neq b$), meaning that there is an edge between the nodes with index $a$ and $b$. Additionally, there will be at most one edge between any pair of vertices.

  • If you think you have already seen the graph before, return an empty list.
    Otherwise, return a list of lists of length 30 containing the new edges that should be added. Each inner list should contain two ints $a$ and $b$ ($0 \leq a,b \leq 999$, $a \neq b$), meaning that you want to add an edge between the nodes with index $a$ and $b$. Note that the each edge must be a list. If you give a tuple, you will receive a “Wrong Answer” verdict instead. In addition, after all edges have been added, there must not exist a pair of nodes with more than one edge between them.

It is important that your solution does not read or write from standard input/output. If your solution does this, you will likely get a strange error message.

Scoring

Your solution will be tested on 100 testcases. If you pass all of them, your solution will be accepted. The jury guarantees that there exists a solution that passes all testcases with very high probability.