Minimum Number of Crabs

In this problem, you are given an undirected graph with \(n\) vertices and \(m\) edges representing the campus of Sunshine University. Each crab can block one vertex, and when a vertex is blocked, all edges incident to it are blocked. However, if two adjacent vertices are both blocked, the crabs fighting causes a conflict.

Your task is to choose a set of vertices to block such that every edge is covered (i.e. for every edge, exactly one endpoint is blocked) and no two adjacent vertices are both blocked. If it is impossible, output \(-1\). Otherwise, output the minimum number of crabs (i.e. vertices blocked) required.

This can be formulated as follows: for every edge \((u,v)\), assign a value of \(0\) (not blocked) or \(1\) (blocked) to vertices such that \(f(u) + f(v) = 1\). In each connected component with at least one edge, if the graph is bipartite, there are exactly two valid assignments. Choose the assignment with the minimum number of \(1\)s. For isolated vertices (with no incident edges), no blocking is needed.

inputFormat

The first line contains two integers \(n\) and \(m\) representing the number of vertices and edges in the graph. The following \(m\) lines each contain two integers \(u\) and \(v\), indicating that there is an undirected edge between vertex \(u\) and vertex \(v\). The vertices are numbered from 1 to \(n\).

outputFormat

Output a single integer representing the minimum number of crabs needed to block all roads under the conflict-free rule. If it is impossible to achieve such a configuration, output \(-1\).

sample

3 3
1 2
2 3
3 1

-1