/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
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 つずつ求めてください。（出力方法が特殊なので、詳しくは出力を見てください。）
下記の制約のもとで、このような塗り方は必ず存在することが示せます。
制約
- 3 \le N \le 5555
- 3 \le M \le \min(N(N-1)/2, 9999)
- 1 \le u_i < v_i \le N
- 1 \le i < j \le N に対して、(u_i, v_i) \neq (u_j, v_j)
- 与えられるグラフは連結である。
- どの辺 i (1 \le i \le M) についても、頂点 u_i と v_i を結ぶパスで、辺 i を使わないものが存在する。
部分点
- N \le 111 かつ M \le 222 を満たすデータセットに正解した場合は、10 点が与えられる。
- 追加制約のないデータセットに正解した場合は、上記とは別に 390 点が与えられる。
入力
入力は以下の形式で標準入力から与えられる。
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 は、(※) を満たす迂回パスに使われない色を含んでいてもよい。
入力例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
辺 1 の迂回パスとして、辺 2 から辺 10 までの辺を使うものがありますが、これらの辺に使われている色は、色 2 から色 10 までの 9 種類なので、このパスは問題文の条件 (※) を満たしません。
しかし、辺 1 の迂回パスとして、辺 2, 3, 11 を使うものがあります。これらの辺に使われている色は、色 2, 3, 5 の 3 種類なので、このパスは問題文の条件 (※) を満たします。