두 사람을 만나게 하기

Mila와 Laura는 오랫동안 온라인 친구로 지냈지만 실제로 만난 적은 없다. 두 사람은 같은 오프라인 행사에 참가하고 있어서 반드시 만나게 된다. 그러나 두 사람이 묵는 호텔은 매우 넓고 복잡해서 며칠이 지나도 아직 마주치지 못했다.

호텔에는 $N$개의 방이 있으며 0번부터 $N-1$번까지 번호가 붙어 있다. 각 방에는 여러 색으로 바꿀 수 있는 조명이 있다. 전기 관리실을 찾았으므로 조명의 색을 바꿀 수 있다. 목표는 조명을 이용해 Mila와 Laura를 안내하여 두 사람이 만나게 하는 것이다.

호텔은 정점 $N$개(방)와 간선 $M$개(복도)로 이루어진 그래프이다. Mila와 Laura는 서로 다른 방에서 출발하지만, 어느 방인지는 알 수 없다. 이동은 여러 번 할 수 있다. 한 번의 이동에서는 정수 $N$개로 이루어진 목록 $c_0, c_1, \ldots, c_{N-1}$을 출력하며, 이는 모든 $i$에 대해 방 $i$의 조명 색을 $c_i$로 바꾼다는 뜻이다. 그러면 Mila와 Laura는 자신이 있는 방의 조명 색을 보고, 같은 색 조명이 켜진 이웃 방으로 걸어간다. 그런 방이 없으면 제자리에 머문다. 여러 개이면 임의로 하나를 고른다.

이동 중 두 사람이 같은 방에 있거나 같은 복도를 동시에 지나면 만나게 한 것으로 성공이다. 최대 $20\,000$번까지 이동할 수 있으며, 이동 횟수가 적을수록 높은 점수를 받는다.

출발 방과, 같은 색 방이 여럿일 때 두 사람이 고르는 방향은 알 수 없다. 해답은 출발 방이나 걷는 방식과 관계없이 항상 옳아야 한다.

첫 줄에 방의 수 $N$과 복도의 수 $M$이 정수로 주어진다.

이어지는 $M$개의 줄에는 각각 정수 $u_i$와 $v_i$가 주어지며, 방 $u_i$와 방 $v_i$가 복도로 연결되어 있다는 뜻이다.

첫 줄에 이동 횟수 $K$를 출력한다.

이어지는 $K$개의 줄에는 각각 정수 $N$개인 $c_0, c_1, \ldots, c_{N-1}$을 출력한다. 모든 $i$에 대해 $0 \le c_i \le N$이다. 이 $K$개의 줄은 시간 순서대로 적은 이동이다.

• $2 \leq N \leq 100$.
• $N-1 \leq M \leq \frac{N(N-1)}{2}$.
• $0 \leq u_i, v_i \leq N-1$이고 $u_i \neq v_i$이다.
• 모든 방에서 다른 모든 방으로 갈 수 있다. 자기 자신으로 가는 복도는 없으며, 같은 두 방을 잇는 복도가 여러 개 있지 않다.
• 이동은 최대 $20\,000$번까지 할 수 있다($K \leq 20\,000$).

예제는 길이가 $3$인 경로이므로 테스트 그룹 $3$, $4$, $5$ 중 하나에 속할 수 있다. 예제 출력에 따라 방의 조명을 칠하면 Mila와 Laura는 항상 만난다.

Mila가 0번 방에서, Laura가 1번 방에서 출발한다고 가정하자.

• 첫 번째 이동: Mila는 반드시 1번 방으로 가야 한다. Laura가 0번 방으로 가면 0번과 1번 사이 복도에서 만난다. 여기서는 Laura가 2번 방으로 간다고 하자.
• 두 번째 이동: Mila는 0번 방으로 돌아가고, Laura는 2번 방에 머문다.
• 세 번째 이동: Mila는 다시 1번 방으로 가고, Laura는 2번 방에 머문다.
• 네 번째 이동: Mila는 2번 방으로, Laura는 1번 방으로 가므로 1번과 2번 사이 복도에서 만난다.
• 다섯 번째 이동: Mila와 Laura가 자리를 바꾸며 다시 만나지만, 이미 만났으므로 상관없다.

아래 그림은 예제의 처음 네 번의 이동을 보여 준다.

이는 한 가지 경우일 뿐이다. 같은 이동 순서는 출발 방과 걷는 방식에 관계없이 항상 두 사람을 만나게 한다.