acm International Collegiate Programming Contest

Links

A B C D E F G H I

Problem I

橋の建造計画 2

N 個の小島からなる国があり,国民はそれらの島に住んでいる.島から島へ渡るにはフェリーを使うしかなく,多くの国民は不便に感じている.そこで国王は国民の意見を聞いて橋を架けることにした.

国王のもとに,国民から「島 u と島 v の間を直接結ぶ双方向に渡れる橋を架けてほしい.」という形の意見が全部で M 個届いた.資金は潤沢にあるので,これらちょうど M 本の橋を架ける計画を立てることにした.

あとはそれぞれの橋について建造を担当する建設会社を決定するだけだが,ここで一つ問題があった.この国には数多くの建設会社が存在するが,その中には,橋の耐久性に問題がある,納期を超過する,などの様々な問題を抱える会社があるらしい.残念ながら問題を抱える会社の特定はできなかったので,リスク分散と各会社との連絡コストとを天秤にかけ,以下の条件を満たすような建設会社の割り当てを考えることにした.

  • 条件
    • 各建設会社について,その会社が建造を担当する全ての橋が通れない状態でも,それ以外の橋を使いすべての島を互いに行き来することができる.
    • その上で,仕事を依頼する(1 本以上の橋の建造を担当する)建設会社の数が最小である.

あなたの仕事は,上の条件を満たすような建設会社の割り当てを実際に求めることである.

Input

入力は 40 個以下のデータセットからなる.各データセットは次の形式で表される.

N M u1 v1  ⋮ uM vM

1 行目には 2 つの整数 N および M が与えられる.N はこの国の島の数であり,2 ≤ N ≤ 150 を満たす.M は国民からの意見の総数であり,N-1 ≤ M ≤ 1500 を満たす.

続く M 行には,M 個の国民からの意見の情報が与えられる.このうち i 番目の行には整数 ui, vi が与えられ,i 番目の意見が「島 ui と島 vi の間を直接結ぶ双方向に渡れる橋を架けてほしい.」というものであることを表す.1 ≤ ui ≤ N および 1 ≤ vi ≤ N および ui ≠ vi を満たすことが保証される.また,i ≠ j ならば { ui, vi } ≠ { uj, vj } を満たすことが保証される.また,M 個の国民からの意見を叶えるように M 本の橋を架けた際,それらの橋を使用してすべての島を互いに行き来することが可能なことが保証される.

入力の終わりは 2 つのゼロからなる行で表される.

Output

各データセットに対し,もし条件を満たすような建設会社の割り当て方法がない場合,-1 と一行に出力せよ.そうでない場合の出力は 2 行となる.まず 1 行目に仕事を依頼する(1 本以上の橋の建造を担当する)建設会社の数 K を出力せよ.そして 2 行目に M 個の整数を空白区切りで出力せよ.そのうち i 番目の整数は,i 番目の意見に対応する橋 (ui, vi) の建造を担当する建設会社の番号であり,1 以上 K 以下の整数である必要がある.

条件を満たす解が複数存在するならば,そのうちどれを出力してもよい.

Sample Input

3 3
1 2
2 3
1 3
3 2
1 2
1 3
4 5
1 2
2 3
3 4
4 1
1 3
0 0

Sample Output

3
2 3 1
-1
3
2 3 2 1 1
(End of Problem I) A B C D E F G H I