Se nos da un grafo conexo simple no dirigido, que consta de $N$ vértices y $M$ aristas.

Los vértices de este grafo están enumerados mediante enteros secuenciales del 1 al $N$, y las aristas están enumeradas mediante enteros secuenciales del 1 al $M$, respectivamente. La arista $i$ conecta el vértice $u_i$ y el vértice $v_i$.

La siguiente propiedad especial se cumple para este grafo: para cada arista $i$ ($1 \le i \le M$), existe un camino que conecta $u_i$ y $v_i$ que no contiene esta arista. Llamaremos a dicho camino un camino de derivación (bypass path) de la arista $i$. Puede haber más de un camino de derivación para la misma arista.

Colorearemos las aristas con colores enumerados mediante enteros secuenciales del 1 al $M$, asignando exactamente un color a cada arista. Algunos colores pueden quedar sin usar, otros pueden usarse más de una vez.

El coloreado de las aristas se denomina interesante si se cumplen las siguientes propiedades:

• Si dos aristas tienen un vértice común, sus colores son diferentes.
• Para cada arista, existe un camino de derivación especial: un camino de derivación que contiene aristas coloreadas con no más de 8 colores diferentes.

Tu tarea es encontrar un coloreado interesante y, para cada una de las $M$ aristas, imprimir cualquier conjunto de colores que pueda utilizarse para construir un camino de derivación especial para esa arista.

Se puede demostrar que, bajo las restricciones anteriores, existe al menos un coloreado interesante.

Entrada

La primera línea de la entrada contiene dos enteros $N$ y $M$ ($3 \le N \le 5555$, $3 \le M \le \min(N(N - 1)/2, 9999)$).

La $i$-ésima de las $M$ líneas siguientes describe la $i$-ésima arista y contiene dos enteros $u_i$ y $v_i$ ($1 \le u_i < v_i \le N$).

Puedes asumir que cada par $(u, v)$ aparece en la lista como máximo una vez, que el grafo dado es conexo y que, tras la eliminación de cualquier arista $(u, v)$, todavía existe un camino de derivación que conecta $u$ y $v$.

Salida

Imprime cualquier coloreado interesante en el siguiente formato.

En la primera línea, imprime $M$ enteros. El $i$-ésimo de estos enteros, $C_i$, debe ser el color de la $i$-ésima arista ($1 \le C_i \le M$).

Luego imprime $M$ líneas. La $i$-ésima de estas líneas describe el conjunto de colores del camino de derivación especial para la arista $i$. Esta línea debe comenzar con el entero $k_i$ ($1 \le k_i \le 8$): el número de colores en la lista. Debe ir seguido de $k_i$ enteros distintos entre sí entre 1 y $M$: la lista de colores. Los colores pueden imprimirse en cualquier orden. Debe existir un camino de derivación especial entre $u_i$ y $v_i$ que no utilice ningún color excepto los colores de la lista. Ten en cuenta que esto significa que la lista de colores no tiene por qué ser la mínima posible, e incluso puede haber un camino que utilice solo una parte de la lista: el programa de verificación solo se asegura de que los colores listados sean suficientes.

Ejemplos

Ejemplos 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

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

Nota

En el ejemplo, hay dos caminos de derivación para la primera arista. El más largo contiene 9 colores (del 2 al 10), por lo que no es especial. El más corto consiste en las aristas 2, 3 y 11 (colores 2, 3 y 5), por lo que es especial.