Decorating the Pastures

Interview

Time limit1sMemory limit128 MB

Summary

Color each connected group of pastures with two letters so neighbors differ and the count of J signs is as large as possible.

Level: Medium4 of 10
Topics: BFS, Graph
Solved: No attempts yet

Problem

Farmer John has N pastures (1 ≤ N ≤ 50,000) connected by M bidirectional paths (1 ≤ M ≤ 100,000). Path i joins pastures Ai and Bi with Ai ≠ Bi. Multiple paths may connect the same pair.

Bessie puts a sign labeled F or J in each pasture. Connected pastures must use different letters. F signs cost more, so maximize the number of J signs. Output -1 if no valid labeling exists.

Input

Line 1: integers N and M
Lines 2 through M+1: integers Ai and Bi

Output

Line 1: the maximum number of J signs, or -1 if impossible

Examples1

Example 1
Input
```
4 4
1 2
2 3
3 4
4 1
```
Expected output
```
2
```