Informatica Online Judge

  도시 개발 #2 [2256 / 08D0]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 3   Total Tried : 4


The Champion of this Problem (C++) : gs17082 - 0ms / 2502byte
My Best Submission (C++) : N/A

[35th 이민제]
Writer ID : [gs17082]

Background

고등학교 시절, 민제는 청주에 산다는 이유로 친구들에게 많은 놀림을 받았다. 큰 상처를 받은 민제는 시장이 되어 청주를 발전시키겠다는 웅대한 꿈을 가지게 된다.

세월이 흘러 청주의 시장이 된 민제는 본격적으로 시를 개발하기 위한 작업에 착수하였다. 청주시는 (1부터 N까지 번호가 붙은) N개의 주거지가 N - 1개의 양방향 도로로 연결되어 있는 형태이며, 도로를 통해 임의의 두 주거지 사이를 왕복할 수 있도록 설계되어 있다. 민제는 다음과 같은 과정을 거쳐 도시를 발전시키려고 한다.

1. 민제는 서로 다른 두 주거지를 고르고, 이 두 주거지를 직접 잇는 도로를 설치한다. 이때 선택된 두 주거지를 직접 잇는 도로는 이전에 없었어야 한다.
2. 새로운 도로가 설치되면, 한 주거지에서 출발해 서로 다른 도로를 몇 개 거쳐 다시 출발지로 돌아오는 "순환로"가 생기게 된다. 순환로가 지나가는 주거지들은 교통이 편리해지기 때문에 발전하게 된다.
3. 단, 균형 잡힌 발전을 위해, 한 주거지는 두 개 이상의 순환로에 속할 수 없다.

예를 들어, 청주시가 다음 그림처럼 8개의 주거지로 이루어져 있다고 하자.



민제가 1번과 3번 주거지를 잇는 도로를 설치한다면 1-2-4-3번 주거지를 연결하는 순환로가 생기고, 이 주거지들은 발전하게 된다.



이 상태에서 민제는 4번과 7번 주거지를 잇는 도로를 설치할 수 없는데, 4번 주거지가 두 개의 순환로에 속하게 되기 때문이다.



민제는 6번과 7번 주거지를 잇는 도로 역시 설치할 수 없다(이미 이 둘을 잇는 도로가 설치되어 있기 때문이다).



민제는 6번과 8번 주거지를 잇는 도로를 설치할 수 있고, 이 경우 6, 7, 8번 주거지가 추가로 발전하게 된다.



민제는 위와 같은 조건을 만족하면서 도로를 설치하되, 최대한 많은 주거지를 발전시키고자 한다. 민제가 최대 몇 개의 주거지를 발전시킬 수 있을지 알려주자.

Input

입력의 첫째 줄에는 주거지의 수를 의미하는 정수 N이 주어진다.
입력의 둘째 줄부터 N - 1개의 줄에 걸쳐 청주시의 도로 정보가
$A_i$ $B_i$
의 형태로 주어지는데, 이는 $A_i$번 주거지와 $B_i$번 주거지를 양방향으로 잇는 도로가 존재함을 의미한다.

[Subtask Info]

Subtask #1: 3 <= N <= 20.
Subtask #2: 3 <= N <= 2000.
Subtask #3: 3 <= N <= 200000.

Output

민제가 적절히 도로를 설치하여 발전시킬 수 있는 주거지 수의 최댓값을 정수 하나로 출력한다.

IO Example

입력 예제

8
4 2
6 7
2 1
5 4
3 4
7 8
4 6

출력 예제

7

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]