题目描述

一位微生物学家有 $n$ 个蓝藻细菌。这些细菌中有 $m$ 组细菌 $(a_i,b_i)$，表示 $a_i$ 和 $b_i$ 之间有一条生物链。若干条生物链顺次连接之后可组成长链。长链的长度定义为这条长链上的细菌数量。

现可在细菌之间两两添加若干条生物链，使得添加之后的所有生物链均不存在环。

求在进行若干次添加生物链的操作后，最长的长链的长度是多少。

输入格式

第一行，两个整数 $n,m$。

接下来的 $m$ 行，每行两个正整数 $a_i,b_i$，表示 $a_i,b_i$ 两个细菌之间有一条生物链。数据保证 $a_i \neq b_i$ 且同一条生物链只会出现一次，同时这 $m$ 条生物链不会存在环。

输出格式

输出最长的长链的长度。

100 0

100

8 6
1 2
1 3
1 4
5 6
5 7
5 8

6

6 5
1 2
2 3
3 4
4 6
4 5

5

提示

【样例 2 解释】

在 $2$ 和 $6$ 之间添加一条生物链后，最长的长链为 $3-1-2-6-5-7$，长度为 $6$。

【数据规模与约定】

本题采用子任务捆绑测试。

• Subtask 1（15 pts）：$m=n-1$。
• Subtask 2（6 pts）：$b_i=a_i+1$。
• Subtask 3（6 pts）：$1 \le a_i \le 2$。
• Subtask 4（15 pts）：$1 \le n \le 1000$。
• Subtask 5（28 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le n \le 10^5$，$0 \le m \lt n$，$1 \le a_i,b_i \le n$。

【提示与说明】

题目译自 COCI 2021-2022 CONTEST #3 Task 2 Cijanobakterije。

本题分值按 COCI 原题设置，满分 $70$。