时间限制：1秒　　内存限制：256M

---

【题目描述】

　　小H想邀请\(n\)个好朋友参加他的高中毕业宴会。虽然小H与所有朋友关系都很好，但不能保证他的朋友们彼此之间关系同样融洽。具体来说，我们知道编号为 \(a_i\) 的朋友与编号为 \(b_i\) 的朋友存在冲突。
　　小H得到了一张包含 \(m\) 个冲突对 \((a_i,b_i)\) 的列表。现在，看似可以将玩家分成两队，但对小H来说并不那么简单……，他想要将这些\(m\)个冲突对划分成若干段，使得：
　　　◆每个冲突对恰好属于一段；
　　　◆仅考虑每段内的关系时，可将所有人分成两队，使得同一队中没有相互冲突的人。
　　小H又把问题描述复杂化了，现在他自己无法解决这个问题。请帮助他，告诉他满足上述条件时，最少可以将这些对划分成多少段。

【输入格式】

　　第一行包含两个整数 \(n、m（1≤n,m≤10^6）\)，分别表示朋友数量和冲突关系数量。接下来的 \(m\) 行，每行包含两个整数\(a_i,b_i（1≤a_i,b_i≤n，a_i≠b_i）\)，表示朋友\(a_i\)与朋友\(b_i\)存在冲突。保证任何冲突对\((a_i,b_i)\)不会重复出现。

【输出格式】

　　输出一个整数，表示问题的答案。

【输入输出样例1】

　Input

3 3
1 2
2 3
1 3

　Output

2

【样例1说明】

　　有3对冲突关系：(1, 2),(2, 3),(1, 3)]。小H可以将前两个对放在第一段。此时，可以组成队伍：{1,3} 和 {2}。在第二段中，我们可以取最后一个对。1和3必须分在不同队伍，2可以在任意一队。或者，我们可以将第一个对分配给第一段，最后两个对分配给第二段。注意，我们不能将第一个和第三个对放在同一段，而将第二个对放在另一段，因为一段应当只包含连续的冲突对。我们也不能将所有对放在同一段，因为那样总会存在一个队伍中有相互冲突的人。

【输入输出样例2】

　Input

5 10
2 4
1 2
3 4
1 3
1 5
4 5
2 3
3 5
1 4
2 5

　Output

3

【样例1说明】

　　可以划分成以下三段：[1,6]、[7,9]、[10,10]。
　　◆在第一段中，可以组成队伍[1,4]和[2,3,5]，1和4不冲突，且(2,3)、(2,5)、(3,5)也不冲突。
　　◆在第二段中，可以组成队伍[1,3]和[2,4,5] ，1和3不冲突，且(2,4)、(2,5)、(4,5)也不冲突。
　　◆在第三段中，可以组成队伍[1,2]和[3,4,5] ，1和2不冲突，且(3,4)、(3,5)、(4,5)也不冲突。

【测试点性质】

　　（4 分）：\(n≤3\)；
　　（7 分）：\(n≤10\)；
　　（15 分）：\(n,m≤5000\)；
　　（13 分）：输入中的冲突对随机生成；这意味着从所有 \(n(n−1)/2\) 对中随机选择 \(m\) 对；
　　（14 分）：每个人冲突的对象不超 1 个；
　　（19 分）：\(n≤100000\)；
　　（17 分）：\(n≤200000\)；
　　（11 分）：无额外限制。

【来源】

　　Mr.he