Problem D
Make Them Meet

Mila and Laura have been friends online for a long time; they have never met in real life. Currently, they are both attending the same onsite event, which means that they will surely meet. However, the hotel where they both are staying is very big and confusing. Therefore, after several days, they still have not run into each other.

The hotel consists of $N$ rooms, numbered $0$ to $N-1$. Each room has a lamp that can be changed into different colours. You have found the electrical service room of the hotel, allowing you to alter the colours of the lamps. Your goal is to guide Mila and Laura using the lamps to finally make them meet.

The hotel can be represented as a graph with $N$ vertices (the rooms) and $M$ edges (the corridors connecting the rooms). Mila and Laura initially start in two different rooms but you do not know which ones. You can make a number of moves. Each move consists of printing a list of $N$ integers, $c_0, c_1, \ldots , c_{N-1}$, meaning that the colour of the lamp in room $i$ becomes $c_ i$ for every $i = 0,1,\ldots ,N-1$. Mila and Laura will then look at the colour of the lamp in the room they are currently in and walk to a neighbouring room whose lamp has the same colour. If there is no such neighbouring room, they will stay where they are. If there are several such neighbouring rooms, they will choose one arbitrarily.

If Mila and Laura are in the same room or use the same corridor simultaneously at any point during your moves, you have succeeded in making them meet. You can make at most $20\, 000$ moves, but you will get a higher score if you use fewer moves.

Note that you do not know which rooms Mila and Laura start in or how they walk if they have multiple rooms with the same colour to choose from. Your solution must be correct regardless of their starting rooms or how they walk.

Input

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

The following $M$ lines each contain two integers, $u_ i$ and $v_ i$, meaning that rooms $u_ i$ and $v_ i$ are connected by a corridor.

Output

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

On each of the following $K$ lines, print $N$ integers, $c_0, c_1, \ldots , c_{N-1}$, such that $0\le c_ i\le N$ for all $i$. These $K$ lines represent your moves in the chronological order.

Constraints and Scoring

• $2 \leq N \leq 100$.

• $N-1 \leq M \leq \frac{N(N-1)}{2}$.

• $0 \leq u_ i, v_ i \leq N-1$, and $u_{i}\neq v_{i}$.

• You can reach every room from every other room. Furthermore, there are no corridors going from a room to itself, and there are not multiple corridors between any pair of rooms.

• You may use at most $20\, 000$ moves (that is, $K\le 20\, 000$).

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group, you need to solve all test cases in the test group.

For every test group that your program solves correctly, you will receive a score based on the following formula:

where $S_ g$ is the max score for the test group and $K_ g$ is the maximum number of moves that your solution used for any test case in the test group. This means that in order to get full score, you need to use at most $600$ moves in all of the test cases. The plot below shows the number of points, as a function of $K_ g$.

Example

The sample case is a path of length $3$, so it could belong to test groups $3$, $4$, or $5$. If the lamps of the rooms are coloured according to the sample output, then Mila and Laura will always meet.

For example, let us assume that Mila starts in room $0$ and Laura starts in room $1$:

• First move: Mila must walk to room $1$. If Laura walks to room $0$, then they will meet in the corridor between $0$ and $1$. Let us say that Laura walks to room $2$ instead.

• Second move: Mila walks back to room $0$ and Laura stays in room $2$.

• Third move: Mila walks to room $1$ again and Laura stays in room $2$.

• Fourth move: Mila walks to room $2$ and Laura walks to room $1$. Thus, they will meet on the corridor between rooms $1$ and $2$.

• Fifth move: Mila and Laura swaps places and meet again (but it does not matter since they already met).

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

Note that this was only the case where the friends start in the rooms $0$ and $1$. One can verify that the same sequence of moves ensures that they will meet, regardless of where they start and how they walk.

3 2
0 1
1 2

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