AT_abc427_c [ABC427C] Bipartize

There is a simple undirected graph with $ N $ vertices and $ M $ edges. The graph consists of vertex $ 1, $ vertex $ 2,\ldots, $ vertex $ N $ , and the $ i $ -th edge $ (1\le i\le M) $ connects vertices $ u _ i $ and $ v _ i $ . You will perform the following operation zero or more times: - Choose one edge that has not been deleted yet, and delete it. Your goal is to make the graph bipartite. Find the minimum number of operations needed to make the graph after the operations bipartite. What it means for a graph to be simple?A graph is simple if and only if it has no self-loops (edges where $ u _ i=v _ i $ ) or multi-edges (pairs of edges where $ u _ i=u _ j $ and $ v _ i=v _ j $ ). What is a bipartite graph?A bipartite graph is a graph where it is possible to color each vertex black or white satisfying the following condition: - For every edge, the two vertices connected by that edge have different colors.

The input is given from Standard Input in the following format: > $ N $ $ M $ $ u _ 1 $ $ v _ 1 $ $ u _ 2 $ $ v _ 2 $ $ \vdots $ $ u _ M $ $ v _ M $

Print the number of operations that need to be performed to make the graph bipartite.

### Sample Explanation 1 You can make the graph bipartite by deleting two edges: for example, the edge connecting vertices $ 1 $ and $ 3 $ , and the edge connecting vertices $ 3 $ and $ 5 $ . It is impossible to make the graph bipartite by performing one or less operations, so print `2`. ### Sample Explanation 2 The graph is bipartite from the beginning. Thus, the number of operations that need to be performed is $ 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) $ - The given graph is simple. - All input values are integers.