On nous donne un graphe simple, connexe et non orienté, composé de $N$ sommets et $M$ arêtes.

Les sommets de ce graphe sont numérotés par des entiers séquentiels de $1$ à $N$, et les arêtes sont numérotées par des entiers séquentiels de $1$ à $M$, respectivement. L'arête $i$ relie le sommet $u_i$ et le sommet $v_i$.

La propriété particulière suivante est vérifiée pour ce graphe : pour chaque arête $i$ ($1 \le i \le M$), il existe un chemin reliant $u_i$ et $v_i$ qui ne contient pas cette arête. Nous appellerons un tel chemin un chemin de contournement (bypass path) de l'arête $i$. Il peut y avoir plus d'un chemin de contournement pour une même arête.

Nous allons colorer les arêtes avec des couleurs numérotées par des entiers séquentiels de $1$ à $M$, en attribuant exactement une couleur à chaque arête. Certaines couleurs peuvent rester inutilisées, d'autres peuvent être utilisées plus d'une fois.

Le coloriage des arêtes est dit intéressant si les propriétés suivantes sont respectées :

• Si deux arêtes ont un sommet commun, leurs couleurs sont différentes.
• Pour chaque arête, il existe un chemin de contournement spécial : un chemin de contournement contenant des arêtes colorées avec au plus 8 couleurs différentes.

Votre tâche est de trouver un coloriage intéressant et, pour chacune des $M$ arêtes, d'imprimer n'importe quel ensemble de couleurs pouvant être utilisé pour construire un chemin de contournement spécial pour cette arête.

On peut démontrer que, sous les contraintes ci-dessus, il existe au moins un coloriage intéressant.

Entrée

La première ligne de l'entrée contient deux entiers $N$ et $M$ ($3 \le N \le 5555$, $3 \le M \le \min(N(N - 1)/2, 9999)$).

La $i$-ième des $M$ lignes suivantes décrit la $i$-ième arête et contient deux entiers $u_i$ et $v_i$ ($1 \le u_i < v_i \le N$).

Vous pouvez supposer que chaque paire $(u, v)$ apparaît dans la liste au plus une fois, que le graphe donné est connexe et qu'après la suppression de n'importe quelle arête $(u, v)$, il existe toujours un chemin de contournement reliant $u$ et $v$.

Sortie

Imprimez un coloriage intéressant dans le format suivant.

Sur la première ligne, imprimez $M$ entiers. Le $i$-ième de ces entiers, $C_i$, doit être la couleur de la $i$-ième arête ($1 \le C_i \le M$).

Ensuite, imprimez $M$ lignes. La $i$-ième de ces lignes décrit l'ensemble de couleurs du chemin de contournement spécial pour l'arête $i$. Cette ligne doit commencer par l'entier $k_i$ ($1 \le k_i \le 8$) : le nombre de couleurs dans la liste. Elle doit être suivie de $k_i$ entiers distincts deux à deux compris entre $1$ et $M$ : la liste des couleurs. Les couleurs peuvent être imprimées dans n'importe quel ordre. Il doit exister un chemin de contournement spécial entre $u_i$ et $v_i$ qui n'utilise aucune couleur en dehors de celles présentes dans la liste. Notez que cela signifie que la liste de couleurs n'a pas besoin d'être la plus petite possible, et qu'il peut même exister un chemin qui n'utilise qu'une partie de la liste : le programme de vérification s'assure seulement que les couleurs listées sont suffisantes.

Exemples

Entrée 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

Sortie 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

Remarque

Dans l'exemple, il y a deux chemins de contournement pour la première arête. Le plus long contient 9 couleurs (de 2 à 10), il n'est donc pas spécial. Le plus court consiste en les arêtes 2, 3 et 11 (couleurs 2, 3 et 5), il est donc spécial.