$N$ 個の頂点と $M$ 本の辺からなる無向単純連結グラフが与えられる。 グラフの頂点には $1$ から $N$ までの番号が、辺には $1$ から $M$ までの番号がそれぞれ付けられている。辺 $i$ は頂点 $u_i$ と頂点 $v_i$ を結んでいる。

このグラフには以下の特別な性質がある：すべての辺 $i$ ($1 \le i \le M$) に対して、その辺を含まない $u_i$ と $v_i$ を結ぶパスが存在する。このようなパスを辺 $i$ の「バイパス」と呼ぶ。同じ辺に対して複数のバイパスが存在する場合がある。

辺を $1$ から $M$ までの番号で表される色で塗り分ける。すべての辺にちょうど一つの色を割り当てるものとする。使われない色があってもよく、同じ色が複数回使われてもよい。 以下の性質を満たすとき、この辺の塗り方を「興味深い」塗り方と呼ぶ：

• 共通の頂点を持つ2つの辺は、異なる色で塗られている。
• すべての辺に対して、「特別なバイパス」が存在する。特別なバイパスとは、使用されている色の種類数が $8$ 種類以下であるようなバイパスのことである。

あなたのタスクは、興味深い塗り方を一つ見つけ、それぞれの $M$ 本の辺について、その辺の特別なバイパスを構成するために使用できる色の集合を出力することである。 上記の制約下では、少なくとも一つの興味深い塗り方が存在することが示せる。

入力

入力の最初の行には、2つの整数 $N$ と $M$ ($3 \le N \le 5555, 3 \le M \le \min(N(N - 1)/2, 9999)$) が含まれる。 続く $M$ 行の各行は $i$ 番目の辺を表し、2つの整数 $u_i$ と $v_i$ ($1 \le u_i < v_i \le N$) が含まれる。 各ペア $(u, v)$ はリストに高々一度しか現れず、与えられたグラフは連結であり、任意の辺 $(u, v)$ を取り除いても $u$ と $v$ を結ぶバイパスが存在すると仮定してよい。

出力

興味深い塗り方を以下の形式で出力せよ。 最初の行に、$M$ 個の整数を出力する。$i$ 番目の整数 $C_i$ は、$i$ 番目の辺の色 ($1 \le C_i \le M$) でなければならない。 続いて $M$ 行を出力する。$i$ 番目の行は、辺 $i$ の特別なバイパスのための色の集合を表す。この行は、リストに含まれる色の数 $k_i$ ($1 \le k_i \le 8$) で始まり、その後に $1$ から $M$ までの相異なる $k_i$ 個の整数（色のリスト）が続く必要がある。色の順序は任意である。リストに含まれる色以外の色を使用しない、$u_i$ と $v_i$ を結ぶ特別なバイパスが存在しなければならない。なお、これは色のリストが最小である必要はないことを意味し、リストの一部のみを使用して構成されるパスが存在してもよい。判定プログラムは、リストされた色が十分であることのみを確認する。

入出力例

入力 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

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

注記

例において、最初の辺には2つのバイパスが存在する。 長い方のバイパスは9種類の色（2から10）を含んでいるため、特別ではない。 短い方のバイパスは辺2, 3, 11（色2, 3, 5）で構成されているため、特別である。