题目描述

  有$N$个人想打篮球，现在我们要对他们进行尽可能的平均分配成两个队伍。但是有$M$对“铁哥们”的关系，如果$u$和$v$是一对“铁哥们”，那么他俩就必须在同一个队伍中。现在，教练想知道将这$N$个人分成两个队伍，两个队伍的人数差距最少为多少？

输入格式

第一行，输入两个整数$N, M(1≤N, M≤5 \times 10^3)$。

接下去$M$行，每行两个整数$u, v(1≤u, v≤N)$，表示$u$、$v$是一对“铁哥们”。

输出格式

输出一行，一个整数表示两个队伍的人数差距的最小值。

样例

3 1
1 2

1

来源

2022 HGNU-SWUT暑假联合集训