문제
캐티는 최근 원기를 상대로 사기를 쳤다. 그래서 원기는 캐티에게 복수하려고 한다.
캐티에게는 캐티가 소중히 여기는 크기 N짜리 트리가 있다.
장난꾸러기 원기는 트리의 두 정점을 연결하는 간선을 추가하려고 한다.
원기는 더 많은 간선을 추가하고 싶었지만,
원래 트리의 주인인 캐티의 복수가 두려워 2개만 추가하려 한다.
그러면 싸이클이 여러개 생기게 되는데,
원기는 그 싸이클들에 속하는 정점의 개수를 최대화하여 캐티의 트리를 망치려 한다.
캐티는 그 계획을 알아채고 자신의 트리가 망가지는 최악의 상황을 알아보고자 한다.
원기가 2개의 간선을 추가해서 만들어진 싸이클들에 속하는 정점의 개수의 최댓값을 구하시오.
입력
첫째 줄에 트리의 정점 수 N(1≤N≤1,000,000)이 주어진다.
2번째~N번째 줄에는 각각 트리의 간선을 나타내는 (s,e)쌍이 공백을 사이에 두고 주어진다.
출력
싸이클들에 속하는 정점 개수의 최댓값을 출력하시오.
[부분점수 제한]
(1) N≤3000 (66%)
(2) 제약 조건 없음 (33%)
예제 #1
8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8
예제 #2
8
1 2
1 3
2 4
2 5
3 6
3 7
2 8
7
출처
william202
로그인해야 코드를 작성할 수 있어요.