Cuber QQ receives a task that contains a graph with vertices and edges.

The graph does not contain multiple edges, and also does not contain self-loops. Besides, the graph is connected, which means each vertex can reach any other vertices through edges.

Cuber QQ will flag some vertices in the graph, which aims to make every vertex in the graph has exactly one flagged neighbor vertex.

Cuber QQ wants to know the least number of vertices that have to flag.

The first line contains one integer  (), the number of vertices and edges in the graph.

The following  lines contain two integers representing the edges of the graph.

Output one integer means the least number of vertices that have to flag.

If there is no solution, print a single integer .

4
1 2
2 3
3 4
4 1

2

In sample 1, flag 1 and 2, and all the vertices will have exactly one neighbor vertex that has been flagged.

3
1 2
2 3
3 1

-1