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: interview

Starter code:

Solutions:
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
input = sys.stdin.readline

n = int(input())
adj = [[] for i in range(n)]
for _ in range(n - 1):
    u, v = 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)

n = int(input())
adj = [[] for i in range(n)]
for _ in range(n - 1):
    u, v = 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)

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)

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
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 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
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
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
 
#sys.setrecursionlimit(10**6)
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()
	#Pick all even or odd levels
	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)			


	





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:  # not assigned a color yet
            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())

# Adjacency list presentation of the graph, in which G[u] is a list of u's adjacent vertices.
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)



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

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]
#print(dp)
#print(ch)

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(dp)
#print(ch)

print(min(dp))