AT_abc427_c [ABC427C] Bipartize

$ N $ 頂点 $ M $ 辺の単純な無向グラフがあります。 グラフは頂点 $ 1, $ 頂点 $ 2,\ldots, $ 頂点 $ N $ からなり、 $ i $ 番目 $ (1\le i\le M) $ の辺は頂点 $ u _ i $ と頂点 $ v _ i $ を結んでいます。 あなたは、次の操作を $ 0 $ 回以上行います。 - まだ削除されていない辺をひとつ選び、削除する。 あなたの目的はグラフを二部グラフにすることです。 操作を行ったあとのグラフを二部グラフにするために、最低でも何回操作を行う必要があるか求めてください。 グラフが単純であるとはグラフが単純であるとは、自己ループ（ $ u _ i=v _ i $ となる辺）や多重辺（ $ u _ i=u _ j $ かつ $ v _ i=v _ j $ となる辺のペア）が存在しないことをいいます。 二部グラフとは二部グラフとは、頂点をそれぞれ黒か白のどちらか一色で塗り、次の条件を満たすことができるグラフのことをいいます。 - どの辺についても、その辺が結んでいるふたつの頂点に塗られた色は異なる。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ u _ 1 $ $ v _ 1 $ $ u _ 2 $ $ v _ 2 $ $ \vdots $ $ u _ M $ $ v _ M $

操作を行ったあとのグラフを二部グラフにするために、行う必要がある操作の回数を出力せよ。

### Sample Explanation 1 例えば、頂点 $ 1 $ と頂点 $ 3 $ を結ぶ辺、頂点 $ 3 $ と頂点 $ 5 $ を結ぶ辺の $ 2 $ つを削除することでグラフを二部グラフにすることができます。 操作を $ 1 $ 回以下行うことでグラフを二部グラフにすることはできないため、`2` を出力してください。 ### Sample Explanation 2 グラフははじめから二部グラフです。 よって、行う必要がある操作の回数は $ 0 $ 回です。 ### Constraints - $ 2\le N\le10 $ - $ 1\le M\le\dfrac{N(N-1)}2 $ - $ 1\le u _ i\lt v _ i\le N\ (1\le i\le M) $ - 与えられるグラフは単純 - 入力はすべて整数