準オイラーグラフ・有向グラフ (paizaランク B 相当)

いくつかの頂点と、それらのうち 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 に向かって辺が伸びていることを表します。

そして、これら以外に辺はありません。

このとき、以下の条件を用いて、このグラフにおいて、すべての辺を一筆書きすることができるかどうか判定してください。ただし、この問題では最終的に初めの頂点に戻らなくても良いものとします。なお、そのようなことが可能なグラフを準オイラーグラフといいます。


弱連結な有向グラフにおいて、すべての辺を一筆書きすることができるための必要十分条件は以下のいずれかを満たすことです。

・すべての頂点において、入次数と出次数が一致する。

・以下の条件をすべて満たす。

・(入次数) = (出次数 + 1) となる頂点がちょうど 1 つ存在する。

・(入次数 + 1) = (出次数) となる頂点がちょうど 1 つ存在する。

・残りのすべての頂点について、入次数と出次数が一致する。




ただし、ここでいう入出次数とは、以下の形式で表現されるものとします。


頂点 i に向かっている辺の個数を頂点 i の入次数といいます。
頂点 i から出ている辺の個数を頂点 i の出次数といいます。

下の図は、ある有向グラフの頂点の入次数を左側の整数、出次数を右側の整数で表したものです。