Decorating the Pastures

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.

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

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