時間制限:1000ミリ秒
メモリ制限:10000KB
チームにしなさいっ!
問題
あなたの仕事は、何人かの人間を2つのチームに分割することである。条件は:
- 誰もが1つのチームに属す。
- どちらのチームも最低1人はメンバーがいる。
- チーム内のどのような2人も互いを知る。
- 2つのチームのメンバーの数はできるだけ近くする。
この問題は複数の解を持ちうる。あなたはそのいづれを出力してもかまわない。もし解が存在しない場合は、そのことを出力すること。
入力
簡単のため、全ての人間が1からNの整数で番号づけられる。
入力の最初の行は、これからチームに分割したい人間の総数をあらわす整数N(2 <= N <= 100)が書かれている。続くN行には、それぞれの人間についての情報が順番に書いてある。各行は互いに異なる数Aij(1 <= Aij <= N, Aij != i)のリストが空白を区切りとして書かれている。このリストは、その人間がどの人間を知っているかを表す。リストの終了は0で示される。
出力
もし問題に対する答えが存在しないのならば、1つのメッセージ"No solution"(引用符は出力しなくてよい)を出力すること。もし答が存在するなら答えを2行で出力せよ。出力の最初の行は、最初のチームに配属された人間の番号のリストが、空白を区切りとして書かれている。続く行には、同様にして次のチームのメンバーを出力すること。チームやメンバーの番号は任意の順番で出力してよい。
入力例
5 2 3 5 0 1 4 5 3 0 1 2 5 0 1 2 3 0 4 3 2 1 0
出力例
3 1 3 5 2 2 4
出典
Northeastern Europe 2001