You are given a tree with $n$ vertices. You are allowed to modify the structure of the tree through the following multi-step operation:  Choose three vertices $a$, $b$, and $c$ such that $b$ is adjacent to both $a$ and $c$.  For every vertex $d$ other than $b$ that is adjacent to $a$, remove the edge connecting $d$ and $a$ and add the edge connecting $d$ and $c$.  Delete the edge connecting $a$ and $b$ and add the edge connecting $a$ and $c$. 

As an example, consider the following tree: [Image] 

The following diagram illustrates the sequence of steps that happen when we apply an operation to vertices $2$, $4$, and $5$: [Image] 

It can be proven that after each operation, the resulting graph is still a tree.

Find the minimum number of operations that must be performed to transform the tree into a star. A star is a tree with one vertex of degree $n - 1$, called its center, and $n - 1$ vertices of degree $1$.


-----Input-----

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

The $i$-th of the following $n - 1$ lines contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$, $u_i \neq v_i$) denoting that there exists an edge connecting vertices $u_i$ and $v_i$. It is guaranteed that the given edges form a tree.


-----Output-----

Print a single integer  — the minimum number of operations needed to transform the tree into a star.

It can be proven that under the given constraints, it is always possible to transform the tree into a star using at most $10^{18}$ operations.


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

Output
1

Input
4
2 4
4 1
3 4

Output
0



-----Note-----

The first test case corresponds to the tree shown in the statement. As we have seen before, we can transform the tree into a star with center at vertex $5$ by applying a single operation to vertices $2$, $4$, and $5$.

In the second test case, the given tree is already a star with the center at vertex $4$, so no operations have to be performed.

Difficulty: VERY_HARD
Tags: Graph algorithms

Graph traversal

Constructive algorithms

Complete search

Tree algorithms

Flows and cuts
Skill types: Complete search

Starter code:

Solutions:
import sys
input = sys.stdin.readline
n = int(input())
E = [[] for i in range(n + 1)]
for i in range(n - 1):
	(x, y) = list(map(int, input().split()))
	E[x].append(y)
	E[y].append(x)
C = [-1] * (n + 1)
Q = [1]
C[1] = 0
while Q:
	x = Q.pop()
	for to in E[x]:
		if C[to] == -1:
			C[to] = 1 - C[x]
			Q.append(to)
B = C.count(0)
W = C.count(1)
print(min(B, W) - 1)


import sys
input = sys.stdin.readline
n = int(input())
graph = [[] for _ in range(n)]
for j in range(n - 1):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	graph[x].append(y)
	graph[y].append(x)
color = [-1] * n
tem = [0]
visit = [0] * n
color[0] = 0
while tem != []:
	x = tem.pop()
	for i in graph[x]:
		if color[i] == -1:
			visit[i] = 1
			color[i] = 1 - color[x]
			tem.append(i)
k = color.count(1)
print(min(k, n - k) - 1)


import sys
input = sys.stdin.readline
import collections
from collections import defaultdict
n = int(input())

def bfs(root):
	visited = [0] * (n + 1)
	queue = collections.deque([root])
	visited[root] = 1
	while queue:
		vertex = queue.popleft()
		for i in graph[vertex]:
			if visited[i] == 0:
				depth[i] = depth[vertex] + 1
				queue.append(i)
				visited[i] = 1
graph = defaultdict(list)
for i in range(n - 1):
	(u, v) = map(int, input().split())
	graph[u - 1].append(v - 1)
	graph[v - 1].append(u - 1)
depth = [0] * n
depth[0] = 0
bfs(0)
(odd, even) = (0, 0)
for i in depth:
	if i & 1:
		odd += 1
	else:
		even += 1
print(min(odd, even) - 1)


a = int(input())
c = list()
for i in range(a + 1):
	c.append(list())
for i in range(a - 1):
	(g, h) = map(int, input().split())
	c[g].append(h)
	c[h].append(g)
q = list()
p = 0
k = 1
q.append(1)
odw = list()
wyn = 0
for i in range(a + 1):
	odw.append(0)
while k > p:
	x = q[p]
	chk = 0
	if x < 0:
		x = -x
		wyn += 1
		chk = 1
	p += 1
	odw[x] = 1
	for s in c[x]:
		if odw[s] == 0:
			q.append(s if chk > 0 else -s)
			k += 1
			odw[s] = 1
wyn = wyn - 1
if wyn > a - (wyn + 1) - 1:
	wyn = a - wyn - 2
print(wyn)


import os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
n = int(input())
connectionList = []
for _ in range(n):
	connectionList.append([])
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	connectionList[a - 1].append(b - 1)
	connectionList[b - 1].append(a - 1)
colorVertex = [-1] * n
isAdded = [False] * n
redSum = 0
blackSum = 0
colorVertex[0] = 0
queue = [(0, 0)]
isAdded[0] = True
queueIndex = 0
while queueIndex < len(queue):
	curElem = queue[queueIndex]
	queueIndex += 1
	colorVertex[curElem[0]] = curElem[1]
	if curElem[1] == 0:
		redSum += 1
	else:
		blackSum += 1
	for elem in connectionList[curElem[0]]:
		if not isAdded[elem]:
			isAdded[elem] = True
			queue.append((elem, 1 - curElem[1]))
print(min(redSum, blackSum) - 1)


n = int(input())
adj = [[] for i in range(n)]
depth = [-1] * n
depth[0] = 0
(odd, even, q) = (0, 1, [0])
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	adj[u - 1].append(v - 1)
	adj[v - 1].append(u - 1)
while q:
	nex = q.pop()
	for v in adj[nex]:
		if depth[v] == -1:
			depth[v] = depth[nex] + 1
			if depth[v] & 1:
				odd += 1
			else:
				even += 1
			q.append(v)
print(min(odd, even) - 1)


import sys
import collections

def input():
	return sys.stdin.readline().rstrip()

def split_input():
	return [int(i) for i in input().split()]
n = int(input())
color = {}
edges = [[] for _ in range(n)]
for i in range(n - 1):
	(u, v) = split_input()
	edges[u - 1].append(v - 1)
	edges[v - 1].append(u - 1)
color[0] = 0
de = collections.deque([])
de.append(0)
while len(de) > 0:
	u = de.popleft()
	for v in edges[u]:
		if v not in color:
			color[v] = 1 - color[u]
			de.append(v)
l = list(color.values())
z = l.count(0)
o = l.count(1)
print(min(z, o) - 1)


import sys
sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

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

def MI():
	return map(int, sys.stdin.readline().split())

def MI1():
	return map(int1, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]
n = II()
to = [[] for _ in range(n)]
for _ in range(n - 1):
	(u, v) = MI1()
	to[u].append(v)
	to[v].append(u)
dp = [0] * n
ch = [0] * n
stack = [(0, -1)]
first = [True] * n
while stack:
	(u, pu) = stack.pop()
	if first[u]:
		first[u] = False
		stack.append((u, pu))
		for v in to[u]:
			if v == pu:
				continue
			stack.append((v, u))
	else:
		for v in to[u]:
			if v == pu:
				continue
			ch[u] += 1 + dp[v]
			dp[u] += ch[v]
stack = [(0, -1)]
while stack:
	(u, pu) = stack.pop()
	for v in to[u]:
		if v == pu:
			continue
		dpvu = dp[u] - ch[v]
		chvu = ch[u] - dp[v] - 1
		dp[v] += chvu
		ch[v] += dpvu + 1
		stack.append((v, u))
print(min(dp))


import sys
from collections import defaultdict as dd
from collections import deque
from fractions import Fraction as f
from copy import *
from bisect import *
from heapq import *
from math import *
from itertools import permutations

def eprint(*args):
	print(*args, file=sys.stderr)
zz = 1
if zz:
	input = sys.stdin.readline
else:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('all.txt', 'w')

def li():
	return [int(x) for x in input().split()]

def fli():
	return [float(x) for x in input().split()]

def gi():
	return [x for x in input().split()]

def fi():
	return int(input())

def si():
	return list(input().rstrip())

def mi():
	return map(int, input().split())

def gh():
	sys.stdout.flush()

def graph(n, m):
	for i in range(m):
		(x, y) = mi()
		a[x].append(y)
		a[y].append(x)

def bo(i):
	return ord(i) - ord('a')
tt = 1
while tt > 0:
	tt -= 1
	n = fi()
	a = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(x, y) = mi()
		a[x].append(y)
		a[y].append(x)
	dis = [0 for i in range(n + 1)]
	q = deque()
	q.append(1)
	vis = [0 for i in range(n + 1)]
	vis[1] = 1
	while len(q):
		z = q.popleft()
		for j in a[z]:
			if vis[j] == 0:
				vis[j] = 1
				dis[j] = dis[z] ^ 1
				q.append(j)
	print(min(dis[1:].count(0), dis[1:].count(1)) - 1)


import sys
from math import ceil, sqrt, sin, pi, tan
from collections import defaultdict
read = sys.stdin.buffer.readline
import heapq
mi = lambda : map(int, read().split())
li = lambda : list(mi())
cin = lambda : int(read())

def ispd(s):
	n = len(s)
	if s[:n // 2] == s[[n // 2 + 1, n // 2][n % 2 == 0]:][::-1]:
		return True
	return False
for _ in range(1):
	n = cin()
	g = {i: [] for i in range(1, n + 1)}
	for i in range(n - 1):
		(u, v) = mi()
		g[u].append(v)
		g[v].append(u)
	(black, white) = (0, 0)
	st = [[1, 0]]
	vis = [0] * (n + 1)
	vis[1] = 1
	while st:
		(u, ct) = (st[-1][0], st[-1][1])
		st.pop()
		ct = 1 - ct
		if ct == 1:
			white += 1
		else:
			black += 1
		for v in g[u]:
			if vis[v] == 0:
				st.append([v, ct])
				vis[v] = 1
	print(min(black, white) - 1)


n = int(input())
allNodes = []
for i in range(n):
	allNodes.append([i])
for i in range(n - 1):
	(u, v) = map(int, input().split())
	allNodes[u - 1].append(v - 1)
	allNodes[v - 1].append(u - 1)
black = 0
white = 0
from collections import deque
q = deque([])
q.append(0)
visited = [-1] * n
visited[0] = 1
while len(q) != 0:
	e = q.pop()
	for i in allNodes[e][1:]:
		if visited[i] == -1:
			q.append(i)
			visited[i] = 1 - visited[e]
m = min(visited.count(1), visited.count(0))
print(m - 1)


import sys
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))
(n,) = I()
g = [[] for i in range(n + 1)]
for i in range(n - 1):
	(u, v) = I()
	g[u].append(v)
	g[v].append(u)
l = [0, 0]
vis = [0] * (n + 1)
st = [[1, 0]]
while st:
	(u, d) = st.pop()
	vis[u] = 1
	l[d] += 1
	for v in g[u]:
		if vis[v] == 0:
			vis[v] = 1
			st.append([v, (d + 1) % 2])
print(min(l) - 1)


from collections import defaultdict
n = int(input())
graph = defaultdict(list)
for i in range(n - 1):
	l = list(map(int, input().split()))
	graph[l[0]].append(l[1])
	graph[l[1]].append(l[0])
color_v = [-1] * (n + 1)
color_v[1] = 0
q = [1]
while q:
	x = q.pop()
	for i in graph[x]:
		if color_v[i] == -1:
			color_v[i] = 1 - color_v[x]
			q.append(i)
print(min(color_v.count(1), color_v.count(0)) - 1)


import sys
input = sys.stdin.readline
n = int(input())
adj = [[] for i in range(n)]
for _ in range(n - 1):
	(u, v) = list(map(int, input().split()))
	adj[u - 1].append(v - 1)
	adj[v - 1].append(u - 1)
depth = [-1] * n
depth[0] = 0
odd = 0
even = 1
q = [0]
while q:
	nex = q.pop()
	for v in adj[nex]:
		if depth[v] == -1:
			depth[v] = depth[nex] + 1
			if depth[v] & 1:
				odd += 1
			else:
				even += 1
			q.append(v)
print(min(odd, even) - 1)


import sys
from collections import defaultdict

def rl():
	return sys.stdin.readline().strip()

def BFS(s, nbrs):
	level = defaultdict(int)
	ind = 0
	level[ind] += 1
	frontier = [s]
	visited = {s}
	while frontier:
		next = []
		ind += 1
		for u in frontier:
			for v in nbrs[u]:
				if v not in visited:
					next.append(v)
					visited.add(v)
					level[ind] += 1
		frontier = next
	return level
n = int(rl())
vert = []
nbrs = defaultdict(list)
for i in range(n - 1):
	vert.append(list(map(int, rl().split())))
	j = vert[-1][0]
	k = vert[-1][1]
	nbrs[j].append(k)
	nbrs[k].append(j)
new = 0
counter = BFS(1, nbrs)
for i in range(2, n - 1, 2):
	new += counter[i]
ans = min(n - 2 - new, new)
print(ans)


import sys

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return map(int, minp().split())

def solve():
	n = mint()
	e = [[] for i in range(n)]
	for _ in range(n - 1):
		(u, v) = mints()
		e[u - 1].append(v - 1)
		e[v - 1].append(u - 1)
	q = [None] * n
	d = [None] * n
	c = [0, 0]
	q[0] = 0
	d[0] = 0
	ql = 0
	qr = 1
	while ql < qr:
		x = q[ql]
		ql += 1
		dd = d[x]
		c[dd] += 1
		dd ^= 1
		for v in e[x]:
			if d[v] is None:
				d[v] = dd
				q[qr] = v
				qr += 1
	print(min(c) - 1)
solve()


import collections as cc
import sys
I = lambda : list(map(int, input().split()))
(n,) = I()
g = cc.defaultdict(list)
for i in range(n - 1):
	(x, y) = I()
	g[x].append(y)
	g[y].append(x)
col = [-1] * (n + 1)
b = 0
w = 0
visi = [0] * (n + 1)
st = cc.deque()
st.append(1)
col[1] = 1
w += 1
while st:
	x = st.pop()
	visi[x] = 1
	for y in g[x]:
		if not visi[y]:
			col[y] = col[x] ^ 1
			st.append(y)
b = col.count(1)
w = col.count(0)
print(min(b, w) - 1)


import sys
import collections
inpy = [int(x) for x in sys.stdin.read().split()]
n = inpy[0]
memo = [set() for _ in range(n + 1)]
for i in range(1, len(inpy), 2):
	memo[inpy[i]].add(inpy[i + 1])
	memo[inpy[i + 1]].add(inpy[i])
que = collections.deque([(1, 0, 1)])
x = 0
while que:
	(index, pre, color) = que.pop()
	x += color
	for i in memo[index]:
		if i != pre:
			que.append((i, index, color ^ 1))
print(min(x, n - x) - 1)


from collections import defaultdict, deque
NONE = -1
WHITE = 0
BLACK = 1
nw = 0

def colorize(G, color, v, c):
	nonlocal nw
	nw += c == WHITE
	color[v] = c
	for u in G[v]:
		if color[u] == NONE:
			colorize(G, color, u, 1 - c)

def colorize_v2(G, stack, color):
	nw = 0
	while stack:
		(v, c) = stack.pop()
		color[v] = c
		nw += c == WHITE
		for u in G[v]:
			if color[u] == NONE:
				stack.append((u, 1 - c))
	return nw
n = int(input())
G = defaultdict(list)
for _ in range(n - 1):
	(u, v) = (int(x) for x in input().strip().split())
	G[u].append(v)
	G[v].append(u)
color = [NONE] * (n + 1)
stack = deque()
stack.append((1, WHITE))
nw = colorize_v2(G, stack, color)
print(min(nw, n - nw) - 1)