The Resistance is trying to take control over all planets in a particular solar system. This solar system is shaped like a tree. More precisely, some planets are connected by bidirectional hyperspace tunnels in such a way that there is a path between every pair of the planets, but removing any tunnel would disconnect some of them.

The Resistance already has measures in place that will, when the time is right, enable them to control every planet that is not remote. A planet is considered to be remote if it is connected to the rest of the planets only via a single hyperspace tunnel.

How much work is there left to be done: that is, how many remote planets are there?


-----Input-----

The first line of the input contains an integer N (2 ≤ N ≤ 1000) – the number of planets in the galaxy.

The next N - 1 lines describe the hyperspace tunnels between the planets. Each of the N - 1 lines contains two space-separated integers u and v (1 ≤ u, v ≤ N) indicating that there is a bidirectional hyperspace tunnel between the planets u and v. It is guaranteed that every two planets are connected by a path of tunnels, and that each tunnel connects a different pair of planets.


-----Output-----

A single integer denoting the number of remote planets.


-----Examples-----
Input
5
4 1
4 2
1 3
1 5

Output
3

Input
4
1 2
4 3
1 4

Output
2



-----Note-----

In the first example, only planets 2, 3 and 5 are connected by a single tunnel.

In the second example, the remote planets are 2 and 3.

Note that this problem has only two versions – easy and medium.

Difficulty: interview

Starter code:

Solutions:
N = int(input())
cnt = [0] * N
for n in range(N - 1):
    u, v = list(map(int, input().split()))
    cnt[u - 1] += 1
    cnt[v - 1] += 1

print(sum(x == 1 for x in cnt))


n = int(input().strip())
graph = [[] for i in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
count = 0
for g in graph:
    if len(g) < 2:
        count += 1
print(count)

N = int(input())
src = [tuple([int(x)-1 for x in input().split()]) for i in range(N-1)]
es = [[] for i in range(N)]
for a,b in src:
    es[a].append(b)
    es[b].append(a)
ans = 0
for e in es:
    if len(e) == 1:
        ans += 1
print(ans)


graph, num = {}, 0
n = int(input())
for i in range(n-1):
  a, b = [int(i) for i in input().split()]
  if a not in graph: graph[a] = []
  graph[a].extend([b])
  if b not in graph: graph[b] = []
  graph[b].extend([a])
  
for key in graph:
  if len(graph[key]) == 1: num += 1

print(num)

from collections import Counter
n = int(input())
C = Counter()
for _ in range(n - 1):
  C.update(list(map(int, input().split())))
print(sum(1 for a, b in list(C.items()) if b == 1)) 


n=int(input())
a,d,f=[],0,0
for i in range(n-1):
    k,l=list(map(int,input().split()))
    a.append(k)
    a.append(l)
for i in range(len(a)):
    d=0
    for j in range(len(a)):
        if i!=j and a[i]==a[j]:d=d+1
    if d==0:f=f+1
print(f)


n=int(input())
arr=[]
for _ in range(n):
    arr.append(0)
for _ in range(n-1):
    a,b=list(map(int,input().split()))
    arr[a-1]+=1 
    arr[b-1]+=1 
print(arr.count(1))


n = int(input())

q = [0] * n

for i in range(n - 1):
    u, v = list(map(int, input().split()))

    q[u - 1] += 1
    q[v - 1] += 1

print(q.count(1))


n=int(input())
graph=[[] for i in range(n)]
for i in range(n-1):
	x,y=map(int,input().split())
	graph[x-1].append(y)
	graph[y-1].append(x)
c=0
for i in range(n):
	if len(graph[i])==1:
		c+=1
print(c)

n = int(input())
myList = []
for k in range(0, n):
    myList.append(0)
counter = 0
for i in range(0, n - 1):
    a, b = list(map(int, input().split()))
    myList[a - 1] += 1
    myList[b - 1] += 1
for j in range(0, len(myList)):
    if myList[j] == 1:
        counter += 1
print(counter)


n = int(input())
tun = {}
for i in range(n):
    tun[i+1] = 0
for i in range(n-1):
    u,v = map(int,input().split())
    tun[u] += 1
    tun[v] += 1
ans = 0
for i in range(1,n+1):
    if tun[i] == 1:
        ans += 1
print(ans)

n = int(input())
dic = {}
for i in range(1, n+1):
  dic.update({i:0})
for i in range(n-1):
  s = input().split()
  dic[int(s[0])]+=1
  dic[int(s[1])]+=1

count = 0 
for x in dic.keys():
  if dic[x]==1:
    count+=1
    
print(count)

N = int(input())

output = [0] * N

for i in range(N - 1):
    u, v = [int(v) for v in input().split(' ')]
    output[u - 1] += 1
    output[v - 1] += 1

print(output.count(1))

n = int(input())
tree = [0] * (n+1)
for i in range(n-1):
    vex1, vex2= list(map(int,input().split()))
    tree[vex1] += 1
    tree[vex2] += 1
ans = 0
for i in range(n+1):
    if tree[i] == 1:
        ans += 1
print(ans)


n = int(input())
counter = 0
a = [[0 for j in range(n)] for i in range(n)]
for i in range(n - 1):
    i, j = map(int, input().split())
    a[i - 1][j - 1] = 1
    a[j - 1][i - 1] = 1

for element in a:
    if element.count(1) == 1:
        counter += 1

print(counter)

n = int(input())
m = [0 for i in range(n)]
for i in range(n - 1):
    u, v = list(map(int, input().split()))
    m[u - 1] += 1
    m[v - 1] += 1
print(m.count(1))


p=int(input())
a=[]
x=0
for i in range(p-1):
    a+=input().split()
for i in range(p):
    if a.count(str(i+1))==1:
        x+=1
print(x)


n = int(input())
li = [0] * n

for x in range(0,n-1):
    line = (input().split())
    for x in line:
        li[int(x)-1] += 1

print(li.count(1))

import sys
from collections import Counter

def main(args):
    n = int(input())
    counter = Counter()
    
    for _ in range(n - 1):
        u, v = list(map(int, input().split()))
        counter[u] += 1
        counter[v] += 1
    
    s = 0
    for c in range(n + 1):
        s += (counter[c] == 1)
    
    print(s)
def __starting_point():
    return(main(sys.argv))

__starting_point()

# -*- coding: utf - 8 -*-
"""""""""""""""""""""""""""""""""""""""""""""
|    author: mr.math - Hakimov Rahimjon     |
|    e-mail: mr.math0777@gmail.com          |
|    created: 14.04.2018 16:50              |
"""""""""""""""""""""""""""""""""""""""""""""
# inp = open("input.txt", "r"); input = inp.readline; out = open("output.txt", "w"); print = out.write
TN = 1


# ===========================================


def solution():
    n = int(input())
    l = [[0 for j in range(n)] for i in range(n)]
    ans = 0
    for i in range(n-1):
        u, v = list(map(int, input().split()))
        l[u-1][v-1] = 1
        l[v-1][u-1] = 1
    for i in l:
        if i.count(1) == 1: ans+=1
    print(ans)


# ===========================================
while TN != 0:
    solution()
    TN -= 1
# ===========================================
# inp.close()
# out.close()


n = int(input())
a = [0] * (n + 1)
for i in range(n - 1):
    v1, v2 = [int(i) for i in input().split()]
    a[v1] += 1
    a[v2] += 1
print(a.count(1))


# from dust i have come dust i will be

n=int(input())

a=[0]*(n+1)
for i in range(n-1):
    u,v=list(map(int,input().split()))
    a[u]+=1
    a[v]+=1

cnt=0
for i in range(1,n+1):
    if a[i]==1:
        cnt+=1

print(cnt)




n = int(input())
d = {}
for i in range(n - 1):
    u, v = map(int, input().split())
    if u not in d:
        d[u] = 1
    else:
        d[u] += 1
    if v not in d:
        d[v] = 1
    else:
        d[v] += 1
ans = 0
for i in range(1, n + 1):
    if d[i] == 1:
        ans += 1
print(ans)

N = int(input())
pairs = [tuple(map(int, input().split())) for i in range(N - 1)]

graph = {i: list() for i in range(1, N + 1)}

for el in pairs:
    x, y = el

    graph[x].append(y)
    graph[y].append(x)

print(sum(1 for i in range(1, N + 1) if len(graph[i]) == 1))


n = int(input())
li = [0] * n

for x in range(0,n-1):
    line = (input().split())
    for x in line:
        li[int(x)-1] += 1

print(li.count(1))