Remove the Tree

가중치 없는 트리에서 한 번의 연산은 선택한 경로 위의 모든 정점과 그에 연결된 간선을 지운다. 모든 간선을 지우는 최소 연산 횟수를 구한다.

보통5트리동적 계획법그리디DFS아직 제출이 없습니다시간 제한2초메모리 제한256 MB

문제 설명

예제3

문제

You are given an unweighted tree with $n$ vertices, numbered by integers from $1$ to $n$ . Let us define the remove operation as follows:

choose an arbitrary path in the current graph (a path with only one vertex is valid),
remove all vertices along this path, and all edges incident to them.

Calculate the minimum number of such operations to remove all edges. Note that it is allowed to leave some vertices not removed.

입력

The first line contains one integer $n$ ( $2 \le n \le 2 \cdot 10^5$ ), the number of vertices in the tree.

The $i$ -th of the next $n - 1$ lines contains integers $a\_i$ and $b\_i$ ( $1 \le a\_i, b\_i \le n$ , $a\_i \ne b\_i$ ), the numbers of vertices connected by edge $i$ .

It is guaranteed that the given graph is a tree.

출력

Output one integer: the minimum number of remove operations.

힌트

The third example corresponds to the following image: