問題一覧 > 通常問題

No.1640 簡単な色塗り

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 79
作問者 : harurunharurun / テスター : platinumplatinum magstamagsta
3 ProblemId : 6612 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-07-09 16:01:58

問題文

$N$ 個の白い球があり、それぞれ $1,2,...,N$ と番号付けられています。

A君は $i=1,2,...,N$ について以下の操作を行います。

  • $i$ 回目に、球$A_i$ または 球$B_i$ のどちらか一方を黒で塗る。

$N$ 回の操作で球を全て黒で塗ることが可能かどうかを判定してください。

全ての球を黒に塗ることが可能ならば、各回でどちらを選ぶべきかも求めてください。

選び方が複数ある場合は、どの選び方を出力してもかまいません。

制約

  • $1≤N≤10^5$

  • $1≤A_i,B_i≤N$

  • 入力は全て整数である。

入力

$N$
$A_1$ $B_1$
$\vdots$
$A_N$ $B_N$
  • $1$ 行目には $N$ が与えられる。

  • $i+1$ 行目 $(1≤i≤N)$ には、$A_i$ と $B_i$ が空白区切りで与えられる。

出力

  • 全て黒く塗ることが出来ない場合は No と $1$ 行に出力してください。

  • 全て黒く塗ることが出来る場合は 以下の通りに出力してください。

    • $1$ 行目には Yes と出力してください。

    • $i+1$ 行目$(1≤i≤N)$には $A_i$ と $B_i$ のうち選んだ方を出力してください。

最後に改行してください。

サンプル

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

この選び方以外には、$(2,4,3,1)$ などもあります。

サンプル2
入力
3
1 2
1 2
1 2
出力
No

どう選んでも、球 $3$ を塗ることはできません。

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

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。