23073번 - Uuu 점수다국어

This molecule corresponds to the graph in the sample.

Unununium (Uuu) was the name of the chemical element with atom number 111, until it changed to Röntgenium (Rg) in 2004. These heavy elements are very unstable and have only been synthesized in a few laboratories.

You have just been hired by one of these labs to optimize the algorithms used in simulations. For example, when simulating complicated chemical reactions, it is important to keep track of how many particles there are, and this is done by counting connected components in a graph.

Currently, the lab has some Python code (see attachments) that takes an undirected graph and outputs the number of connected components. As you can see, this code is based on everyone's favourite data structure union-find.

After looking at the code for a while, you notice that it actually has a bug in it!  The code still gives correct answers, but the bug could cause it to run inefficiently. Your task is to construct a graph with a given number of vertices and edges where the code runs very slowly. We will count how many times the third line (the one inside the while loop) is visited, and your program will get a score according to this number.

The input consists of one line with two integers $N$ and $M$, the number of vertices and edges your graph should have. Apart from the sample, there will be only one test case, with $N = 100$ and $M = 500$.

The output consists of $M$ lines where the $i$:th contains two integers $u_i$ and $v_i$ ($1 \leq u_i, v_i \leq N$). This indicates that the vertices $u_i$ and $v_i$ are connected with an edge in your graph.

Your graph must not contain any duplicate edges or self-loops. That is, $u_i$ must be different from $v_i$ and all the sets $\{u_i, v_i\}$ must be distinct.

Let $X$ be the number of times the innermost while loop is visited when given your test case. Then your score will be $\min(X / 200, 100)$.

You will not get any points for the sample test case.

In the sample case, the output contains a graph that causes the innermost loop to be visited $20$ times. Run the code and see for yourself!

• unununion_find.py