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: MEDIUM
Tags: Graph algorithms

Graph traversal

Greedy algorithms

Tree algorithms

Dynamic programming
Skill types: Dynamic programming

Greedy algorithms

Starter code:

Solutions:
from collections import deque

def main():
	n = int(input())
	neis = [[] for i in range(n + 1)]
	vis = [0 for i in range(n + 1)]
	nodes = [1 for i in range(n + 1)]
	pre = [None for i in range(n + 1)]
	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()


from collections import Counter, OrderedDict
from itertools import permutations as perm
from fractions import Fraction
from collections import deque
from sys import stdin
from bisect import *
from heapq import *
g = lambda : stdin.readline().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
mod = int(1000000000.0) + 7
inf = float('inf')
(n,) = gil()
if n & 1:
	print(-1)
	exit()
adj = [[] for _ in range(n + 1)]
for _ in range(n - 1):
	(x, y) = gil()
	adj[x].append(y)
	adj[y].append(x)
vis = [0] * (n + 1)
ans = [0] * (n + 1)
stack = [1]
final = -1
while stack:
	p = stack[-1]
	if vis[p]:
		stack.pop()
		for c in adj[p]:
			ans[p] += ans[c]
		ans[p] += 1
		if ans[p] & 1 == 0:
			final += 1
	else:
		vis[p] = 1
		for c in adj[p]:
			if not vis[c]:
				stack.append(c)
print(final)


import sys, collections
input = sys.stdin.readline

def bfs(adj_list, n):
	c = [1] * n
	v = [-1] * n
	v[0] = 0
	q = [0]
	while q:
		x = q[-1]
		flag = False
		for to in adj_list[x]:
			if v[to] == -1:
				v[to] = x
				q.append(to)
				flag = True
		if not flag:
			q.pop()
			c[v[x]] += c[x]
	ans = 0
	for i in c[1:]:
		if i & 1 == 0:
			ans += 1
	print(ans)
n = int(input())
if n % 2 == 1:
	print(-1)
	exit()
adj_list = [[] for _ in range(n + 10)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	adj_list[a].append(b)
	adj_list[b].append(a)
bfs(adj_list, n)


n = int(input())
if n % 2 == 1:
	print(-1)
	exit()
adj = [[] for _ in range(n + 1)]
for _ in range(n - 1):
	(u, v) = 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)


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)


from sys import exit

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)
		exit()
	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()
		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 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)
main()


import sys
from collections import defaultdict
input = sys.stdin.readline
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

def get_adj_mat(src, dst, n):
	matrix = defaultdict(list)
	for (src_i, dst_i) in zip(src, dst):
		matrix[src_i].append(dst_i)
		matrix[dst_i].append(src_i)
	return matrix

@bootstrap
def get_num(src, adj_mat, seen):
	seen[src] = True
	(num_el, num_seg) = (1, 0)
	for dst in adj_mat[src]:
		if not seen[dst]:
			(num_el_i, num_seg_i) = (yield get_num(dst, adj_mat, seen))
			num_el += num_el_i
			num_seg += num_seg_i
	if num_el % 2 == 0:
		num_el = 0
		num_seg += 1
	yield (num_el, num_seg)

def solve(src, dst, n):
	adj_mat = get_adj_mat(src, dst, n)
	seen = [False] * n
	(num_el, num_seg) = get_num(0, adj_mat, seen)
	if num_el == 0:
		return num_seg - 1
	else:
		return -1
n = int(input())
(src, dst) = ([], [])
for _ in range(n - 1):
	(src_i, dst_i) = [int(val) for val in input().split()]
	(src.append(src_i - 1), dst.append(dst_i - 1))
print(solve(src, dst, n))


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)


import sys, os
from io import BytesIO, IOBase
from math import floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque
from heapq import merge, heapify, heappop, heappush, nsmallest
from bisect import bisect_left as bl, bisect_right as br, bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(stdin, stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
mod = pow(10, 9) + 7
mod2 = 998244353

def inp():
	return stdin.readline().strip()

def iinp():
	return int(inp())

def out(var, end='\n'):
	stdout.write(str(var) + '\n')

def outa(*var, end='\n'):
	stdout.write(' '.join(map(str, var)) + end)

def lmp():
	return list(mp())

def mp():
	return map(int, inp().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(m, val) for j in range(n)]

def ceil(a, b):
	return (a + b - 1) // b
S1 = 'abcdefghijklmnopqrstuvwxyz'
S2 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

def isprime(x):
	if x <= 1:
		return False
	if x in (2, 3):
		return True
	if x % 2 == 0:
		return False
	for i in range(3, int(sqrt(x)) + 1, 2):
		if x % i == 0:
			return False
	return True
n = iinp()
edges = l2d(n + 1, 0)
for i in range(n - 1):
	(x, y) = mp()
	edges[x].append(y)
	edges[y].append(x)
if n % 2:
	print(-1)
	exit()
ans = 0
depth = l1d(n + 1, -1)
par = l1d(n + 1)
stk = [(1, 0)]
depth[1] = 0
while stk:
	(node, lvl) = stk.pop()
	for child in edges[node]:
		if depth[child] == -1:
			par[child] = node
			depth[child] = lvl + 1
			stk.append((child, lvl + 1))
levels = [(depth[i], i) for i in range(2, n + 1)]
levels.sort()
dp = l1d(n + 1, 1)
for (_, node) in levels[::-1]:
	if dp[node] % 2 == 0:
		ans += 1
	else:
		dp[par[node]] += dp[node]
print(ans)


import os, sys, bisect, copy
from collections import defaultdict, Counter, deque
from functools import lru_cache
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 map(int if arg == 0 else str, input().split())
import sys
sys.setrecursionlimit(10 ** 5)
from types import GeneratorType

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):
	global 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)
if sz[1] & 1:
	print(-1)
else:
	print(res)


def dfs(g, s):
	visited = set([s])
	stack = [s]
	res = 0
	while len(stack) > 0:
		s = stack.pop()
		cnt = 0
		cnt += 1
		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():
	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(dfs2(tree, 1, n))

def __starting_point():
	solve()
__starting_point()


import sys
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 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)


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)
	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)


import sys
input = sys.stdin.readline
from collections import deque
n = int(input())
graph = [[] for _ in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	graph[a - 1].append(b - 1)
	graph[b - 1].append(a - 1)
parent = [-1] * n
size = [1] * n
q = deque([0])
stack = []
while q:
	node = q.popleft()
	stack.append(node)
	for i in graph[node]:
		if i == parent[node]:
			continue
		parent[i] = node
		q.append(i)
for i in range(n - 1, 0, -1):
	node = stack[i]
	size[parent[node]] += size[node]
if size[0] & 1:
	print(-1)
else:
	q = deque([0])
	ans = 0
	while q:
		node = q.popleft()
		for i in graph[node]:
			if i == parent[node]:
				continue
			if size[i] & 1 == 0:
				ans += 1
			q.append(i)
	print(ans)


import sys
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

class Graph:

	def __init__(self, V):
		self.V = V
		self.adj = [[] for i in range(V)]

	@bootstrap
	def DFSUtil(self, temp, v, visited, subtree):
		visited[v] = True
		temp.append(v)
		cnt = 1
		for i in self.adj[v]:
			if visited[i] == False:
				temp = (yield self.DFSUtil(temp, i, visited, subtree))
				cnt += subtree[i]
		subtree[v] = cnt
		yield temp

	def addEdge(self, v, w):
		self.adj[v].append(w)
		self.adj[w].append(v)
n = int(input())
G = Graph(n)
for i in range(n - 1):
	(u, v) = list(map(int, sys.stdin.readline().split()))
	G.addEdge(u - 1, v - 1)
if n % 2 == 1:
	print(-1)
else:
	visited = [False for _ in range(n)]
	subtree = [0 for _ in range(n)]
	G.DFSUtil([], 0, visited, subtree)
	total = 0
	for i in range(0, n):
		if subtree[i] % 2 == 0:
			total += 1
	print(total - 1)


from collections import deque

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]]:
				stack.append((cur, i))
				(cur, i) = go_to(cur, tos[cur][i])
			else:
				i += 1
				continue
		else:
			post(cur)
			if len(stack) == 0:
				break
			(cur, i) = stack.pop()
			i += 1
			continue
from sys import exit
n = int(input().strip())
tos = [[] for _ in range(n)]
for _ in range(n - 1):
	[u, v] = map(int, input().strip().split())
	tos[u - 1].append(v - 1)
	tos[v - 1].append(u - 1)
if n % 2 == 1:
	print(-1)
	exit(0)

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)))


n = int(input())
if n & 1 > 0:
	print(-1)
	exit()
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)


n = int(input())
if n % 2 == 1:
	print(-1)
	exit(0)
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)


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)


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left, bisect_right
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import collections as col

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())
MOD = 10 ** 9 + 7

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

def solve():
	N = getInt()
	graph = col.defaultdict(set)

	def vadd(u, v):
		graph[u].add(v)
		graph[v].add(u)
	for n in range(N - 1):
		(U, V) = getInts()
		vadd(U, V)
	if N % 2 == 1:
		return -1
	subtree = [0] * (N + 1)

	@bootstrap
	def numberOfNodes(s, e):
		subtree[s] = 1
		for u in graph[s]:
			if u == e:
				continue
			yield numberOfNodes(u, s)
			subtree[s] += subtree[u]
		yield
	numberOfNodes(1, 0)
	ans = 0
	for j in range(2, N + 1):
		if subtree[j] % 2 == 0:
			ans += 1
	return ans
print(solve())


import sys, os, io

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

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

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

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
import math, datetime, functools, itertools, operator, bisect, fractions, statistics
from collections import deque, defaultdict, OrderedDict, Counter
from fractions import Fraction
from decimal import Decimal
from sys import stdout
from heapq import heappush, heappop, heapify, _heapify_max, _heappop_max, nsmallest, nlargest
sys.setrecursionlimit(111111)
INF = 99999999999999999999999999999999

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))

def main():
	mod = 1000000007
	starttime = datetime.datetime.now()
	if os.path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	tc = 1
	for _ in range(tc):
		n = ri()
		graph = [[] for i in range(n + 1)]
		for i in range(n - 1):
			(a, b) = ria()
			graph[a].append(b)
			graph[b].append(a)
		if n % 2:
			wi(-1)
			exit()

		def dfs():
			start = 1
			dp = [0] * (n + 1)
			(visited, finished) = ([False] * (n + 1), [False] * (n + 1))
			stack = [start]
			while stack:
				start = stack[-1]
				if not visited[start]:
					visited[start] = True
					for child in graph[start]:
						if not visited[child]:
							stack.append(child)
				else:
					stack.pop()
					dp[start] += 1
					for child in graph[start]:
						if finished[child]:
							dp[start] += dp[child]
					finished[start] = True
			return dp
		size = dfs()
		count = 0
		for i in range(2, n + 1):
			if size[i] % 2 == 0:
				count += 1
		wi(count)
	endtime = datetime.datetime.now()
	time = (endtime - starttime).total_seconds() * 1000
	if os.path.exists('input.txt'):
		print('Time:', time, 'ms')

class FastReader(io.IOBase):
	newlines = 0

	def __init__(self, fd, chunk_size=1024 * 8):
		self._fd = fd
		self._chunk_size = chunk_size
		self.buffer = io.BytesIO()

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self, size=-1):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

class FastWriter(io.IOBase):

	def __init__(self, fd):
		self._fd = fd
		self.buffer = io.BytesIO()
		self.write = self.buffer.write

	def flush(self):
		os.write(self._fd, self.buffer.getvalue())
		(self.buffer.truncate(0), self.buffer.seek(0))

class FastStdin(io.IOBase):

	def __init__(self, fd=0):
		self.buffer = FastReader(fd)
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

class FastStdout(io.IOBase):

	def __init__(self, fd=1):
		self.buffer = FastWriter(fd)
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.flush = self.buffer.flush
sys.stdin = FastStdin()
sys.stdout = FastStdout()
main()


n = int(input())
tr = [[] for i in range(n)]
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	tr[u - 1].append(v - 1)
	tr[v - 1].append(u - 1)
if n % 2:
	print(-1)
	exit()
c = [1] * n
par = [-1] * n
par[0] = 0
q = [0]
while q:
	ver = q[-1]
	flag = False
	for to in tr[ver]:
		if par[to] == -1:
			par[to] = ver
			q.append(to)
			flag = True
	if not flag:
		q.pop()
		c[par[ver]] += c[ver]
ans = 0
for i in range(1, n):
	if c[i] % 2 == 0:
		ans += 1
print(ans)


def dfs(node):
	par[1] = 1
	stack = [1]
	ans = 0
	while stack:
		k = stack[-1]
		f = 0
		for i in g[k]:
			if par[i] == -1:
				par[i] = k
				stack.append(i)
				f = 1
		if f == 0:
			k = stack.pop()
			subtree[par[k]] += subtree[k]
	for i in subtree[2:]:
		if i % 2 == 0:
			ans = ans + 1
	print(ans)
n = int(input())
g = {}
for i in range(1, n + 1):
	g[i] = []
for i in range(1, n):
	(a, b) = map(int, input().split())
	g[a].append(b)
	g[b].append(a)
par = [-1 for i in range(n + 1)]
subtree = [1 for i in range(n + 1)]
if n % 2:
	print(-1)
else:
	dfs(1)


from sys import stdin
input = lambda : stdin.readline().strip()
from math import ceil, sqrt, factorial, gcd
from collections import deque
n = int(input())
d = {i: set() for i in range(1, n + 1)}
for i in range(n - 1):
	(a, b) = map(int, input().split())
	d[a].add(b)
	d[b].add(a)
stack = deque()
stack.append([1, 0])
ans = [[0, 0] for i in range(n + 1)]
l = []
while stack:
	x = stack.pop()
	try:
		l[x[1]].append(x[0])
	except:
		l.append([x[0]])
	for i in d[x[0]]:
		ans[i][0] = x[0]
		d[i].remove(x[0])
		stack.appendleft([i, x[1] + 1])
count = 0
if n % 2 != 0:
	print(-1)
	exit()
while l:
	stack = [i for i in l.pop()]
	while stack:
		x = stack.pop()
		if ans[x][1] > 0 and (ans[x][1] + 1) % 2 == 0:
			count += 1
		else:
			ans[ans[x][0]][1] += ans[x][1] + 1
print(count - 1)


from collections import deque
from array import array

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

	def fake_dfs(start_point):
		nonlocal neis
		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)
main()


from collections import defaultdict
import threading
from sys import stdin, setrecursionlimit
setrecursionlimit(300000)
input = stdin.readline

def dfs(node, g, par, sz):
	for i in g[node]:
		if i != par:
			sz[node] += dfs(i, g, node, sz)
	return sz[node] + 1

def main():
	n = int(input())
	if n % 2 != 0:
		print(-1)
		exit(0)
	g = defaultdict(list)
	for i in range(n - 1):
		(x, y) = map(int, input().strip().split())
		g[x - 1].append(y - 1)
		g[y - 1].append(x - 1)
	sz = [0] * n
	tt = []
	dfs(0, g, -1, sz)
	res = 0
	for i in range(1, n):
		if sz[i] % 2 != 0:
			res += 1
	print(res)
threading.stack_size(10 ** 8)
t = threading.Thread(target=main)
t.start()
t.join()


n = int(input())
if n & 1 > 0:
	print(-1)
	exit()
g = [[] for i in range(n)]
for i in range(n - 1):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	g[u].append(v)
	g[v].append(u)
c = [1] * n
v = [-1] * n
v[0] = 0
q = [0]
while q:
	x = q[-1]
	flag = False
	for to in g[x]:
		if v[to] == -1:
			v[to] = x
			q.append(to)
			flag = True
	if not flag:
		q.pop()
		c[v[x]] += c[x]
ans = 0
for j in c[1:]:
	if j & 1 < 1:
		ans += 1
print(ans)


import sys, threading
sys.setrecursionlimit(10 ** 6)
threading.stack_size(10 ** 8)

def dfs(x):
	global v, l, adj
	v[x] = 1
	l[x] = 1
	for i in adj[x]:
		if not v[i]:
			l[x] += dfs(i)
	return l[x]

def dfs1(x):
	global v, l, adj, ans
	v[x] = 1
	for i in adj[x]:
		if not v[i]:
			if l[i] % 2 == 0:
				ans += 1
			dfs1(i)

def main():
	global v, l, adj, ans
	n = int(input())
	l = [0] * (n + 1)
	v = [0] * (n + 1)
	adj = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(x, y) = map(int, input().split())
		adj[x].append(y)
		adj[y].append(x)
	dfs(1)
	ans = 0
	v = [0] * (n + 1)
	dfs1(1)
	if n % 2:
		print(-1)
	else:
		print(ans)
t = threading.Thread(target=main)
t.start()
t.join()


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]:
			cutFlag[vert] = cutFlag[v1] == cutFlag[vert]
		if cutFlag[vert]:
			result += 1
	return result
if n % 2 == 1:
	print(-1)
else:
	print(solve1(n, u, v))


n = int(input())
d = {i: [] for i in range(1, n + 1)}
for i in range(n - 1):
	(a, b) = map(int, input().split())
	d[a].append(b)
	d[b].append(a)
if n & 1:
	print(-1)
else:
	val = [1 for i in range(n + 1)]
	par = [-1 for i in range(n + 1)]
	par[1] = 1
	stack = [1]
	while stack:
		u = stack[-1]
		f = 0
		for i in d[u]:
			if par[i] == -1:
				par[i] = u
				stack.append(i)
				f = 1
		if f == 0:
			stack.pop()
			val[par[u]] += val[u]
	ans = 0
	for i in range(2, n + 1):
		if val[i] % 2 == 0:
			ans += 1
	print(ans)


n = int(input())
graph = [[] for i in range(n + 1)]
for i in range(n - 1):
	(u, v) = list(map(int, input().split()))
	graph[u].append(v)
	graph[v].append(u)
if n % 2 != 0:
	print(-1)
	exit()
subtree_size = [1 for i in range(n + 1)]
par = [-1 for i in range(n + 1)]
par[1] = 1
st = [1]
while st != []:
	u = st[-1]
	f = 0
	for v in graph[u]:
		if par[v] == -1:
			par[v] = u
			st.append(v)
			f = 1
	if f == 0:
		st.pop()
		subtree_size[par[u]] += subtree_size[u]
res = 0
for i in range(2, len(subtree_size)):
	if subtree_size[i] % 2 == 0:
		res += 1
print(res)


from collections import defaultdict
for _ in range(1):
	n = int(input())
	tree = defaultdict(list)
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		tree[u].append(v)
		tree[v].append(u)
	if len(tree) % 2 or n == 1:
		print(-1)
		exit(0)
	subtree_count = [1 for i in range(n + 1)]
	visited = [-1 for i in range(n + 1)]
	stack = [1]
	while stack:
		cn = stack[-1]
		found = 0
		for nn in tree[cn]:
			if visited[nn] == -1:
				found = 1
				visited[nn] = cn
				stack.append(nn)
		if not found:
			stack.pop()
			subtree_count[visited[cn]] += subtree_count[cn]
	edges = 0
	for count_ in subtree_count[2:]:
		if count_ % 2 == 0:
			edges += 1
	print(edges)