잔디 심기 timer 2s memory 512MB

농부 존은 농장에 풀을 심으려고 한다. 농장은 총 N개(1 \le N \le 10^5)의 풀밭이 있어서 1 이상 N 이하의 서로 다른 정수 번호가 매겨져 있다. 또한 풀밭을 연결하는 N-1개의 양방향 길이 있어서 모든 풀밭이 길을 통해 서로 연결되어 있다.

농부 존은 각 풀밭에 여러 종류의 풀을 심으려고 하는데, 사용하는 풀 종류의 수가 많을수록 비용이 더 많이 들기 때문에 어쩔 수 없이 최대한 적은 종류의 풀을 심어야 한다.

하지만 그의 소들은 입맛이 까다로워서 가까운 풀밭(하나 또는 두 개의 길을 거쳐 갈 수 있는 풀밭)에 같은 종류의 풀이 있다면, 소들이 반찬투정을 하며 말썽을 피우게 된다.

농부 존의 소들이 불평을 하지 않도록 적절하게 풀을 심기 위해 필요한 최소 잔디 종류 수를 구하여라.