Narfouz in the Center#12438
As we all know, Narfouz Al-Narfouz enjoys annoying his cow with his low quality problems. Actually, his cow is now willing to cut off the electricity in his apartment!
The building where Narfouz lives is structured as a tree with apartments and n-1 corridors.
Narfouz is willing to do the following operation exactly once:
He'll remove one apartment and all the corridors connected to it, then he'll move to one of the centers\Large^{\star} of one of the remaining connected components.
After doing the operation, his cow will chase every possible apartment where he could live and cut off its electricity!
Narfouz is nervously asking you what is the largest number of possible apartments after doing the operation once?
\Large^{\star} a node in a tree is considered to be a center iff the maximum distance between it and every other node in the tree is minimal across all nodes
The first line contains an integer (3 \leq n \leq 2 \times 10^5), the number of apartments.
The i+1-th line contains two numbers and (1 \leq u,v \leq n) representing the endpoints of the -th corridor.
You should print one integer representing the maximum number of possible apartments where Narfouz could live after doing the operation once.
Example 1
After removing the 2_{\mathsf{nd}} apartment, we get three connected components , , \{1,6,7,3\}
In the first connected component, the only center is .
In the second connected component, the only center is .
In the third connected component, nodes and are considered centers
It can be proven that this is the only optimal way of doing the operation
Subtask ( points): The -th corridor connects apartments and i+1
Subtask ( points): The -th corridor connects apartments and i+1
Subtask ( points): (1 \leq n \leq 1000)
Subtask ( points): No additional constraints