주유소 timer 3초 memory 1024MB

KOI 국가는 N개의 마을로 이루어져 있다.
각 마을에는 1번 마을, 2번 마을, \cdots, N번 마을과 같이 번호가 붙어 있다.
그리고 도로가 N-1개 있는데, 각각의 도로는 서로 다른 두 마을을 잇고 있다.
각 도로에도 1번 도로, 2번 도로, ..., N-1번 도로와 같이 번호가 붙어 있다.
i번 도로는 x_i번 마을과 y_i번 마을을 직접 잇고 있다.
KOI 국가의 임의의 두 마을에 대해, 두 마을을 잇는 경로가 정확히 하나 존재한다.

x번 마을과 y번 마을을 잇는 경로는 x번 마을 - z_1번 마을 - z_2​번 마을 - \cdots​ - z_3​번 마을 - y번 마을과 같이
마을로 이루어진 수열 형태를 띤다.
이 수열이 다음 두 성질을 만족할 때 경로라고 부른다.

1. 경로를 이루는 인접한 두 마을 사이, 즉 x번 마을과 z_1번 마을 사이,
z_1번 마을과 z_2번 마을 사이, \cdots, z_t번 마을과 y번 마을 사이를 잇는 도로가 존재한다.

2. 경로에는 같은 마을이 두 번 등장하면 안 된다.
즉, 경로를 이루는 x번, z_1​, \cdots, z_t번, y번 마을은 모두 서로 다른 마을이어야 한다.

이 때 경로의 "길이"는, 경로를 이루는 도로의 수, 즉 t+1로 정의한다. 

마을들 중 몇 개의 마을을 골라 주유소를 설치하려고 한다.
KOI 국가의 법에 따라, 주유소는 다음 조건을 만족하도록 설치해야 한다.

• 길이 k인 임의의 경로에, 주유소가 설치된 마을이 적어도 하나 존재해야 한다.

위 조건을 만족하도록 가장 적은 개수의 마을을 골라 주유소를 설치하려고 한다.
이 때 설치해야 하는 주유소의 개수의 최솟값을 구하여라.