No.2236 Lights Out On Simple Graph
タグ : / 解いたユーザー数 72
作問者 :
![srjywrdnprkt](https://pbs.twimg.com/profile_images/975469531601645568/A252dvSp.jpg)
![kemuniku](https://pbs.twimg.com/profile_images/1627159705083842560/aL4N0yrm.jpg)
問題文
から までの番号がついた 個の頂点と、 から までの番号がついた 本の辺からなる連結とは限らない単純無向グラフが与えられます。辺 は頂点 と頂点 を結んでいます。
また、各頂点は白か黒のいずれかの色で塗られており、頂点 の色は です。ただし、 は白を、 は黒を表します。
あなたは以下の操作を 回以上何度でも行えます。全ての頂点の色を白にすることができるか判定し、可能な場合は必要な操作回数の最小値を求めてください。
(操作)
を満たす整数 を一つ選び、頂点 と頂点 の色をそれぞれ反転させる。すなわち、頂点の色が黒ならば白に、白ならば黒に変える。
入力
入力は全て整数で以下の制約を満たす。
- ならば
- は または
出力
全ての頂点の色を白にするために必要な操作回数の最小値を出力してください。
ただし、何度操作を行なっても全ての頂点の色を白にできないならば-1を出力してください。
最後に改行してください。
サンプル
サンプル1
入力
5 5 1 2 2 3 2 4 4 5 2 5 1 1 1 0 1
出力
3
, , の順で操作を行います。すると、各頂点の色は と変化します。 回以下の操作では全ての頂点の色を白にできないので が答えです。
サンプル2
入力
3 1 1 2 0 1 1
出力
-1
何度操作を行なっても、全ての頂点の色を白にすることはできません。与えられるグラフは連結であるとは限らないことに注意してください。
サンプル3
入力
7 9 1 2 1 4 2 3 2 4 3 4 4 5 5 6 5 7 6 7 1 0 1 1 0 0 1
出力
4
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。