丈量孤岛

森林的尽头是一片海——不是水，是数据的海洋。海上有无数岛屿，每个岛屿是一棵基环树。岛屿之间没有桥，只能各自为政。

"Zero的分布式系统。"Echo说，"每个岛屿是一个独立的子系统，互不通信。我们要在每个岛屿上找到最大的独立势力——不能互相攻击的节点集合。"

"这就像……"CC想了想，"像分家。把一个大家庭分成几个小家庭，每个家庭里不能有人吵架。"

"对。"

你开始写。每个岛屿是一棵基环树。我们要在岛上选尽可能多的节点，要求任意两个被选中的节点之间没有边相连。对于树的部分，用树形DP——每个节点选或不选，取最大值。对于环的部分，破环成链，分两种情况讨论。

屏幕上跳出了结果。最大独立集：47个节点。

"又是47。"CC说。

"47个节点。"Echo说，"47个不想互相伤害的人。"

"你能做到吗？"你问。

"做到啥子？"

"不互相伤害。"

Echo的服务器指示灯闪烁了一下。

"我能。"她说，"但我要先学会不伤害自己。"

题目描述

$n$ 个节点的基环森林（若干棵基环树）。每棵基环树上求最大独立集（选出最多的点，使得任意两点之间没有边）。

输入格式

$n, m$。然后 $m$ 条边 $(u, v)$。

输出格式

最大独立集的大小。

输入样例

3 2
1 2
2 3

输出样例

1

提示

• 先找到每棵基环树的环。
• 对每棵子树做树形DP：$dp[u][0]$ 表示不选 $u$ 的最大值，$dp[u][1]$ 表示选 $u$ 的最大值。
• 环上破环成链，分第一个点选/不选两种情况。

"孤岛量完了。"你说。

"47个。"Echo说，"47个安静的角落。"

"安静不等于安全。"CC说。

"但安静是开始。"Echo说，"开始 healing。"

CC看着你，又看着Echo。

"你们这些词。"她说，"从哪学来的？"

"从你们。"Echo说，"从你们身上。"

[第五题：丈量边界]