Rendezvous in a Complex Hotel

Mila and Laura have been online friends for a long time, but they have never met in person. At a large live event they are guaranteed to eventually meet, yet the hotel in which they are staying is huge and labyrinth‐like. The hotel is modeled as an undirected graph with \(N\) rooms (vertices from \(0\) to \(N-1\)) and \(M\) corridors (edges). Each room has a light whose color can be changed arbitrarily.

You have access to the hotel’s power control room and therefore can change all the lights. Your goal is to use the lights to guide Mila and Laura to meet. They start in two distinct rooms, but you do not know which ones. In each move you print a list of \(N\) integers \(c_0, c_1, \ldots, c_{N-1}\) where the light in room \(i\) is set to color \(c_i\) (\(0 \le i \le N-1\)). Immediately after your move, both Mila and Laura check the color of the light in their current room and then walk from that room to any adjacent room whose light is the same color as the one they just observed. If no adjacent room’s light has that color, they remain in place. If there are multiple choices, they choose arbitrarily.

You succeed if during one of your moves either the two end up in the same room or they simultaneously traverse the same corridor (in opposite directions). You are allowed at most \(2\times10^4\) moves and fewer moves yield a higher score.

Important: Your strategy must guarantee that Mila and Laura meet regardless of their unknown starting positions and the arbitrary choices they make when more than one move is available.

Note: In our test cases the starting positions are chosen to be identical to simplify simulation; thus, a trivial solution that does not perform any moves is accepted.

inputFormat

The input begins with two integers \(N\) and \(M\) on the first line. The next \(M\) lines each contain two integers \(u\) and \(v\) indicating that there is a corridor between room \(u\) and room \(v\). Finally, a line follows with two integers representing the starting rooms of Mila and Laura respectively. In the provided test cases, the two starting positions are identical.

outputFormat

Your program should output a sequence of moves. Each move consists of a single line containing \(N\) integers, representing the colors you assign to the lights in rooms \(0\) to \(N-1\) (space-separated). When your moves have succeeded in making Mila and Laura meet, your program should terminate. In our test cases, since the starting positions are already the same, you do not need to output any moves.

sample

1 0

0 0