Background

Day 2 Problem D.

The statement is translated from EGOI2024 makethemmeet. The translation comes from ChatGPT and has been manually proofread. If there are any mistakes, please contact rui_er。

Warning: Abusing the judge for this problem will result in an account ban.

Problem Description

Mila and Laura have been friends online for a long time, but they have never met in real life. Now they are both attending the same live event, which means they will definitely meet. However, the hotel they are staying in is very large and complicated. So after several days, they still have not run into each other.

The hotel consists of $N$ rooms, numbered from $0$ to $N - 1$. Each room has a lamp whose color can be changed. You have found the hotel's electrical service room, which allows you to change the colors of the lamps. Your goal is to use these lamps to guide Mila and Laura so that they eventually meet.

The hotel can be represented as a graph with $N$ vertices (rooms) and $M$ edges (corridors connecting rooms). Mila and Laura initially start in two different rooms, but you do not know which rooms. You may perform several moves. Each move consists of printing a list $c_0,c_1,\cdots,c_{N-1}$ of $N$ integers, meaning that the lamp in room $i$ becomes color $c_i$, where $i = 0, 1,\cdots, N - 1$. Then Mila and Laura will look at the color of the lamp in their current room, and walk to an adjacent room whose lamp has the same color. If there is no such adjacent room, they will stay where they are. If there are multiple such adjacent rooms, they will choose one arbitrarily.

If during your moves, Mila and Laura are in the same room, or they use the same corridor at the same time, then you have successfully made them meet. You may make at most $2\times 10^4$ moves, but if you use fewer moves, your score will be higher.

Note that you do not know which rooms Mila and Laura start in, and you also do not know how they will choose when they have multiple same-colored options. Your solution must be correct no matter what their starting rooms are, and no matter how they move.

Input Format

The first line contains two integers $N$ and $M$, representing the number of rooms and the number of corridors.

The next $M$ lines each contain two integers $u_i$ and $v_i$, indicating that rooms $u_i$ and $v_i$ are connected by a corridor.

Output Format

Output one line with an integer $K$, the number of moves.

In the next $K$ lines, output $N$ integers $c_0,c_1,\cdots,c_{N-1}$ each line, where for all $i$ we have $0 \le c_i \le N$. These $K$ lines represent your moves in chronological order.

3 2
0 1
1 2

5
2 2 2
2 2 3
2 2 3
1 2 2
1 2 2

Hint

Sample Explanation

In the sample, the graph is a path of length $3$, so it could belong to test group $3$, $4$, or $5$. If the room lamps are colored according to the sample output, then Mila and Laura will always meet.

For example, suppose Mila starts in room $0$ and Laura starts in room $1$:

• Step 1: Mila must walk to room $1$. If Laura walks to room $0$, then they will meet on the corridor between $0$ and $1$. Assume Laura walks to room $2$.
• Step 2: Mila walks back to room $0$, and Laura stays in room $2$.
• Step 3: Mila walks to room $1$ again, and Laura stays in room $2$.
• Step 4: Mila walks to room $2$, and Laura walks to room $1$. Then they will meet on the corridor between rooms $1$ and $2$.
• Step 5: Mila and Laura swap positions and meet again (but this does not matter, because they have already met).

The figure below shows the first four steps of the sample.

Note that this is only the case where they start from rooms $0$ and $1$. You can verify that no matter where they start and how they walk, the same sequence of moves guarantees that they meet.

---

Constraints

For all data, $2\le N\le 100$, $N-1\le M\le \frac{N(N-1)}{2}$, $0\le u_i,v_i\le N-1$, and $u_i\ne v_i$. It is guaranteed that every room is reachable from every other room, that there is no corridor connecting a room to itself, and that there are no multiple corridors connecting the same pair of rooms. You may use at most $2\times 10^4$ steps (i.e., $K\le 2\times 10^4$).

• Subtask 1 (at most $10$ points): $M=N-1$, and the corridors are $(0,1),(0,2),(0,3),\cdots,(0,N-1)$. That is, the graph is a star.
• Subtask 2 (at most $13$ points): $M=\frac{N(N-1)}{2}$, meaning there is a corridor between every pair of rooms. That is, the graph is complete.
• Subtask 3 (at most $11$ points): $M=N-1$, and the corridors are $(0,1),(1,2),(2,3),\cdots,(N-2,N-1)$. That is, the graph is a path.
• Subtask 4 (at most $36$ points): $M=N-1$. That is, the graph is a tree.
• Subtask 5 (at most $30$ points): No additional constraints.

Note: Some test points were placed into multiple subtasks in EGOI. To save judging resources and reduce the workload of organizing the testdata, these test points are placed into the subtask with the smallest index among all subtasks that contain them. This may cause a solution to get a higher score than expected, but it still cannot pass the problem.

---

Scoring

For each subtask that your program solves correctly, you will receive a score according to the following formula:

$$\textrm{score}=\left\lfloor S_g\cdot\min\left(1,\frac{2000}{K_g+1900}+\frac{1}{5}\right)\right\rfloor$$

Here $S_g$ is the full score of the subtask, and $K_g$ is the maximum number of steps used by your program among all test points in this subtask. This means that to get full score, you need to solve each test point in at most $600$ steps. The figure below shows the score as a function of $K_g$.

Translated by ChatGPT 5