No.768 Tapris and Noel play the game on Treeone

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 25
作問者 : NoelちゃんNoelちゃん / テスター : lumc_lumc_
2 ProblemId : 2085 / 出題時の順位表

問題文

ある日 Noel ちゃんと Tapris ちゃんが友達の Treeone さんを使ってゲームをしました.
ゲームは次のルールに従います.

  • 0. Treeone さんは頂点になにも書かれていない $N$ 頂点の木です.初めに Noel ちゃんが好きな頂点を 1 つ選び文字 "N" を書きます.
  • 1. Tapris ちゃんが文字 "N" と書かれた頂点に隣接する頂点のうち,何も書かれていないものを 1 つ選び,文字 "T" を書きます.
  • 2. Noel ちゃんが文字 "T" と書かれた頂点に隣接する頂点のうち,何も書かれていないものを 1 つ選び,文字 "N" を書きます.
  • 3. 1 - 2 を繰り返します,これ以上書けなくなったほうが負けです.

Noel ちゃんは Tapris ちゃんに勝ちたいと思っています.

Tapris ちゃんの選択にかかわらず Noel ちゃんが勝つことのできる頂点をすべて求めてください.

入力

$N$
$a_1\ b_1$
$a_2\ b_2$
$\vdots$
$a_{N-1}\ b_{N-1}$

1 行目に木の頂点数 $N(2\le N\le 10^5)$ が与えられる.
2 行目以降 N - 1 行に $a_i$ と $b_i(1\le a_i,\ b_i\le N)$ が空白区切りで与えられ,辺$_i$ は頂点 $a_i$ と頂点 $b_i$ を結ぶ.

出力

1 行目に Noel ちゃんが最初に選ぶと勝てる頂点の個数を出力してください.
2 行目以降に Noel ちゃんが最初に選ぶと勝てる頂点を昇順で改行区切りで出力してください(最後の頂点の後にも改行を出力してください).

もしそのような頂点が 1 つもない場合は, 0と出力してください.

サンプル

サンプル1
入力
6
1 2
1 3
2 4
2 5
2 6
出力
3
4
5
6

Noel ちゃんは 4, 5, 6 の頂点を選ぶことで Tapris ちゃんがどんな頂点を選んでも勝つことができます.

サンプル2
入力
5
1 2
1 5
2 3
3 4
出力
3
2
4
5

頑張ってください.

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。