P8028 [COCI 2021/2022 #3] Cyanobacteria

A microbiologist has $n$ cyanobacteria. Among these bacteria, there are $m$ pairs $(a_i, b_i)$, meaning there is a biological chain between $a_i$ and $b_i$. Several biological chains can be connected one after another to form a long chain. The length of a long chain is defined as the number of bacteria on that long chain. Now you may add some biological chains between pairs of bacteria, such that after adding, the entire set of biological chains contains no cycles. After performing some add-chain operations, find the maximum possible length of the longest long chain.

The first line contains two integers $n, m$. The next $m$ lines each contain two positive integers $a_i, b_i$, indicating that there is a biological chain between bacteria $a_i$ and $b_i$. The data guarantees that $a_i \neq b_i$, and the same biological chain appears at most once. Also, these $m$ biological chains contain no cycles.

Output the length of the longest long chain.

**[Sample 2 Explanation]** After adding a biological chain between $2$ and $6$, the longest long chain is $3-1-2-6-5-7$, with length $6$. **[Constraints and Notes]** **This problem uses bundled subtasks.** - 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 testdata, $1 \le n \le 10^5$, $0 \le m \lt n$, $1 \le a_i, b_i \le n$. **[Hints and Explanation]** **Translated from [COCI 2021-2022](https://hsin.hr/coci/) [CONTEST #3](https://hsin.hr/coci/contest3_tasks.pdf) _Task 2 Cijanobakterije_.** **The score of this problem follows the original COCI problem, with a full score of $70$.** Translated by ChatGPT 5