16717번 - Katty and Wonki

캐티는 최근 원기를 상대로 사기를 쳤다. 그래서 원기는 캐티에게 복수하려고 한다.

캐티에게는 캐티가 소중히 여기는 정점의 개수가 N개인 트리가 있다. 장난꾸러기 원기는 트리의 두 정점을 연결하는 간선을 추가하려고 한다.

원기는 되도록 많은 간선을 추가하고 싶었지만, 원래 트리의 주인인 캐티의 복수가 두려워 2개만 추가하려 한다.

간선을 추가하게 되면 사이클이 여러 개 생기게 되는데, 원기는 그 사이클들에 속하는 정점의 개수를 최대화하여 캐티의 트리를 망치려 한다.

캐티는 그 계획을 알아채고 자신의 트리가 망가지는 최악의 상황을 알아보고자 한다.

원기가 2개의 간선을 추가해서 만들어진 사이클들에 속하는 정점의 개수의 최댓값을 구하시오.

단, 원기가 두 개의 간선을 추가한 후 나오는 그래프는 중복간선 또는 self loop를 포함할 수 있다. 

또한, 여러 사이클에 속하는 정점도 정확히 한 번만 세며, self loop도 하나의 사이클로 본다. 

첫째 줄에 트리의 정점 수 N이 주어진다. (1 ≤ N ≤ 10⁵)

그 뒤로 N-1개의 줄에 걸쳐, 트리의 각 간선이 잇는 두 정점의 번호가 공백을 사이에 두고 주어진다.

2개의 간선을 추가했을 때, 사이클들에 속하게 되는 정점 개수의 최댓값을 출력하시오.