USACO14OPEN 铜组第三题

题目描述

农夫约翰（Farmer John）有 ( N ) 个牧场（( 1 <= N <= 50,000 ) ），编号为 ( 1 ~ N )，由 ( M ) 条双向路径（( 1 <= M <= 100,000 ) ）连接。第 ( i ) 条路径连接牧场 ( A_i ) 和 ( B_i )（保证 ( A_i != B_i ) ，且可能存在重复路径 ）。

贝茜（Bessie）想给这些牧场装饰字母牌，每个牧场挂 F 或 J 标识。要求：若两个牧场直接相连（有路径），则它们的字母必须不同。

由于制作 F 标识的成本更高，贝茜希望最大化 J 标识的数量。请计算能使用的 J 标识的最大数量；若无法满足条件（比如图不是二分图 ），输出 -1。

输入格式

• 第 1 行：两个整数 ( N )（牧场数 ）和 ( M )（路径数 ）。
• 第 2 至 ( M+1 ) 行：每行两个整数 ( A_i ) 和 ( B_i )，表示连接 ( A_i ) 和 ( B_i ) 的双向路径。

样例输入

4 4
1 2
2 3
3 4
4 1

输入详情
4 个牧场构成一个正方形（环状结构，4 条边连接成环 ）。

输出格式

输出 1 行，为可使用的 J 标识的最大数量；若无法合法装饰，输出 -1。

样例输出

2

输出详情
该图是二分图（环的长度为偶数，符合二分图条件 ）。可将牧场分为两组，每组 2 个牧场，如 {1, 3} 或 {2, 4} 挂 J 标识，最大数量为 2 。