You are given an undirected tree consisting of $n$ vertices. An undirected tree is a connected undirected graph with $n - 1$ edges.

Your task is to add the minimum number of edges in such a way that the length of the shortest path from the vertex $1$ to any other vertex is at most $2$. Note that you are not allowed to add loops and multiple edges.


-----Input-----

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

The following $n - 1$ lines contain edges: edge $i$ is given as a pair of vertices $u_i, v_i$ ($1 \le u_i, v_i \le n$). It is guaranteed that the given edges form a tree. It is guaranteed that there are no loops and multiple edges in the given edges.


-----Output-----

Print a single integer — the minimum number of edges you have to add in order to make the shortest distance from the vertex $1$ to any other vertex at most $2$. Note that you are not allowed to add loops and multiple edges.


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

Output
2

Input
7
1 2
1 3
2 4
2 5
3 6
1 7

Output
0

Input
7
1 2
2 3
3 4
3 5
3 6
3 7

Output
1



-----Note-----

The tree corresponding to the first example: [Image] The answer is $2$, some of the possible answers are the following: $[(1, 5), (1, 6)]$, $[(1, 4), (1, 7)]$, $[(1, 6), (1, 7)]$.

The tree corresponding to the second example: [Image] The answer is $0$.

The tree corresponding to the third example: [Image] The answer is $1$, only one possible way to reach it is to add the edge $(1, 3)$.

Difficulty: HARD
Tags: Dynamic programming

Graph algorithms

Greedy algorithms
Skill types: Dynamic programming

Greedy algorithms
Expected Time Complexity: O(N)

Starter code:

Solutions:
import sys
from collections import deque
mod = 10 ** 9 + 7
INF = float('inf')

def inp():
	return int(sys.stdin.readline())

def inpl():
	return list(map(int, sys.stdin.readline().split()))
n = inp()
edges = [[] for _ in range(n)]
for _ in range(n - 1):
	(a, b) = inpl()
	(a, b) = (a - 1, b - 1)
	edges[a].append(b)
	edges[b].append(a)
dist = [-1] * n
dist[0] = 0
pa = [-1] * n
se = set()
pq = []
q = deque()
q.append(0)
while q:
	now = q.popleft()
	for nx in edges[now]:
		if dist[nx] != -1:
			continue
		pa[nx] = now
		dist[nx] = dist[now] + 1
		if dist[nx] > 2:
			se.add(nx)
			pq.append((dist[nx], nx))
		q.append(nx)
pq = pq[::-1]
res = 0
ind = 0
while se:
	(d, v) = pq[ind]
	ind += 1
	if not v in se:
		continue
	res += 1
	pv = pa[v]
	se.discard(pv)
	for nv in edges[pv]:
		se.discard(nv)
print(res)


import sys

def get_new_edges(graph):
	n = len(graph)
	far_vertex = []
	pi = [None] * n
	visit = [False] * n
	visit[0]
	queue = [[0, 0]]
	i = 0
	while True:
		if i >= len(queue):
			break
		(current, d) = queue[i]
		i += 1
		visit[current] = True
		for v in graph[current]:
			if not visit[v]:
				u = [v, d + 1]
				pi[v] = current
				queue.append(u)
				if d + 1 > 2:
					far_vertex.append(u)
	far_vertex.sort(key=lambda x: -x[1])
	pos = [None] * n
	for (i, e) in enumerate(far_vertex):
		pos[e[0]] = i
	count = 0
	for i in range(len(far_vertex)):
		if not far_vertex[i]:
			continue
		(vertex, depth) = far_vertex[i]
		father = pi[vertex]
		count += 1
		if pos[father]:
			far_vertex[pos[father]] = None
		for u in graph[father]:
			if pos[u]:
				far_vertex[pos[u]] = None
	return count

def read_int_line():
	return list(map(int, sys.stdin.readline().split()))
vertex_count = int(input())
graph = [[] for _ in range(vertex_count)]
for i in range(vertex_count - 1):
	(v1, v2) = read_int_line()
	v1 -= 1
	v2 -= 1
	graph[v1].append(v2)
	graph[v2].append(v1)
print(get_new_edges(graph))


from sys import stdin
n = int(stdin.readline())
g = dict()
for i in range(n - 1):
	(u, v) = map(int, stdin.readline().split())
	g.setdefault(u - 1, []).append(v - 1)
	g.setdefault(v - 1, []).append(u - 1)
st = [0]
rank = [0] * n
tree = [0] * n
msk = [0] * n
rd = dict()
while len(st) > 0:
	top = st.pop()
	msk[top] = 1
	for c in g[top]:
		if msk[c] == 0:
			st.append(c)
			tree[c] = top
			rank[c] = rank[top] + 1
			rd.setdefault(rank[c], []).append(c)
max_rank = max(rank)
reach = [0] * n
build = [0] * n
ans = 0
for r in range(max_rank, 2, -1):
	for node in rd[r]:
		if reach[node] == 0:
			reach[node] = 1
			reach[tree[node]] = 1
			reach[tree[tree[node]]] = 1
			build[tree[node]] = 1
print(sum(build))


import sys
from collections import deque
import heapq
input = sys.stdin.readline
N = int(input())
EDGE = [list(map(int, input().split())) for i in range(N - 1)]
EDGELIST = [[] for i in range(N + 1)]
for (i, j) in EDGE:
	EDGELIST[i].append(j)
	EDGELIST[j].append(i)
REDG = [None for i in range(N + 1)]
QUE = deque([1])
check = [0] * (N + 1)
DEPTH = [None] * (N + 1)
i = 0
while QUE:
	NQUE = deque()
	i += 1
	while QUE:
		x = QUE.pop()
		DEPTH[x] = i
		check[x] = 1
		for to in EDGELIST[x]:
			if check[to] == 1:
				continue
			else:
				REDG[to] = x
				NQUE.append(to)
	QUE = NQUE
check = [0] * (N + 1)
check[1] = 1
LEAF = []
for i in range(2, N + 1):
	if len(EDGELIST[i]) == 1:
		LEAF.append((-DEPTH[i], i))
QUE = LEAF
heapq.heapify(QUE)
ANS = 0
while QUE:
	(dep, x) = heapq.heappop(QUE)
	if check[x] != 0 or dep >= -3:
		continue
	if check[REDG[x]] == 2:
		continue
	if check[x] == 0:
		check[x] = 1
	if check[REDG[REDG[x]]] == 0:
		check[REDG[REDG[x]]] = 1
	check[REDG[x]] = 2
	heapq.heappush(QUE, (-DEPTH[REDG[REDG[REDG[x]]]], REDG[REDG[REDG[x]]]))
	ANS += 1
print(ANS)


from collections import defaultdict
from collections import deque
import sys
input = sys.stdin.readline

def bfs(s):
	q = deque()
	q.append(s)
	dist = [-1] * (n + 1)
	dist[s] = 0
	p = []
	parent = [1] * (n + 1)
	ok = [0] * (n + 1)
	while q:
		i = q.popleft()
		d = dist[i]
		if d < 3:
			ok[i] = 1
		p.append(i)
		for j in G[i]:
			if dist[j] == -1:
				q.append(j)
				dist[j] = d + 1
				parent[j] = i
	ans = 0
	while p:
		i = p.pop()
		j = parent[i]
		if not ok[i]:
			ok[j] = 1
			ans += 1
			for k in G[j]:
				ok[k] = 1
	return ans
n = int(input())
G = [[] for _ in range(n + 1)]
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	G[u].append(v)
	G[v].append(u)
ans = bfs(1)
print(ans)