해결한 사람
0
명
정답률
0.00
%
시간 제한
2000
ms
메모리 제한
245
MB
The Resistance은 특정 태양계의 모든 행성을 장악하려 한다. 이 태양계는 트리 형태이다. 더 정확히 말하면, 일부 행성들이 양방향 초공간 터널로 연결되어 있어 모든 행성 쌍 사이에 경로가 존재하지만, 어떤 터널이든 제거하면 행성 중 일부의 연결이 끊어진다.
The Resistance은 때가 되면 외딴 행성이 아닌 모든 행성을 장악할 수 있게 해 줄 조치를 이미 마련해 두었다. 어떤 행성이 단 하나의 초공간 터널을 통해서만 나머지 행성들과 연결되어 있다면 외딴 행성으로 간주한다.
해야 할 일이 얼마나 남아 있는가? 즉, 외딴 행성은 몇 개인가?
입력의 첫 번째 줄에는 은하에 있는 행성의 수를 나타내는 정수 N (2 ≤ N ≤ 1000)가 주어진다.
다음 N - 1개의 줄은 행성 사이의 초공간 터널을 설명한다. Each of the N - 1개의 줄에는 공백으로 구분된 두 정수 u와 v (1 ≤ u, v ≤ N)가 주어지며, 이는 행성 u와 v 사이에 양방향 초공간 터널이 있음을 나타낸다. 임의의 두 행성이 터널 경로로 연결되어 있으며, 각 터널은 서로 다른 행성 쌍을 연결함이 보장된다.
외딴 행성의 수를 나타내는 정수 하나를 출력한다.
4
1 2
4 3
1 4
2
5
4 1
4 2
1 3
1 5
3
첫 번째 예제에서는 행성 2, 3, 5만 단 하나의 터널로 연결되어 있다.
두 번째 예제에서 외딴 행성은 2와 3이다.
이 문제에는 쉬운 버전과 중간 버전, 두 가지 버전만 있다는 점에 유의하라.