Problem Description

A microbiologist has $n$ cyanobacteria. Among these bacteria, there are $m$ pairs of bacteria $(a_i, b_i)$, indicating a biological chain between $a_i$ and $b_i$. Several biological chains connected in sequence can form a long chain. The length of the long chain is defined as the number of bacteria on this long chain.

It is possible to add several biological chains between any two bacteria such that all biological chains after addition do not form cycles.

Determine the length of the longest long chain after performing several operations of adding biological chains.

Input Format

The first line contains two integers $n$ and $m$.

The next $m$ lines each contain two positive integers $a_i$ and $b_i$, indicating a biological chain between $a_i$ and $b_i$. The data guarantees that $a_i \neq b_i$ and each biological chain appears only once, and these $m$ biological chains do not form cycles.

Output Format

Output the length of the longest long chain.

Sample Input and Output

Sample Input #1

100 0

Sample Output #1

100

Sample Input #2

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

Sample Output #2

6

Sample Input #3

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

Sample Output #3

5

Notes

Explanation for Sample 2

After adding a biological chain between $2$ and $6$, the longest long chain is $3-1-2-6-5-7$, with a length of $6$.

Data Range and Constraints

This problem uses subtask-based scoring.

• 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): No special restrictions.

For $100\%$ of the data, $1 \le n \le 10^5$, $0 \le m < n$, $1 \le a_i, b_i \le n$.

Translated from COCI 2021-2022 CONTEST #3 Task 2 Cijanobakterije.

This problem is scored according to the original COCI settings, with a maximum score of $70$.

见题面 Input 部分

见题面 Output 部分