自己ループと二重辺を含まない 頂点 辺の無向連結グラフがあります。 番目の辺 は頂点 と頂点 を結んでいます。
アリスさんはこのグラフの上で種まきをします。頂点 から頂点 に移動するときその つの頂点を結ぶ辺に種をまき、頂点 に到着した時点で花が咲きます。種まきは任意の頂点から始めることができます。
ただし、花を踏んでしまう可能性があるので、アリスさんは一度通った辺の上は歩かないことにしました。
アリスさんは全ての辺に花を咲かせることができるでしょうか。
入力は以下の形式で標準入力から与えられる。
アリスさんが全ての辺に全ての辺に花を咲かせることができる場合 Yes
、そうでなければ No
を出力しなさい。
3 3 1 2 1 3 2 3
Yes
以下の順に種をまくことで全ての辺に花を咲かせることができます。
7 7 1 3 2 7 3 4 4 5 4 6 5 6 6 7
No
どの始点からスタートしても、全ての辺に種をまくには必ず一度通った辺を再び通る必要があります。
2 1 1 2
Yes