B - B 問題 /

Time Limit: 2 sec / Memory Limit: 256 MB

この問題は、暫定ランキングではペナルティ表示がありますが、最終ランキングではペナルティはありません。
提出回数・提出時間は最終ランキングに影響しないため、コンテスト終了時間ギリギリまで何度でも提出してください。

問題文

自己辺や多重辺を含まない無向グラフが与えられます。
このグラフから K 個の頂点を互いに隣接しないように選び、それを出力してください。


入力

入力は以下の形式で標準入力から与えられる。

V E K
a_1 b_1
a_2 b_2
:
a_E b_E
  • 1 行目には与えられるグラフの頂点の数 V ( 1 \leq V \leq 100 ) と辺の数 E ( 0 \leq E \leq 4950 ) と K ( 1 \leq K \leq V ) が空白区切りで与えられる。
  • 1 行目には与えられるグラフの頂点の数 V ( 1 \leq V \leq 20 ) と辺の数 E ( 0 \leq E \leq 190 ) と K ( 1 \leq K \leq V ) が空白区切りで与えられる。
  • 続く E 行には i 番目の辺がつなぐ頂点の番号 a_ib_i ( 0 \leq{} a_i,\ b_i \leq{} V-1 ) が空白区切りで与えられる。
  • 与えられるグラフは自己辺や多重辺を含まない。
  • 条件を満たす頂点の選び方が存在することは保証される。
  • V \leq 20, E \leq 190 の入力に対して正答すると AC となる。

出力

選んだ K 個の頂点の、頂点の番号を K 行に出力せよ。

配点

この問題の得点は、コンテスト開催時間終了後に以下の操作が行われて確定する。
コンテスト開催時間中に Text (cat) において AC となった他の本戦参加者の A 問題の提出のうち、各参加者の最後の提出を、その参加者の A 問題の本提出とする。
コンテスト開催時間中に AC となったあなたの B 問題の提出のうち、最後の提出を、あなたの B 問題の本提出とする。
B 問題の本提出を行うと、10 点が与えられる。
コンテスト開催時間終了後、他の参加者の A 問題の本提出の入力部分が、あなたの B 問題の本提出に入力として与えられる。
他の本戦参加者 n 人の A 問題の本提出の入力部分に対して、あなたの B 問題の本提出が正答し、
他の本戦参加者 m 人の A 問題の本提出がなかった場合、あなたに上記とは別に 2(n+m) 点が与えられる。

この問題には部分点は設定されていない。正解した場合は、10 点が与えられる。


入力例1

3 2 2
0 1
1 2

出力例1

2
0

入力例2

5 3 4
0 1
0 2
0 3

出力例2

2
1
3
4

与えられるグラフが連結であるとは限りません。


入力例3

4 3 2
0 1
1 2
2 3

出力例3

0
2

\{0,\ 2\}\{1,\ 3\} は両方条件を満たします。この場合どちらを出力しても正解です。