問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう!
いくつかの頂点と、それらのうち 2 つの頂点を結ぶ辺の集合をグラフといいます。特に、辺に向きがつけられていない場合は無向グラフといいます。
さらに、どの 2 つの頂点間も辺をたどって行き来ができるような場合は、連結なグラフといいます。下の図は、頂点の数が 5 の連結な無向グラフの一例です。
1, ..., n の番号がついた n 個の頂点と、1, ..., m の番号がついた m 個の辺からなる連結な無向グラフを考えます。
整数 n, m と、m 個の頂点の組 (a_1, b_1), ..., (a_m, b_m) が与えられます。
頂点の組 (a_i, b_i) は、頂点 a_i と 頂点 b_i が辺で直接つながっていることを表します。
(頂点 a_i と 頂点 b_i が辺で直接つながっているとき、頂点 b_i と 頂点 a_i も辺で直接つながっているといえます。)
そして、これら以外に辺で直接つながっている頂点の組はありません。
このとき、以下の条件を用いて、このグラフにおいて、ある頂点から始めてすべての辺を一筆書きして最初の頂点に戻ってくることができるかどうか判定してください。なお、そのようなことが可能なグラフをオイラーグラフといいます。
連結な無向グラフにおいて、ある頂点から始めてすべての辺を一筆書きして最初の頂点に戻ってくることができるための必要十分条件は以下のようになります。
・すべての頂点の次数が偶数である。
ただし、ここでいう次数とは、以下の形式で表現されるものとします。
頂点 i をつないでいる辺の個数を頂点 i の次数といいます。
ただし、辺がループの場合は、その辺に対して 2 回分数えるものします。
下の図は、ある無向グラフの頂点の次数を表したものです。
n m
a_1 b_1
...
a_m b_m
与えられたグラフにおいて、ある頂点から始めてすべての辺を一筆書きして最初の頂点に戻ってくることができる場合は 1, そうでない場合は 0 を出力してください。
また、末尾に改行を入れ、余計な文字を含んではいけません。
すべてのテストケースにおいて、以下の条件をみたします。
・ 入力はすべて整数
・ 2 ≦ n ≦ 100
・ n - 1 ≦ m ≦ 10000 = 10^4
・ 1 ≦ a_i ≦ b_i ≦ n
・ 与えられるグラフは連結である
3 2
1 2
2 3
0
3 4
1 2
1 2
2 3
2 3
1