AT_kupc2020_i Coloring Paths

[problemUrl]: https://atcoder.jp/contests/kupc2020/tasks/kupc2020_i $ N $ 頂点 $ M $ 辺の無向単純連結グラフがあります。 このグラフの頂点には $ 1 $ から $ N $ までの番号がついていて、辺には $ 1 $ から $ M $ までの番号がついています。 辺 $ i\ (1\ \le\ i\ \le\ M) $ は頂点 $ u_i $ と頂点 $ v_i $ を結んでいます。 このグラフには、次のような特別な性質があります。 - どの辺 $ i\ (1\ \le\ i\ \le\ M) $ についても、頂点 $ u_i $ と $ v_i $ を結ぶパスで、辺 $ i $ を使わないものが存在する。 このようなパスを「辺 $ i $ の迂回パス」と呼ぶことにします。$ 1 $ つの辺の迂回パスは複数存在するかもしれません。 グラフの各辺を、色 $ 1 $ から色 $ M $ までの $ M $ 個の色のうちの $ 1 $ つを選んで塗ることにします。このとき、次の条件を満たさなければなりません。 - 同じ頂点に接続している $ 2 $ つの辺は、異なる色で塗られていなければならない。 - どの辺についても、その辺の迂回パスで、次を満たすものが少なくとも $ 1 $ つ存在している。 - パスが含むすべての辺に使われている色は $ 8 $ 種類以下である。(※) このような色の塗り方を $ 1 $ つ求めてください。 さらに、そのように色を塗ったグラフの各辺について、上の (※) を満たす迂回パスを $ 1 $ つずつ求めてください。（出力方法が特殊なので、詳しくは出力を見てください。） 下記の制約のもとで、このような塗り方は必ず存在することが示せます。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ u_1 $ $ v_1 $ $ u_2 $ $ v_2 $ $ \vdots $ $ u_M $ $ v_M $

条件を満たす色の塗り方を $ 1 $ つ求め、以下の形式で出力せよ。 $ 1 $ 行目には、辺 $ i\ (1\ \le\ i\ \le\ M) $ に塗る色 $ C_i $ を空白区切りで出力せよ。 $ i\ +\ 1 $ 行目 $ (1\ \le\ i\ \le\ M) $ には、次を満たす色の集合 $ T_i $ を $ 1 $ つ出力せよ。 - $ 1\ \le\ |T_i|\ \le\ 8 $ - $ T_i $ に **含まれない** 色の辺と、辺 $ i $ をグラフから取り除いても、頂点 $ u_i,\ v_i $ は連結である。 $ T_i $ のサイズ $ |T_i| $ と、$ T_i $ に **含まれる** 色 $ D_{i,j}\ (1\ \le\ j\ \le\ |T_i|) $ をすべて出力せよ。 なお $ T_i $ の存在と、問題文の (※) を満たす辺 $ i $ の迂回パスの存在は同値である。 > $ C_1 $ $ C_2 $ $ \ldots $ $ C_M $ $ |T_1| $ $ D_{1,1} $ $ D_{1,2} $ $ \ldots $ $ D_{1,|T_1|} $ $ |T_2| $ $ D_{2,1} $ $ D_{2,2} $ $ \ldots $ $ D_{2,|T_2|} $ $ \vdots $ $ |T_M| $ $ D_{M,1} $ $ D_{M,2} $ $ \ldots $ $ D_{M,|T_M|} $ ここで、出力は次の条件を満たさなければならない。 - $ 1\ \le\ C_i\ \le\ M\ (1\ \le\ i\ \le\ M) $ - $ 1\ \le\ |T_i|\ \le\ 8\ (1\ \le\ i\ \le\ M) $ - $ 1\ \le\ D_{i,j}\ \le\ M\ (1\ \le\ i\ \le\ M,\ 1\ \le\ j\ \le\ |T_i|) $ - $ D_{i,j}\ =\ D_{i,k} $ なる $ j\ \ne\ k $ は存在しない。 - 辺 $ i $ と、$ T_i $ に含まれない色の辺をグラフから取り除いても、頂点 $ u_i,\ v_i $ は連結である。$ (1\ \le\ i\ \le\ M) $ - $ C_i $ および $ D_{i,j} $ は整数である。 これらの条件を満たす出力は、すべて正答となる。 **特に $ T_i $ は、(※) を満たす迂回パスに使われない色を含んでいてもよい。**

### 制約 - $ 3\ \le\ N\ \le\ 5555 $ - $ 3\ \le\ M\ \le\ \min(N(N-1)/2,\ 9999) $ - $ 1\ \le\ u_i\