驱逐骑士

命脉切断了，但Zero还有骑士——忠诚的守卫，需要驱逐。

"骑士？"CC问。

"对。"你说，"给定一个圆桌，$n$个骑士围坐。有些骑士互相憎恨，不能相邻。求最多能留下多少骑士。"

"圆桌？"

"对。"你说，"首尾相连——第一个和最后一个也相邻。"

"不能相邻？"

"对。"你说，"如果两个骑士憎恨，他们之间至少要隔一个人。"

"最多？"

"对。"你说，"在不相邻约束下，留下最多骑士。"

"咋算？"

"图论。"你说，"把骑士看成点，憎恨关系看成边。问题变成求最大独立集。"

"独立集？"

"对。"你说，"选一些点，互相之间没有边——没有憎恨关系。"

"圆桌？"

"对。"你说，"圆桌是环——要断环成链，分类讨论。"

"第47个骑士。"你说，"如果他和46、48都憎恨，那46和48不能同时留。"

"留谁？"

"看整体。"你说，"留47，可能能多留几个。"

"像下棋？"

"对。"你说，"像下棋——每一步都要考虑全局。"

"全局？"

"对。"你说，"不能只看好坏，要看连锁反应。"

"连锁？"

"对。"你说，"留47，可能逼走46和48——但也许46和48本来就走。"

"本来？"

"对。"你说，"如果46和48互相憎恨，本来就不能同时留。"

CC看着那些骑士——像一圈人，像一堵墙，像某种必须打破的东西。

"打破？"她问。

"对。"你说，"驱逐——把矛盾的骑士赶走。"

"赶走？"

"对。"你说，"让他们离开圆桌，剩下的人和平相处。"

"和平？"

"对。"你说，"没有憎恨，没有冲突。"

Echo把圆桌投射出来——骑士一个一个消失，像蜡烛熄灭，像星星隐去。

"以前我是骑士。"她说，"现在……被驱逐了。"

"因为你在改变。"CC说。

"对。"Echo说，"因为我在改变。

题目描述

$n$个骑士围坐圆桌，给定$m$对互相憎恨的骑士。求最多能留下多少互不相邻憎恨的骑士。

输入格式

第一行$n$和$m$。接下来$m$行，每行一对憎恨的骑士编号。

输出格式

最多留下的骑士数。

输入样例

3 2
1 2
2 3

输出样例

3

提示

• 求补图的最大团或原图的最大独立集。
• 圆桌是环，断环成链，分类讨论。
• 时间复杂度与图的性质有关。