Background

Thanks to @ScanfN for providing two sets of hack testdata.

Problem Description

For a tree, we can extract some path together with the edges incident to that path; it looks like a caterpillar. The more vertices it contains, the larger the caterpillar. For example, extracting part of the tree on the left (Figure $1$) yields the caterpillar on the right (Figure $2$).

Input Format

The first line contains two integers $N, M$, denoting the number of vertices and the number of edges in the tree.

The next $M$ lines each contain two integers $a, b$, indicating that there is an edge between vertices $a$ and $b$ ($a, b \le N$). You may assume that no identical pair $(a, b)$ appears more than once.

Output Format

Output a single integer on one line, representing the size of the largest caterpillar.

13 12 
1 2 
1 5 
1 6 
3 2 
4 2 
5 7 
5 8 
7 9 
7 10 
7 11 
8 12 
8 13 

11

Hint

For $40\%$ of the testdata, $1\leq N \le 50000$.

For $100\%$ of the testdata, $1\leq N \le 300000$.

Translated by ChatGPT 5