개선문

바이토티아(Byteotia)의 왕 바이테아사르(Byteasar)가 전투에서 승리하고 조국으로 돌아오고 있다. 바이토티아에는 $n$개의 마을이 있으며, 이들은 정확히 $n-1$개의 도로로 연결되어 있다. 어떤 마을에서 다른 어떤 마을로든 하나 이상의 도로로 이루어진 유일한 경로를 통해 갈 수 있다. 즉, 도로망은 트리(tree)를 이룬다.

왕은 방금 수도에 들어섰고, 그곳에는 승리한 왕이 지나가는 문인 개선문이 이미 세워져 있다. 따뜻한 환영에 감격한 바이테아사르는 지금 있는 수도에서 출발하여 바이토티아의 모든 마을을 방문하는 개선 행진을 계획한다.

하지만 다른 마을들은 아직 왕을 맞이할 준비가 되지 않았다. 그 마을들의 개선문은 착공조차 하지 않았기 때문이다. 왕의 믿음직한 참모가 이 일을 처리하려 한다. 그는 여러 건설 팀을 고용할 수 있는데, 각 팀은 하루에 어느 마을에든 개선문 하나를 세울 수 있다. 왕이 마을을 방문하는 순서는 아무도 모른다. 확실한 것은 매일 왕이 현재 있는 마을에서 인접한 마을로 이동한다는 점뿐이다. 왕은 같은 마을을 여러 번 방문할 수 있지만, 각 마을에는 개선문이 하나만 있으면 충분하다.

참모는 각 팀이 개선문을 몇 개 세우든 상관없이 모두에게 같은 정액 보수를 지급한다. 따라서 그는 왕이 처음 도착하는 순간 모든 마을에 이미 개선문이 세워져 있도록 보장하면서도, 되도록 적은 수의 팀을 고용하고자 한다. 필요한 팀의 최소 개수를 구하여 그를 도와라.

첫째 줄에 바이토티아의 마을 수를 나타내는 정수 $n$ ($1 \le n \le 300{,}000$)이 주어진다. 마을은 $1$번부터 $n$번까지 번호가 매겨져 있으며, $1$번 마을이 수도이다.

다음 $n-1$개의 줄에는 각각 공백으로 구분된 두 정수 $a$, $b$ ($1 \le a, b \le n$)가 주어지며, 이는 마을 $a$와 마을 $b$가 양방향 도로로 직접 연결되어 있음을 뜻한다.

참모가 고용해야 하는 팀의 최소 개수를 정수 하나로 출력한다.

첫째 날에는 마을 $2$, $3$, $4$에 개선문을 세워야 한다. 둘째 날에는 마을 $5$, $6$, $7$에 세우면 된다.