Dany jest nieskierowany, spójny graf prosty, składający się z $N$ wierzchołków i $M$ krawędzi.

Wierzchołki tego grafu są ponumerowane kolejnymi liczbami całkowitymi od $1$ do $N$, a krawędzie odpowiednio od $1$ do $M$. Krawędź $i$ łączy wierzchołek $u_i$ oraz wierzchołek $v_i$.

Dla tego grafu zachodzi następująca szczególna własność: dla każdej krawędzi $i$ ($1 \le i \le M$) istnieje ścieżka łącząca $u_i$ i $v_i$, która nie zawiera tej krawędzi. Taką ścieżkę nazywamy ścieżką obejściową (ang. bypass path) krawędzi $i$. Dla tej samej krawędzi może istnieć więcej niż jedna ścieżka obejściowa.

Pokolorujemy krawędzie kolorami oznaczonymi kolejnymi liczbami całkowitymi od $1$ do $M$, przypisując dokładnie jeden kolor każdej krawędzi. Niektóre kolory mogą pozostać nieużyte, inne mogą być użyte więcej niż raz.

Kolorowanie krawędzi nazywamy interesującym, jeśli spełnione są następujące właściwości: Jeśli dwie krawędzie mają wspólny wierzchołek, ich kolory są różne. Dla każdej krawędzi istnieje specjalna ścieżka obejściowa: ścieżka obejściowa zawierająca krawędzie pokolorowane nie więcej niż 8 różnymi kolorami.

Twoim zadaniem jest znalezienie interesującego kolorowania oraz, dla każdej z $M$ krawędzi, wypisanie dowolnego zbioru kolorów, których można użyć do zbudowania specjalnej ścieżki obejściowej dla tej krawędzi.

Można wykazać, że przy powyższych ograniczeniach istnieje co najmniej jedno interesujące kolorowanie.

Wejście

Pierwsza linia wejścia zawiera dwie liczby całkowite $N$ oraz $M$ ($3 \le N \le 5555$, $3 \le M \le \min(N(N - 1)/2, 9999)$). Kolejne $M$ linii opisuje krawędzie, gdzie $i$-ta linia zawiera dwie liczby całkowite $u_i$ oraz $v_i$ ($1 \le u_i < v_i \le N$).

Możesz założyć, że każda para $(u, v)$ pojawia się na liście co najwyżej raz, że dany graf jest spójny oraz że po usunięciu dowolnej krawędzi $(u, v)$ nadal istnieje ścieżka obejściowa łącząca $u$ i $v$.

Wyjście

Wypisz dowolne interesujące kolorowanie w następującym formacie:

W pierwszej linii wypisz $M$ liczb całkowitych. $i$-ta z tych liczb, $C_i$, musi być kolorem $i$-tej krawędzi ($1 \le C_i \le M$).

Następnie wypisz $M$ linii. $i$-ta z tych linii opisuje zbiór kolorów specjalnej ścieżki obejściowej dla krawędzi $i$. Linia ta musi zaczynać się od liczby całkowitej $k_i$ ($1 \le k_i \le 8$): liczby kolorów na liście. Następnie musi po niej następować $k_i$ parami różnych liczb całkowitych z zakresu od $1$ do $M$: lista kolorów. Kolory mogą być wypisane w dowolnej kolejności. Musi istnieć specjalna ścieżka obejściowa między $u_i$ i $v_i$, która nie używa żadnych kolorów poza kolorami z listy. Zauważ, że oznacza to, iż lista kolorów nie musi być minimalna możliwa i może istnieć ścieżka, która używa tylko części listy: program sprawdzający upewnia się jedynie, że wymienione kolory są wystarczające.

Przykład

Wejście 1

10 11
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
1 10
1 4

Wyjście 1

1 2 3 4 5 6 7 8 9 10 5
3 2 3 5
3 1 3 5
3 1 2 5
6 5 6 7 8 9 10
7 4 5 6 7 8 9 10
6 4 5 7 8 9 10
6 4 5 6 8 9 10
6 4 5 6 7 9 10
6 4 5 6 7 8 10
8 4 5 6 7 8 9 1 2
3 1 2 3

Uwagi

W przykładzie dla pierwszej krawędzi istnieją dwie ścieżki obejściowe. Dłuższa z nich zawiera 9 kolorów (od 2 do 10), więc nie jest specjalna. Krótsza składa się z krawędzi 2, 3 i 11 (kolory 2, 3 i 5), więc jest specjalna.