You're given a tree with $n$ vertices.

Your task is to determine the maximum possible number of edges that can be removed in such a way that all the remaining connected components will have even size.


-----Input-----

The first line contains an integer $n$ ($1 \le n \le 10^5$) denoting the size of the tree. 

The next $n - 1$ lines contain two integers $u$, $v$ ($1 \le u, v \le n$) each, describing the vertices connected by the $i$-th edge.

It's guaranteed that the given edges form a tree.


-----Output-----

Output a single integer $k$ — the maximum number of edges that can be removed to leave all connected components with even size, or $-1$ if it is impossible to remove edges in order to satisfy this property.


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

Output
1
Input
3
1 2
1 3

Output
-1
Input
10
7 1
8 4
8 10
4 7
6 5
9 3
3 5
2 10
2 5

Output
4
Input
2
1 2

Output
0


-----Note-----

In the first example you can remove the edge between vertices $1$ and $4$. The graph after that will have two connected components with two vertices in each.

In the second example you can't remove edges in such a way that all components have even number of vertices, so the answer is $-1$.

Difficulty: interview

Starter code:

Solutions:
def main():
  n = int(input())

  if n % 2 != 0:
    print(-1)
    return

  links = [[1, set()] for i in range(1, n+1)]
  W = 0
  L = 1

  i = 0
  while i < n-1:
    i += 1
    [a, b] = [int(x) for x in input().split()]
    links[a-1][L].add(b-1)
    links[b-1][L].add(a-1)

  count = 0
  sear = 0
  cur = 0
  while sear < n:
    li = cur
    l = links[li]
    if len(l[L]) != 1:
      if sear == cur:
        sear += 1
      cur = sear
      continue
    
    mi = l[L].pop()
    m = links[mi]
    if l[W] % 2 == 0:
      count += 1
    else:
      m[W] += 1

    m[L].remove(li)
    if mi < sear:
      cur = mi
    else:
      sear += 1
      cur = sear

  print(count)

main()


import collections;
def getIntList():
    return list(map(int, input().split()));
def getTransIntList(n):
    first=getIntList();
    m=len(first);
    result=[[0]*n for _ in range(m)];
    for i in range(m):
        result[i][0]=first[i];
    for j in range(1, n):
        curr=getIntList();
        for i in range(m):
            result[i][j]=curr[i];
    return result;
n=int(input());
if n>1:
    u, v=getTransIntList(n-1);
    for i in range(n-1):
        u[i]-=1;
        v[i]-=1;
def solve1(n, u, v):
    nears = [set() for _ in range(n)];
    for i in range(n-1):
        v1, v2 = u[i], v[i];
        nears[v1].add(v2);
        nears[v2].add(v1);
    prev=[0]*n;
    nexts=[set() for _ in range(n)];
    level=[0]*n;
    vStart=0;
    VertToCheck = collections.deque([vStart]);
    AllVerts=collections.deque();
    def defineNextPrev(vert):
        for v1 in nears[vert]:
            if v1!=prev[vert]:
                nexts[vert].add(v1);
                prev[v1]=vert;
                level[v1]=level[vert]+1;
                VertToCheck.append(v1);
    while len(VertToCheck)>0:
        currVert=VertToCheck.popleft();
        AllVerts.append(currVert);
        defineNextPrev(currVert);
    cutFlag=[False]*n;
    result=-1;
    while len(AllVerts)>0:
        vert=AllVerts.pop();
        for v1 in nexts[vert]:
            #print(cutFlag[vert], cutFlag[v1]);
            cutFlag[vert]=cutFlag[v1] ==cutFlag[vert];
            #print(cutFlag[vert])
        if cutFlag[vert]:
            result+=1;
    return result;
if n%2==1:
    print(-1);
else:
    print(solve1(n, u, v));

#!/usr/bin/env python3

from collections import deque

# pre(u) -- to do first at u
# proc(u, v) -- to do before switching from u (parent) to v (child)
# post(u) -- to do before switching to parent of u
def nrDFS(u, tos, pre, proc, post):
	n = len(tos)
	visited = [False for _ in range(n)]
	def go_to(cur, nxt):
		proc(cur, nxt)
		visited[nxt] = True
		pre(nxt)
		return nxt, 0
	stack = deque()
	cur, i = go_to(u, u)
	while True:
		if i < len(tos[cur]):
			if not visited[tos[cur][i]]:  # go to tos[cur][i]
				stack.append((cur, i))
				cur, i = go_to(cur, tos[cur][i])
			else:
				i += 1
				continue
		else:  # return to parent
			post(cur)
			if len(stack) == 0:
				break
			cur, i = stack.pop()
			i += 1
			continue



n = int(input().strip())
tos = [[] for _ in range(n)]
for _ in range(n - 1):
	[u, v] = list(map(int, input().strip().split()))
	tos[u - 1].append(v - 1)
	tos[v - 1].append(u - 1)

if n % 2 == 1:
	print(-1)
	return

def pre(u):
	pass

parent = [0 for _ in range(n)]
def proc(u, v):
	parent[v] = u

s = [0 for _ in range(n)]
def post(u):
	s[u] = 1 + sum(s[v] for v in tos[u] if v != parent[u])
		

nrDFS(0, tos, pre, proc, post)
print(n - 1 - sum(si % 2 for si in s))



def dfs(adj,i,parent):
	rem = 0
	tree_size = 1
	for item in adj[i]:
		if(item==parent):
			continue
		subtree_size,t = dfs(adj,item,i)
		rem += t
		if(subtree_size%2==0):
			rem +=1
		tree_size += subtree_size
	return (tree_size,rem)

def dfs_new(adj,n):
	stack = [(1,0)]
	sol = [None for i in range(n+1)]
	while(not len(stack)==0):
		i,parent = stack[-1]
		flag = True
		for item in adj[i]:
			if(item==parent):
				continue
			if(sol[item]==None):
				stack.append((item,i))
				flag = False
		if(flag):
			rem = 0
			tree_size = 1
			for item in adj[i]:
				if(item==parent):
					continue
				subtree_size,t = sol[item]
				if(subtree_size%2==0):
					rem+=1
				rem += t
				tree_size += subtree_size
			sol[i] = [tree_size,rem]
			stack.pop(-1)
	# print(sol)
	return sol[1][1]


n = int(input())
adj = [[] for i in range(n+1)]
for _ in range(n-1):
	u,v = map(int,input().split())
	adj[u].append(v)
	adj[v].append(u)
if(n%2==1):
	print(-1)
else:
	ans = dfs_new(adj,n)
	print(ans)

# n nodes, n - 1 edges, no possibility for loop
# so no need of maintaining a vis array, it'd not visit nodes previously visited
# as long as you don't go along the edge back which leads you to the current node


from collections import deque


def main():
    n = int(input())
    neis = [[] for i in range(n + 1)]
    vis = [0 for i in range(n + 1)]  # vis[i] -- the next node i is going to visit is neis[vis[i]]
    nodes = [1 for i in range(n + 1)]  # nodes[i] -- the number of nodes 'belong to' i(included i)
    pre = [None for i in range(n + 1)]  # pre[i] -- the node which leads to node i in fake dfs process
    cut = 0

    for _ in range(n - 1):
        u, v = list(map(int, input().split()))
        neis[u].append(v)
        neis[v].append(u)
    for i in range(1, n + 1):
        neis[i].append(None)

    start_point = 1
    pre[start_point] = start_point
    q = deque()
    q.append(start_point)

    while len(q) > 0:
        top = q[-1]
        nei = neis[top][vis[top]]

        if nei is not None:
            vis[top] += 1
            if nei != pre[top]:
                q.append(nei)
                pre[nei] = top
        else:
            if top != start_point:
                nodes[pre[top]] += nodes[top]
                if nodes[top] % 2 == 0:
                    cut += 1
            q.pop()

    if nodes[1] % 2 == 0:
        print(cut)
    else:
        print(-1)


def __starting_point():
    main()

__starting_point()

# n nodes, n - 1 edges, no possibility for loop
# so no need of maintaining a vis array, it'd not visit nodes previously visited
# as long as you don't go along the edge back which leads you to the current node


from collections import deque


def main():
    n = int(input())
    # don't use hash table
    neis = [[] for i in range(n + 1)]
    vis = [0 for i in range(n + 1)]  # vis[i] -- the next node i is going to visit is neis[vis[i]]
    nodes = [1 for i in range(n + 1)]  # nodes[i] -- the number of nodes 'belong to' i(included i)
    pre = [None for i in range(n + 1)]  # pre[i] -- the node which leads to node i in fake dfs process
    cut = 0

    for _ in range(n - 1):
        u, v = list(map(int, input().split()))
        neis[u].append(v)
        neis[v].append(u)
    for i in range(1, n + 1):
        neis[i].append(None)



    start_point = 1
    q = deque()
    q.append(start_point)

    while len(q) > 0:
        top = q[-1]
        nei = neis[top][vis[top]]

        if nei is not None:
            vis[top] += 1
            if nei != pre[top]:
                q.append(nei)
                pre[nei] = top
        else:
            if top != start_point:
                nodes[pre[top]] += nodes[top]
                if nodes[top] % 2 == 0:
                    cut += 1
            q.pop()

    if nodes[1] % 2 == 0:
        print(cut)
    else:
        print(-1)


def __starting_point():
    main()

__starting_point()

# n nodes, n - 1 edges, no possibility for loop
# so no need of maintaining a vis array, it'd not visit nodes previously visited
# as long as you don't go along the edge back which leads you to the current node


from collections import deque


def main():
    n = int(input())
    # don't use hash table
    neis = [[] for i in range(n + 1)]
    vis = [0 for i in range(n + 1)]  # vis[i] -- the next node i is going to visit is neis[vis[i]]
    nodes = [1 for i in range(n + 1)]  # nodes[i] -- the number of nodes 'belong to' i(included i)
    pre = [None for i in range(n + 1)]  # pre[i] -- the node which leads to node i in fake dfs process
    cut = 0

    for _ in range(n - 1):
        u, v = list(map(int, input().split()))
        neis[u].append(v)
        neis[v].append(u)

    start_point = 1
    pre[start_point] = start_point
    q = deque()
    q.append(start_point)

    while len(q) > 0:
        top = q[-1]

        if vis[top] < len(neis[top]):
            nei = neis[top][vis[top]]
            vis[top] += 1
            if nei != pre[top]:
                q.append(nei)
                pre[nei] = top
        else:
            if top != start_point:
                nodes[pre[top]] += nodes[top]
                if nodes[top] % 2 == 0:
                    cut += 1
            q.pop()

    if nodes[1] % 2 == 0:
        print(cut)
    else:
        print(-1)


def __starting_point():
    main()

__starting_point()

# n nodes, n - 1 edges, no possibility for loop
# so no need of maintaining a vis array, it'd not visit nodes previously visited
# as long as you don't go along the edge back which leads you to the current node


from collections import deque


def main():
    n = int(input())
    # don't use hash table
    neis = [[] for i in range(n + 1)]
    for _ in range(n - 1):
        u, v = list(map(int, input().split()))
        neis[u].append(v)
        neis[v].append(u)

    def fake_dfs(start_point):
        nonlocal neis

        vis = [0 for i in range(n + 1)]  # vis[i] -- the next node i is going to visit is neis[vis[i]]
        nodes = [1 for i in range(n + 1)]  # nodes[i] -- the number of nodes 'belong to' i(included i)
        pre = [None for i in range(n + 1)]  # pre[i] -- the node which leads to node i in fake dfs process
        cut = 0

        q = deque()
        q.append(start_point)
        pre[start_point] = start_point

        while len(q) > 0:
            top = q[-1]

            if vis[top] < len(neis[top]):
                nei = neis[top][vis[top]]
                vis[top] += 1
                if nei != pre[top]:
                    q.append(nei)
                    pre[nei] = top
            else:
                if top != start_point:
                    nodes[pre[top]] += nodes[top]
                    if nodes[top] & 1 == 0:
                        cut += 1
                q.pop()

        if nodes[1] & 1 == 0:
            print(cut)
        else:
            print(-1)

    fake_dfs(1)


def __starting_point():
    main()

__starting_point()

# n nodes, n - 1 edges, no possibility for loop
# so no need of maintaining a vis array, it'd not visit nodes previously visited
# as long as you don't go along the edge back which leads you to the current node


from collections import deque
from array import array


def main():
    n = int(input())
    # don't use hash table
    neis = [[] for i in range(n + 1)]
    for _ in range(n - 1):
        u, v = list(map(int, input().split()))
        neis[u].append(v)
        neis[v].append(u)

    def fake_dfs(start_point):
        nonlocal neis

        # vis = [0 for i in range(n + 1)]  # vis[i] -- the next node i is going to visit is neis[vis[i]]
        # nodes = [1 for i in range(n + 1)]  # nodes[i] -- the number of nodes 'belong to' i(included i)
        # pre = [None for i in range(n + 1)]  # pre[i] -- the node which leads to node i in fake dfs process
        vis = array('I', (0 for _ in range(n + 1)))
        nodes = array('I', (1 for _ in range(n + 1)))
        pre = array('I', (0 for _ in range(n + 1)))
        cut = 0

        q = deque()
        q.append(start_point)
        pre[start_point] = start_point

        while len(q) > 0:
            top = q[-1]

            if vis[top] < len(neis[top]):
                nei = neis[top][vis[top]]
                vis[top] += 1
                if nei != pre[top]:
                    q.append(nei)
                    pre[nei] = top
            else:
                if top != start_point:
                    nodes[pre[top]] += nodes[top]
                    if nodes[top] & 1 == 0:
                        cut += 1
                q.pop()

        if nodes[1] & 1 == 0:
            print(cut)
        else:
            print(-1)

    fake_dfs(1)


def __starting_point():
    main()

__starting_point()

n = int(input())

if n % 2 != 0:
  print(-1)
  return

links = [[1, set()] for i in range(1, n+1)]
W = 0
L = 1

i = 0
while i < n-1:
  i += 1
  [a, b] = [int(x) for x in input().split()]
  links[a-1][L].add(b-1)
  links[b-1][L].add(a-1)

count = sear = cur = 0
while sear < n:
  li = cur
  l = links[li]
  if len(l[L]) != 1:
    if sear == cur:
      sear += 1
    cur = sear
    continue

  mi = l[L].pop()
  m = links[mi]
  if l[W] % 2 == 0:
    count += 1
  else:
    m[W] += 1

  m[L].remove(li)
  if mi < sear:
    cur = mi
  else:
    sear += 1
    cur = sear

print(count)


def main():
    n = int(input())

    g = [[] for i in range(n + 5)]
    vh = [[] for i in range(n + 5)]
    size = [1 for i in range(n + 5)]
    par = [i for i in range(n + 5)]

    if n % 2 == 1:
        print(-1)
        return

    for i in range(n - 1):
        u, v = map(int, input().split())
        g[u].append(v)
        g[v].append(u)

    q = [[1, 1]]
    vh[1].append(1)
    max_height = 1
    while len(q) > 0:
        u, hu = q.pop()
        #print(u)
        leaf_node = True

        for v in g[u]:
            if v == par[u]:
                continue
            hv = hu + 1
            par[v] = u
            q.append([v, hv])
            vh[hv].append(v)
            max_height = max(max_height, hv)

    while max_height > 0:
        for v in vh[max_height]:
            size[par[v]] += size[v]
        max_height -= 1

    print(n - 1 - sum(size[i] % 2 for i in range(1, n + 1)))

main()

def dfs_new(adj,n):
	stack = [(1,0)]
	sol = [None for i in range(n+1)]
	while(not len(stack)==0):
		i,parent = stack[-1]
		flag = True
		for item in adj[i]:
			if(item==parent):
				continue
			if(sol[item]==None):
				stack.append((item,i))
				flag = False
			# print(stack, flag)
			# print(sol)
		if(flag):
			rem = 0
			tree_size = 1
			for item in adj[i]:
				if(item==parent):
					continue
				subtree_size,t = sol[item]
				# print(item, subtree_size, t)
				if(subtree_size%2==0):
					rem+=1
				rem += t
				tree_size += subtree_size
			sol[i] = [tree_size,rem]
			stack.pop(-1)
	# print(sol)
	return sol[1][1]


n = int(input())
adj = [[] for i in range(n+1)]
for _ in range(n-1):
	u,v = list(map(int,input().split()))
	adj[u].append(v)
	adj[v].append(u)
if(n%2==1):
	print(-1)
else:
	ans = dfs_new(adj,n)
	print(ans)


n=int(input())
if n&1>0:print(-1);return
g=[[] for _ in range(n) ]
for _ in range(n-1):
    a,b=map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)
c=[1]*n
v=[-1]*n
v[0]=0
s=[0]
while s:
    x=s[-1]
    k=False
    for j in g[x]:
        if v[j]==-1:
            v[j]=x
            s.append(j)
            k=True
    if not k:
        s.pop()
        c[v[x]]+=c[x]
o=0
for j in c[1:]:
    if j&1<1:o+=1 
print(o)

def dfs(g, s):
    visited = set([s])
    stack = [s]
    res = 0
    
    while len(stack) > 0:
        s = stack.pop()
        cnt = 0

        cnt += 1 #count the size of the current subtree
        visited.add(s)        
        
        for v in g[s]:
            if v not in visited:
                cnt += 1
                stack.append(v)

        if cnt % 2 == 0:
            res += 1

    return res // 2

def dfs2(g,s,n):
    parent = [0]*(n+1)
    counts = [1]*(n+1)
    stack = []

    stack.append(s)
        
    while stack:
        v = stack[-1]
        empty_s = True
        
        if not parent[v]:
            parent[v] = 1
        
        for node in g[v]:
            if not parent[node]:
                parent[node] = v
                stack.append(node)
                empty_s = False
                
        if empty_s:
            stack.pop()
            counts[parent[v]] += counts[v]
    
    return sum([1 for x in counts[2:] if x % 2 == 0])

def solve():
    #f = open("Cut em all - DFS.txt")
    n = int(input())
    
    tree = [[] for i in range(n+1)]
    
    for i in range(n-1):
        u ,v = input().split()
        u, v = int(u), int(v)
        tree[v].append(u)
        tree[u].append(v)
    
    if n % 2 != 0:
        print (-1)
        return

    #print (dfs(tree, 1))
    print (dfs2(tree, 1, n))

def __starting_point():
    solve()
__starting_point()

n=int(input())
if n&1>0:print((-1));return
g=[[] for _ in range(n) ]
for _ in range(n-1):
    a,b=list(map(int,input().split()))
    g[a-1].append(b-1)
    g[b-1].append(a-1)
c=[1]*n
v=[-1]*n
v[0]=0
s=[0]
while s:
    x=s[-1]
    k=False
    for j in g[x]:
        if v[j]==-1:
            v[j]=x
            s.append(j)
            k=True
    if not k:
        s.pop()
        c[v[x]]+=c[x]
o=0
for j in c[1:]:
    if j%2==0:
        o+=1 
print(o)


def main():
    n = int(input())
    if n % 2 != 0: print((-1)); return;

    graph = [[] for _ in range(n)]

    for _ in range(n-1):
        a, b = list(map(int, input().split()))
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)

    res = 0    
    stack = [0]
    visited = [-1] * n
    visited[0] = 0

    count = [1] * n

    while stack:
        s = stack[-1]
        flag = False

        for v in graph[s]:
            if visited[v] == -1:
                stack.append(v)
                visited[v] = s
                flag = True

        if not flag:
            stack.pop()
            if s == 0: break;
            count[visited[s]] += count[s]

    res = sum([1 if i % 2 == 0 else 0 for i in count])
    print(res-1)

def __starting_point():
    main()


__starting_point()

from sys import stdin
inp = stdin.readline
n, ans = int(inp()), 0
if n & 1:
    print(-1)
    return
g = {i: [set(), 0] for i in range(1, n + 1)}
visited = [0] * (n + 1)
for _ in range(n - 1):
    a, b = map(int, inp().split())
    g[a][0].add(b)
    g[b][0].add(a)
visited = [0, 1] + [0] * (n - 1)
q = [1]
p = [0] * (n + 1)
while q:
    v = q.pop()
    if v != 1 and len(g[v][0]) == 1:
        g[p[v]][0].remove(v)
        g[p[v]][1] += g[v][1] + 1
        q.append(p[v])
        if g[v][1] & 1: ans += 1
        continue
    for i in g[v][0]:
        if not visited[i]:
            visited[i] = True
            p[i] = v
            q.append(i)
            if min(g[v][1], g[i][1]) & 1:
                ans += 1
print(ans)

n = int(input())
if n%2 == 1:
    print(-1)
    return
graph = {}
for i in range(n-1):
    v, u = map(int, input().strip().split())
    v -= 1; u -= 1
    if v in graph:
        graph[v].append(u)
    else:
        graph[v] = [u]
    
    if u in graph:
        graph[u].append(v)
    else:
        graph[u] = [v]
countArr = [1 for i in range(n)]
s = [0]
vis = [-1 for i in range(n)]
while s:
    curr = s[-1]
    k = False
    for i in graph[curr]:
        if vis[i] == -1:
            vis[i] = curr
            s.append(i)
            k = True
    if not k:
        if curr != 0:
            countArr[vis[curr]] += countArr[curr]
        s.pop()
o = 0
for i in countArr[1:]:
    if i%2 == 0: o += 1
print(o)

n = int(input())
if n % 2 == 1:
    print(-1)
    return

adj = [[] for _ in range(n+1) ]
for _ in range(n-1):
    u, v = list(map(int, input().split()))
    adj[u].append(v)
    adj[v].append(u)

cnt = [1] * (n+1)
prt = [-1] * (n+1)
prt[1] = 1
stk = [1]
while stk:
    u = stk[-1]
    k = False
    for v in adj[u]:
        if prt[v] == -1:
            prt[v] = u
            stk.append(v)
            k = True
    if not k:
        stk.pop()
        cnt[prt[u]] += cnt[u]
res = 0
for j in cnt[2:]:
    if j % 2 == 0:
        res += 1 
print(res)


import sys

# import bisect
# from collections import deque
# sys.setrecursionlimit(100000)
 
Ri = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()
 
def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return list(map(int, input().split()))
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
INF = 10 ** 18
MOD = 10 ** 9 + 7
 
n =int(ri())
lis = [[] for i in range(n)]
for _ in range(n-1):
    a,b = Ri()
    a-=1
    b-=1
    lis[a].append(b)
    lis[b].append(a)
visit =[-1]*n
no = [1]*n
sta = [0]
visit[0]= True
if n&1 == 1:
    print(-1)
else:
    while len(sta) > 0:
        top = sta[-1]
        ret = True
        for i in range(len(lis[top])):
            if visit[lis[top][i]] == -1:
                visit[lis[top][i]] = top
                ret = False
                sta.append(lis[top][i])
        if ret:
            if top != 0:
                no[visit[top]]+=no[top]
            sta.pop()
    ans=0
    no= no[1:]
    for i in no:
        if i&1 == 0:
            ans+=1
    print(ans)



import os, sys, bisect, copy
from collections import defaultdict, Counter, deque
from functools import lru_cache   #use @lru_cache(None)
if os.path.exists('in.txt'): sys.stdin=open('in.txt','r')
if os.path.exists('out.txt'): sys.stdout=open('out.txt', 'w')
#
def input(): return sys.stdin.readline()
def mapi(arg=0): return list(map(int if arg==0 else str,input().split()))
#------------------------------------------------------------------
import sys
sys.setrecursionlimit(10**5)
from types import GeneratorType
#use:- put @bootstrap overrecursive function
def bootstrap(func, stack=[]):
    def wrapped_function(*args, **kwargs):
        if stack:
            return func(*args, **kwargs)
        else:
            call = func(*args, **kwargs)
            while True:
                if type(call) is GeneratorType:
                    stack.append(call)
                    call = next(call)
                else:
                    stack.pop()
                    if not stack:
                        break
                    call = stack[-1].send(call)
            return call
    return wrapped_function

n = int(input())
gr = defaultdict(list)
for i in range(n-1):
    x,y = mapi()
    gr[x].append(y)
    gr[y].append(x)

sz = [0]*(n+1)
res = 0
@bootstrap
def dfs(s,par):
    nonlocal res
    sz[s] = 1
    for u in gr[s]:
        if par==u: continue
        sz[s]+= yield dfs(u,s)
    if sz[s]%2==0 and s!=1:
        res+=1
    yield sz[s]
dfs(1,-1)
#print(*sz)
if sz[1]&1:
    print(-1)
else:
    print(res)


n = int(input())
if n % 2 == 1:
    print(-1)
else:
    edges = [[] for i in range(n)]
    for i in range(n-1):
        [a,b] = [int(j) for j in input().split()]
        edges[a-1].append(b-1)
        edges[b-1].append(a-1)
    dfs_stack = [0]
    c = [1 for i in range(n)]
    visited = [-1 for i in range(n)]
    visited[0] = 0
    
    while dfs_stack != []:
        current_node = dfs_stack[-1]
        can_go_further = False
        for i in edges[current_node]:
            if visited[i] == -1:
                dfs_stack.append(i)
                visited[i] = current_node
                can_go_further = True
        if can_go_further == False:
            dfs_stack.pop(-1)
            c[visited[current_node]] += c[current_node]
    
    ans = 0
    for i in c[1:]:
        if i % 2 == 0:
            ans += 1
    print(ans)

n = int(input())
if n % 2 == 1:
    print(-1)
else:
    edges = [[] for i in range(n)]
    for i in range(n-1):
        [a,b] = [int(j) for j in input().split()]
        edges[a-1].append(b-1)
        edges[b-1].append(a-1)
    dfs_stack = [0]
    comp_size = [1 for i in range(n)]
    visited = [-1 for i in range(n)]
    visited[0] = 0
    
    while dfs_stack != []:
        current_node = dfs_stack[-1]
        can_go_further = False
        for i in edges[current_node]:
            if visited[i] == -1:
                dfs_stack.append(i)
                visited[i] = current_node
                can_go_further = True
        if can_go_further == False:
            dfs_stack.pop(-1)
            comp_size[visited[current_node]] += comp_size[current_node]
    
    ans = 0
    for i in comp_size[1:]:
        if i % 2 == 0:
            ans += 1
    print(ans)

n = int(input())
if n % 2 == 1:
    print(-1)
else:
    edges = [[] for i in range(n)]
    for i in range(n-1):
        [a,b] = [int(j) for j in input().split()]
        edges[a-1].append(b-1)
        edges[b-1].append(a-1)
    dfs_stack = [0]
    comp_size = [1 for i in range(n)]
    visited = [-1 for i in range(n)]
    visited[0] = 0
    
    while dfs_stack != []:
        current_node = dfs_stack[-1]
        can_go_further = False
        for i in edges[current_node]:
            if visited[i] == -1:
                dfs_stack.append(i)
                visited[i] = current_node
                can_go_further = True
        if can_go_further == False:
            dfs_stack.pop(-1)
            comp_size[visited[current_node]] += comp_size[current_node]
    
    ans = 0
    for i in comp_size[1:]:
        if i % 2 == 0:
            ans += 1
    print(ans)

#!/usr/bin/env python
# coding: utf-8

# In[8]:


n = int(input())
if n % 2 == 1:
    print(-1)
else:
    edges = [[] for i in range(n)]
    for i in range(n-1):
        [a,b] = [int(j) for j in input().split()]
        edges[a-1].append(b-1)
        edges[b-1].append(a-1)
    dfs_stack = [0]
    comp_size = [1 for i in range(n)]
    visited = [-1 for i in range(n)]
    visited[0] = 0
    
    while dfs_stack != []:
        current_node = dfs_stack[-1]
        can_go_further = False
        for i in edges[current_node]:
            if visited[i] == -1:
                dfs_stack.append(i)
                visited[i] = current_node
                can_go_further = True
        if can_go_further == False:
            dfs_stack.pop(-1)
            comp_size[visited[current_node]] += comp_size[current_node]
    
    ans = 0
    for i in comp_size[1:]:
        if i % 2 == 0:
            ans += 1
    print(ans)


# In[ ]: