Mahmoud and Ehab continue their adventures! As everybody in the evil land knows, Dr. Evil likes bipartite graphs, especially trees.

A tree is a connected acyclic graph. A bipartite graph is a graph, whose vertices can be partitioned into 2 sets in such a way, that for each edge (u, v) that belongs to the graph, u and v belong to different sets. You can find more formal definitions of a tree and a bipartite graph in the notes section below.

Dr. Evil gave Mahmoud and Ehab a tree consisting of n nodes and asked them to add edges to it in such a way, that the graph is still bipartite. Besides, after adding these edges the graph should be simple (doesn't contain loops or multiple edges). What is the maximum number of edges they can add?

A loop is an edge, which connects a node with itself. Graph doesn't contain multiple edges when for each pair of nodes there is no more than one edge between them. A cycle and a loop aren't the same .


-----Input-----

The first line of input contains an integer n — the number of nodes in the tree (1 ≤ n ≤ 10^5).

The next n - 1 lines contain integers u and v (1 ≤ u, v ≤ n, u ≠ v) — the description of the edges of the tree.

It's guaranteed that the given graph is a tree. 


-----Output-----

Output one integer — the maximum number of edges that Mahmoud and Ehab can add to the tree while fulfilling the conditions.


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

Output
0

Input
5
1 2
2 3
3 4
4 5

Output
2



-----Note-----

Tree definition: https://en.wikipedia.org/wiki/Tree_(graph_theory)

Bipartite graph definition: https://en.wikipedia.org/wiki/Bipartite_graph

In the first test case the only edge that can be added in such a way, that graph won't contain loops or multiple edges is (2, 3), but adding this edge will make the graph non-bipartite so the answer is 0.

In the second test case Mahmoud and Ehab can add edges (1, 4) and (2, 5).

Source: codeforces | Difficulty: EASY
Tags: Tree algorithms

Graph algorithms

Graph traversal


Solutions:
n = int(input())
e = {}
for i in range(n - 1):
	(a, b) = map(int, input().split(' '))
	x = e.get(a, [])
	x.append(b)
	e[a] = x
	x = e.get(b, [])
	x.append(a)
	e[b] = x
x = 1
y = 0
temp1 = [1]
temp2 = []
seen = set()
k = 0
while len(temp1) > 0:
	for i in temp1:
		seen.add(i)
		for j in e[i]:
			if j not in seen:
				temp2.append(j)
				if k % 2 == 0:
					y += 1
				else:
					x += 1
	temp1 = temp2
	temp2 = []
	k += 1
print(x * y - n + 1)


class Item:
	count = [0, 0]

	def __init__(self):
		self.next = set()
		self.parity = -1

	def add(self, it):
		self.next.add(it)
		it.next.add(self)

	def hang(self):
		self.parity = 0
		queue = [self]
		while queue:
			cur = queue.pop()
			Item.count[cur.parity] += 1
			for it in cur.next:
				if it.parity < 0:
					it.parity = 1 - cur.parity
					queue.append(it)
n = int(input())
arr = [Item() for _ in range(n)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	arr[a - 1].add(arr[b - 1])
arr[0].hang()
print(Item.count[0] * Item.count[1] - n + 1)


import sys
nodes = int(input())
adjacency_list = {node: set() for node in range(1, nodes + 1)}
for _ in range(nodes - 1):
	(a, b) = [int(x) for x in input().split()]
	adjacency_list[a].add(b)
	adjacency_list[b].add(a)
sets = [set(), set()]
start_node = 1
start_level = 0
stack = [(start_node, start_level)]
visited = [False] * (nodes + 1)
while stack:
	(node, level) = stack.pop(-1)
	visited[node] = True
	sets[level % 2].add(node)
	for neighbor in adjacency_list[node]:
		if not visited[neighbor]:
			stack.append((neighbor, level + 1))
max_edges = len(sets[0]) * len(sets[1])
print(max_edges - (nodes - 1))


import collections
n = int(input())

def bfs(stack1):
	while True:
		stack2 = list()
		while stack1:
			vertex = stack1.pop()
			if not visited1[vertex]:
				visited1[vertex] = 1
				for v in inp[vertex]:
					if not visited2[v]:
						stack2.append(v)
		if not stack2:
			return
		stack1 = list()
		while stack2:
			vertex = stack2.pop()
			if not visited2[vertex]:
				visited2[vertex] = 1
				for v in inp[vertex]:
					if not visited1[v]:
						stack1.append(v)
		if not stack1:
			return
inp = collections.defaultdict(list)
for _ in range(n - 1):
	(v1, v2) = list(map(int, input().split()))
	inp[v1].append(v2)
	inp[v2].append(v1)
(visited1, visited2) = ([0] + [0] * n, [0] + [0] * n)
bfs([1])
print(sum(visited1) * sum(visited2) - (n - 1))


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

def bfs():
	q = deque([0])
	dist = [-1] * n
	dist[0] = 0
	while q:
		v = q.popleft()
		for nv in G[v]:
			if dist[nv] == -1:
				dist[nv] = dist[v] + 1
				q.append(nv)
	return dist
n = int(input())
G = [[] for _ in range(n)]
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	G[u - 1].append(v - 1)
	G[v - 1].append(u - 1)
dist = bfs()
(b, w) = (0, 0)
for i in range(n):
	if dist[i] % 2 == 0:
		b += 1
	else:
		w += 1
print(b * w - (n - 1))


from collections import Counter, defaultdict, deque
n = int(input())

def BFS(cmap, v):
	visited = [False] * len(cmap)
	q = deque([v])
	level = 0
	blue = 0
	red = 0
	while len(q) != 0:
		for i in range(len(q)):
			vertex = q.popleft()
			if not visited[vertex]:
				if level % 2 == 0:
					blue += 1
				else:
					red += 1
				visited[vertex] = True
				q.extend(cmap[vertex])
		level += 1
	return (blue, red)
connections = [[] for x in range(n)]
for i in range(n - 1):
	(a, b) = [int(x) - 1 for x in input().split()]
	connections[a].append(b)
	connections[b].append(a)
(b, r) = BFS(connections, 0)
print(b * r - n + 1)


def is_bipartite(graph):
	n = len(graph)
	color = [-1] * n
	for start in range(n):
		if color[start] == -1:
			color[start] = 0
			stack = [start]
			while stack:
				parent = stack.pop()
				for child in graph[parent]:
					if color[child] == -1:
						color[child] = 1 - color[parent]
						stack.append(child)
					elif color[parent] == color[child]:
						return (False, color)
	return (True, color)
N = int(input())
g = [[] for _ in range(N)]
for i in range(N - 1):
	(u, v) = map(int, input().split())
	g[u - 1].append(v - 1)
	g[v - 1].append(u - 1)
colors = is_bipartite(g)[1]
left = colors.count(0)
right = N - left
print(left * right - N + 1)


from sys import stdin, stdout
import queue
AdjList = []
distance = []
q = queue.Queue(0)

def bfs(u):
	q.put(u)
	distance[u] = 0
	while q.empty() == False:
		u = q.get()
		for j in AdjList[u]:
			if distance[j] == -1:
				q.put(j)
				distance[j] = distance[u] + 1
n = int(input())
for _ in range(n):
	AdjList.append([])
	distance.append(-1)
for _ in range(n - 1):
	(u, v) = [int(x) for x in stdin.readline().split()]
	AdjList[u - 1].append(v - 1)
	AdjList[v - 1].append(u - 1)
bfs(0)
parni = neparni = 0
for i in range(len(distance)):
	if distance[i] % 2 == 0:
		parni += 1
	else:
		neparni += 1
ans = parni * neparni - n + 1
print(ans)


def readln():
	return list(map(int, input().rstrip().split()))
data = {}
n = int(input())
for i in range(1, n + 1):
	data[i] = []
for i in range(0, n - 1):
	(u, v) = readln()
	data[u].append(v)
	data[v].append(u)
l = [0, 0]
visited = [False] * (n + 1)
stk = [(1, 0)]
while stk:
	u = stk.pop()
	visited[u[0]] = True
	l[u[1]] += 1
	for i in data[u[0]]:
		if not visited[i]:
			stk.append((i, 1 - u[1]))
print(l[0] * l[1] - (n - 1))


from collections import deque
n = int(input())
g = [[] for i in range(n + 1)]
for i in range(n - 1):
	(u, v) = map(int, input().split())
	g[u].append(v)
	g[v].append(u)
f = [0] * (n + 1)
c = [1, 0]
q = deque()
q.appendleft((1, 0))
while q:
	(u, p) = q.pop()
	for v in g[u]:
		if v != p:
			f[v] = (f[u] + 1) % 2
			c[f[v]] += 1
			q.appendleft((v, u))
ans = 0
for u in range(1, n + 1):
	n = len(g[u])
	opp = c[1 - f[u]]
	ans += opp - n
print(ans // 2)


n = int(input())
graph = [None] * (n + 1)
for i in range(1, n + 1):
	graph[i] = []
for i in range(n - 1):
	(u, v) = map(int, input().split())
	graph[u].append(v)
	graph[v].append(u)
is_u = [None] * (n + 1)
is_u[1] = True
stack = [1]
while stack:
	top = stack.pop()
	vals = graph[top]
	for i in range(len(vals)):
		cur = vals[i]
		if is_u[cur] == None:
			is_u[cur] = not is_u[top]
			stack.append(cur)
count_u = is_u.count(True)
print(count_u * (n - count_u) - (n - 1))


import sys
from sys import stdin, stdout
import bisect
import math
mod = 10 ** 9 + 7

def st():
	return list(stdin.readline().strip())

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

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

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

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

def DFS(dictionary, vertex, visited):
	visited[vertex] = True
	stack = [vertex]
	print(vertex)
	while stack:
		a = stack.pop()
		for i in dictionary[a]:
			if not visited[i]:
				print(i)
				visited[i] = True
				stack.append(i)

def soe(limit):
	l = [1] * (limit + 1)
	l[0] = 0
	l[1] = 0
	prime = []
	for i in range(2, limit + 1):
		if l[i]:
			for j in range(i * i, limit + 1, i):
				l[j] = 0
	for i in range(2, limit + 1):
		if l[i]:
			prime.append(i)
	return prime

def segsoe(low, high):
	limit = int(high ** 0.5) + 1
	prime = soe(limit)
	n = high - low + 1
	l = [0] * (n + 1)
	for i in range(len(prime)):
		lowlimit = low // prime[i] * prime[i]
		if lowlimit < low:
			lowlimit += prime[i]
		if lowlimit == prime[i]:
			lowlimit += prime[i]
		for j in range(lowlimit, high + 1, prime[i]):
			l[j - low] = 1
	for i in range(low, high + 1):
		if not l[i - low]:
			if i != 1:
				print(i)

def gcd(a, b):
	while b:
		a = a % b
		(b, a) = (a, b)
	return a

def power(a, n):
	r = 1
	while n:
		if n & 1:
			r = r * a
		a *= a
		n = n >> 1
	return r

def DFS(d, visited, ver, color, value):
	value[ver] = color
	visited[ver] = True
	stack = [ver]
	while stack:
		a = stack.pop()
		for i in d[a]:
			if not visited[i]:
				visited[i] = True
				stack.append(i)
				value[i] = value[a] ^ 1
			elif value[i] == value[a]:
				return False
	return True

def solve():
	n = inp()
	visited = [False for i in range(n + 1)]
	d = {i: [] for i in range(1, n + 1)}
	for i in range(n - 1):
		(a, b) = mp()
		d[a].append(b)
		d[b].append(a)
	ans = 0
	value = [-1] * (n + 1)
	for i in range(1, n + 1):
		if not visited[i]:
			if not DFS(d, visited, i, 0, value):
				pr(0)
				return
	a = value.count(1)
	pr(a * (n - a) - (n - 1))
for _ in range(1):
	solve()


import queue

def read_int():
	return read_tuple()[0]

def read_tuple():
	return tuple(map(lambda x: int(x), input().strip().split()))

def read_graph():
	n = read_int()
	edges = [[] for _ in range(n + 1)]
	for _ in range(n - 1):
		(u, v) = read_tuple()
		edges[u].append(v)
		edges[v].append(u)
	return (n, edges)

def bfs(n, edges):
	dist = [None] * (n + 1)
	q = queue.Queue()
	q.put(1)
	dist[1] = 0
	while not q.empty():
		u = q.get()
		for w in edges[u]:
			if dist[w] == None:
				dist[w] = dist[u] ^ 1
				q.put(w)
	return dist[1:]
(n, edges) = read_graph()
res = bfs(n, edges)
p1 = sum((x == 0 for x in res))
p2 = n - p1
print(p1 * p2 - (n - 1))


from collections import defaultdict, Counter

class Graph:

	def __init__(self, n):
		self.vertices = n
		self.graph = defaultdict(list)

	def addEdge(self, fr, to):
		self.graph[fr].append(to)
		self.graph[to].append(fr)

	def bipartite(self):
		color = [-1] * self.vertices
		visited = [False] * self.vertices
		queue = [1]
		k = 0
		color[0] = k
		visited[0] = True
		while queue:
			k = 1 - k
			small = queue.copy()
			while small:
				s = small.pop(0)
				queue.pop(0)
				visited[s - 1] = True
				for i in self.graph[s]:
					if visited[i - 1] == False:
						queue.append(i)
						color[i - 1] = k
		Dict = Counter(color)
		one = Dict[1]
		zero = Dict[0]
		return one * zero - (self.vertices - 1)
n = int(input())
G = Graph(n)
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	G.addEdge(a, b)
print(G.bipartite())


n = int(input())
a = [[] for i in range(n)]
for i in range(n - 1):
	(f, s) = map(int, input().split())
	a[s - 1].append(f)
	a[f - 1].append(s)
q = [1]
fl = [1] + [0] * n
while len(q) != 0:
	x = q.pop()
	for i in a[x - 1]:
		if fl[i - 1] == 0:
			q.append(i)
			fl[i - 1] = -fl[x - 1]
print(fl.count(1) * (n - fl.count(1)) - n + 1)


n = int(input())
p = [[] for i in range(n + 1)]
for j in range(n - 1):
	(u, v) = map(int, input().split())
	p[u].append(v)
	p[v].append(u)
s = [(1, 1)]
t = [0, 0]
while s:
	(u, k) = s.pop()
	t[k] += 1
	s += [(v, 1 - k) for v in p[u] if p[v]]
	p[u] = []
print(t[0] * t[1] - n + 1)


import os
import sys
from io import BytesIO, IOBase
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')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
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 RL():
	return map(int, sys.stdin.readline().rstrip().split())

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

def N():
	return int(input())

def comb(n, m):
	return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
	return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)
mod = 998244353
INF = float('inf')
from math import factorial
from collections import Counter, defaultdict, deque
from heapq import heapify, heappop, heappush

def main():
	n = N()
	gp = [[] for _ in range(n + 1)]
	for _ in range(n - 1):
		(f, t) = RL()
		gp[f].append(t)
		gp[t].append(f)
	one = 0

	@bootstrap
	def dfs(node=1, par=-1, c=1):
		nonlocal one
		if c:
			one += 1
		for nex in gp[node]:
			if nex == par:
				continue
			yield dfs(nex, node, c ^ 1)
		yield None
	dfs()
	print(one * (n - one) - (n - 1))
main()


from _collections import defaultdict
n = int(input())
f = 0
s = 0
gen = defaultdict(list)
for i in range(n - 1):
	(a, b) = map(lambda x: int(x), input().split())
	gen[a].append(b)
	gen[b].append(a)
start = [1]
visited = set()
Turn = True
while start:
	q = []
	for i in start:
		visited.add(i)
		for j in gen[i]:
			if j not in visited:
				q.append(j)
	if Turn:
		f += len(start)
	else:
		s += len(start)
	Turn = not Turn
	start = q
print(f * s - (n - 1))


N = int(input())
adj = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b) = list(map(int, input().split()))
	a -= 1
	b -= 1
	adj[a].append(b)
	adj[b].append(a)
visited = {0}
cur_level = [0]
levels = []
while cur_level:
	levels.append(cur_level)
	next_level = []
	for n in cur_level:
		for m in adj[n]:
			if m not in visited:
				next_level.append(m)
				visited.add(m)
	cur_level = next_level
color_0 = sum(map(len, levels[0::2]))
color_1 = sum(map(len, levels[1::2]))
out = 0
for (i, level) in enumerate(levels):
	for n in level:
		if i % 2 == 0:
			out += color_1 - len(adj[n])
		else:
			out += color_0 - len(adj[n])
assert out % 2 == 0
print(out // 2)


n = int(input())
g = {i: set() for i in range(1, n + 1)}
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	g[u].add(v)
	g[v].add(u)
c = [-1] * (n + 1)
c[1] = 0
v = [False] * (n + 1)
s = [1]
while s:
	x = s.pop(0)
	if v[x]:
		continue
	v[x] = True
	for y in g[x]:
		if c[y] == -1:
			c[y] = 1 - c[x]
			s.append(y)
print(c.count(0) * c.count(1) - n + 1)


from collections import defaultdict
n = int(input())
g = defaultdict(list)
for i in range(n - 1):
	(u, v) = map(int, input().split())
	g[u].append(v)
	g[v].append(u)
colored = [None] * (n + 1)
colored[1] = 1
temp = [1]
while temp:
	top = temp.pop()
	for x in g[top]:
		if colored[x] == None:
			colored[x] = 1 - colored[top]
			temp.append(x)
r = colored.count(1)
ans = r * (n - r) - n + 1
print(ans)


n = int(input())
dist = {}
for i in range(n - 1):
	(u, v) = [int(e) for e in input().split()]
	if u not in dist:
		dist[u] = []
	if v not in dist:
		dist[v] = []
	dist[u].append(v)
	dist[v].append(u)
	if i == 0:
		root = u
a = {}
a[root] = 1
q = [root]
while q:
	top = q.pop()
	for e in dist[top]:
		if e not in a:
			a[e] = -a[top]
			q.append(e)
s1 = [k for (k, v) in list(a.items()) if v == 1]
s2 = [k for (k, v) in list(a.items()) if v == -1]
print(len(s1) * len(s2) - n + 1)


def dfs(node, c):
	visited[node] = True
	stack = [node]
	while stack:
		node = stack.pop()
		for child in g[node]:
			if visited[child] == False:
				color[child] = color[node] ^ 1
				stack.append(child)
				visited[child] = True
	return color
n = int(input())
g = {i: [] for i in range(1, n + 1)}
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	g[u].append(v)
	g[v].append(u)
color = [0 for i in range(n + 1)]
visited = [False for i in range(n + 1)]
for i in range(1, n + 1):
	if visited[i] == False:
		color = dfs(i, color[i])
c1 = 0
c2 = 0
for i in range(1, n + 1):
	if color[i] == 0:
		c1 += 1
	else:
		c2 += 1
print(c1 * c2 - (n - 1))


import sys
import copy
input = sys.stdin.readline
from collections import deque
from math import *

def bfs(a, col, vis):
	vis[1] = 1
	r = deque()
	r.append(1)
	while len(r) > 0:
		z = r[0]
		r.popleft()
		for i in a[z]:
			if vis[i] == 0:
				vis[i] = 1
				col[i] = col[z] ^ 1
				r.append(i)
n = int(input())
a = [[] for i in range(n + 1)]
for i in range(n - 1):
	(x, y) = map(int, input().split())
	a[x].append(y)
	a[y].append(x)
col = [0 for i in range(n + 1)]
vis = [0 for i in range(n + 1)]
bfs(a, col, vis)
z = col[1:].count(0)
o = col[1:].count(1)
print(z * o - n + 1)


n = int(input())
store = [[] for _ in range(n + 1)]
mark = [0 for _ in range(n + 1)]
markX = [0 for _ in range(n + 1)]
sumA = 0
part = 0
left = [1]
(l, r) = (0, 0)
for i in range(n - 1):
	(u, v) = map(int, input().split())
	store[v].append(u)
	store[u].append(v)
temp = []
if n != 1:
	l += 1
	mark[1] = len(store[1])
	for ii in store[1]:
		temp.append(ii)
		markX[ii] = 1
	while len(temp) > 0:
		next = []
		part ^= 1
		if part:
			for item in temp:
				if not mark[item]:
					r += 1
					for ii in store[item]:
						if markX[ii] == 0:
							markX[ii] = 1
							next.append(ii)
					mark[item] = 1
		else:
			for item in temp:
				if not mark[item]:
					for ii in store[item]:
						if markX[ii] == 0:
							markX[ii] = 1
							next.append(ii)
					left.append(item)
					mark[item] = len(store[item])
		temp = next[:]
for v in left:
	sumA += r - mark[v]
print(sumA)


from collections import defaultdict
n = int(input())
degree = [0 for i in range(n + 1)]

def BFS(d, x, visited):
	visited[x] = 1
	queue = [(x, 1)]
	l1 = set()
	l2 = set()
	while len(queue):
		(temp, j) = queue.pop()
		visited[temp] = 1
		if j % 2 == 1:
			l1.add(temp)
		else:
			l2.add(temp)
		for i in d[temp]:
			if visited[i] == 0:
				queue.append((i, j + 1))
	return (l1, l2)
d = defaultdict(list)
for i in range(n - 1):
	(u, v) = map(int, input().split())
	d[u].append(v)
	d[v].append(u)
	degree[u] = degree[u] + 1
	degree[v] = degree[v] + 1
visited = [0 for i in range(n + 1)]
(l1, l2) = BFS(d, 1, visited)
s = 0
for i in range(1, n + 1):
	if i in l1:
		s = s + len(l2) - degree[i]
	elif i in l2:
		s = s + len(l1) - degree[i]
print(s // 2)


n = int(input())
color = [-1] * n
adj = [[] for i in range(n)]
vis = [0] * n
for i in range(n - 1):
	(x, y) = map(int, input().split(' '))
	adj[x - 1] += [y - 1]
	adj[y - 1] += [x - 1]
c = [0]
color[0] = 0
vis[0] = 1
while c:
	q = c.pop()
	for t in adj[q]:
		if vis[t] == 0:
			if color[t] == -1:
				if color[q] == 0:
					color[t] = 1
				else:
					color[t] = 0
			vis[t] = 1
			c += [t]
rr = sum(color)
ll = n - rr
print(ll * rr - n + 1)


n = int(input())
f = lambda u, v: u.append(v)
l = [0] * n
d = [[] for _ in range(n)]
l[0] = 1
c = [1]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	f(d[a - 1], b)
	f(d[b - 1], a)
while c:
	x = c.pop()
	for y in d[x - 1]:
		if not l[y - 1]:
			f(c, y)
			l[y - 1] = -1 * l[x - 1]
r = l.count(1)
print(r * (n - r) - n + 1)


def main():
	n = int(input())
	uv = [[] for _ in range(n + 1)]
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		uv[u].append(v)
		uv[v].append(u)
	(avail, u) = ([True] * (n + 1), n // 2 + 1)
	(avail[u], nxt, a, b) = (False, [u], -1, -1)
	while nxt:
		(cur, nxt, a, b) = (nxt, [], b, a)
		for u in cur:
			a += 1
			for v in uv[u]:
				if avail[v]:
					avail[v] = False
					nxt.append(v)
	print(a * b)
main()


n = int(input())
g = [[] for i in range(n)]
for i in range(n - 1):
	(u, v) = map(int, input().split())
	g[u - 1].append(v - 1)
	g[v - 1].append(u - 1)
q = [[0, 0]]
lvls = [0 for i in range(n)]
lvls[0] = 1
vis = set([0])
while len(q) > 0:
	v = q[0][0]
	l = q[0][1]
	del q[0]
	for u in g[v]:
		if u not in vis:
			vis.add(u)
			q.append([u, l + 1])
			lvls[l + 1] += 1
clvls = [i for i in lvls]
for i in range(2, n):
	if lvls[i] == 0:
		break
	clvls[i] += clvls[i - 2]
ans = 0
for i in range(2, n):
	if lvls[i] == 0:
		break
	ans += lvls[i] * (clvls[i - 1] - 1)
print(ans)


from collections import defaultdict
n = int(input())
a = defaultdict(list)
for i in range(n - 1):
	(x, y) = map(int, input().split())
	a[x].append(y)
	a[y].append(x)
colors = [None] * (n + 1)
colors[1] = 1
queue = [1]
while queue:
	top = queue.pop()
	for x in a[top]:
		if colors[x] is None:
			colors[x] = 1 - colors[top]
			queue.append(x)
k = colors.count(1)
res = k * (n - k) - (n - 1)
print(res)


n = int(input())
mass = [[] for _ in range(n + 1)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	mass[a].append(b)
	mass[b].append(a)
num_class = {1: 0, 0: 0}
npc = [(1, 0, 0)]
while npc:
	(node, p_node, color) = npc.pop()
	num_class[color] += 1
	for neig in mass[node]:
		if neig != p_node:
			npc.append(tuple((neig, node, 1 - color)))
print(num_class[0] * num_class[1] - n + 1)


from collections import deque
import sys
input = sys.stdin.readline
n = int(input())
adj_list = [[] for _ in range(n)]
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)
visited = [-1] * n
ans = 0
a = []
q = deque([0])
k = 0
c = 1
visited[0] = 1
while q:
	node = q.popleft()
	for neighbour in adj_list[node]:
		if visited[neighbour] == -1:
			q.append(neighbour)
			visited[neighbour] = visited[node] ^ 1
col1 = visited.count(1)
print(col1 * (n - col1) - (n - 1))


from collections import deque

def readints():
	return [int(item) for item in input().strip().split()]

class Graph:
	NOT_INITIALIZED = -1

	def __init__(self, size):
		self.g = [[] for _ in range(size)]
		self.nodes = [Graph.NOT_INITIALIZED] * size
		self.counts = [0, 0]

	def add_edge(self, u, v):
		self.g[u].append(v)

	def bipartite(self):
		q = deque([1])
		self.nodes[1] = 0
		self.counts[0] = 1
		while len(q) > 0:
			v = q.popleft()
			for u in self.g[v]:
				if self.nodes[u] != Graph.NOT_INITIALIZED:
					continue
				val = 1 - self.nodes[v]
				self.nodes[u] = val
				self.counts[val] += 1
				q.append(u)

	def max_edges(self):
		self.bipartite()
		ans = 0
		for i in range(1, len(self.g)):
			others = 1 - self.nodes[i]
			ans += self.counts[others] - len(self.g[i])
		return ans // 2

class Solver:

	def main(self):
		n = readints()[0]
		g = Graph(n + 1)
		for i in range(n - 1):
			(u, v) = readints()
			g.add_edge(u, v)
			g.add_edge(v, u)
		print(g.max_edges())
Solver().main()


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

def main():
	global al, va, ca, n0, n1
	n = int(input())
	al = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		al[a].append(b)
		al[b].append(a)
	c = 0
	va = [0] * (n + 1)
	ca = [-1] * (n + 1)
	n0 = 0
	n1 = 0
	for e in range(1, n + 1):
		if va[e] == 0:
			dfs(e, 0)
	print(n0 * n1 - (n - 1))

def dfs(n, col):
	global n0, n1, al, va, ca
	va[n] = 1
	ca[n] = col
	if col == 0:
		n0 = n0 + 1
	else:
		n1 = n1 + 1
	for e in al[n]:
		if va[e] == 0:
			dfs(e, ca[n] ^ 1)
t = threading.Thread(target=main)
t.start()
t.join()


n = int(input())
a = []
for i in range(n - 1):
	a.append(list(map(int, input().split(' '))))
Table = [[] for i in range(n + 1)]
for i in range(len(a)):
	Table[a[i][0]].append(a[i][1])
	Table[a[i][1]].append(a[i][0])
c = [2 for i in range(n + 1)]
c[1] = 1
queue = []
queue.append(1)
pointer = -1
while pointer + 1 < len(queue):
	pointer += 1
	x = queue[pointer]
	for i in range(len(Table[x])):
		if c[Table[x][i]] == 2:
			queue.append(Table[x][i])
			c[Table[x][i]] = 1 - c[x]
l = 0
r = 0
for i in range(1, len(c)):
	if c[i] == 1:
		l += 1
	else:
		r += 1
Max = l * r
print(Max - (n - 1))


from collections import deque

def bfs(graph):
	seen = [False] * 100001
	blue_count = 0
	red_count = 0
	frontier = deque()
	frontier.append((1, True))
	while len(frontier) != 0:
		(node, red) = frontier.popleft()
		blue_count += 1 if not red else 0
		red_count += 1 if red else 0
		seen[node] = True
		for nbor in graph[node]:
			if not seen[nbor]:
				frontier.append((nbor, False if red else True))
	return (blue_count, red_count)

def bipartite(graph):
	return bfs(graph)
nodes = int(input())
graph = {i + 1: [] for i in range(0, nodes)}
for i in range(0, nodes - 1):
	(src, dest) = input().split(' ')
	graph[int(src)].append(int(dest))
	graph[int(dest)].append(int(src))
(blue, red) = bipartite(graph)
print(blue * red - nodes + 1)


n = int(input())
adj = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	adj[a - 1].append(b - 1)
	adj[b - 1].append(a - 1)
visited = [0] * n
value = [-1] * n
q = [0]
value[0] = 0
while q:
	x = q.pop(0)
	for u in adj[x]:
		if visited[u] == 0:
			visited[u] = 1
			q.append(u)
			value[u] = 1 - value[x]
l = value.count(0)
r = value.count(1)
print(l * r - (n - 1))


def input_numbers():
	return list(map(int, input().split()))
n = int(input())
g = {}
i = 1
while i <= n:
	g[i] = set()
	i += 1
i = 1
while i <= n - 1:
	(u, v) = input_numbers()
	g[u].add(v)
	g[v].add(u)
	i += 1
queue = [1]
visited = set()
part1 = set(queue)
part2 = set()
while len(queue):
	u = queue.pop(0)
	visited.add(u)
	for v in g[u]:
		if v not in visited:
			queue.append(v)
			if u in part1:
				part2.add(v)
			else:
				part1.add(v)
need = len(part1) * len(part2) - (n - 1)
print(need)


from sys import stdout, stdin, setrecursionlimit
from io import BytesIO, IOBase
from collections import *
from itertools import *
from bisect import *
from string import *
from queue import *
from heapq import *
from math import *
from re import *
from os import *

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 = read(self._fd, max(fstat(self._fd).st_size, 8192))
			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 = read(self._fd, max(fstat(self._fd).st_size, 8192))
			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:
			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(stdin), IOWrapper(stdout))
(graph, mod, szzz) = ({}, 10 ** 9 + 7, lambda : sorted(zzz()))

def getStr():
	return input()

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

def listStr():
	return list(input())

def getStrs():
	return input().split()

def isInt(s):
	return '0' <= s[0] <= '9'

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

def zzz():
	return [int(i) for i in input().split()]

def output(answer, end='\n'):
	stdout.write(str(answer) + end)

def lcd(xnum1, xnum2):
	return xnum1 * xnum2 // gcd(xnum1, xnum2)
dx = [-1, 1, 0, 0, 1, -1, 1, -1]
dy = [0, 0, 1, -1, 1, -1, -1, 1]
daysInMounth = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
n = getInt()
for i in range(n):
	graph[i + 1] = []
for i in range(n - 1):
	(x, y) = zzz()
	graph[x].append(y)
	graph[y].append(x)
que = deque()
que.append(1)
color = [1] + [0] * n
while que:
	x = que.pop()
	for i in graph[x]:
		if not color[i - 1]:
			que.append(i)
			color[i - 1] = -color[x - 1]
x = color.count(1)
y = n - x
print(x * y - (n - 1))


from collections import defaultdict
n = int(input())
graph = defaultdict(set)
num_edges = n - 1
for i in range(num_edges):
	(a, b) = input().split()
	graph[a].add(b)
	graph[b].add(a)
start = next(iter(graph.keys()))
(left, right) = (set([start]), set())
frontier = [(start, True)]
while frontier:
	(node, is_left) = frontier.pop()
	for neighbor in graph[node]:
		if is_left and neighbor in right or (not is_left and neighbor in left):
			continue
		frontier.append((neighbor, not is_left))
		if is_left:
			right.add(neighbor)
		else:
			left.add(neighbor)
print(len(left) * len(right) - num_edges)


n = int(input())
graph = [[] for _ in range(n + 1)]
visited = [False for _ in range(n + 1)]
mark = [0 for _ 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)
f = 0
r = 1
last = 1
a = 1
b = level = 0
queue = [1]
while f < r:
	u = queue[f]
	visited[u] = True
	f = f + 1
	for v in graph[u]:
		if not visited[v]:
			queue.append(v)
			r = r + 1
	if f == last:
		last = r
		level += 1
		if level % 2 == 1:
			b += r - f
		else:
			a += r - f
print(a * b - n + 1)


n = int(input())
dist = {}
for i in range(n - 1):
	(u, v) = [int(e) for e in input().split()]
	if u not in dist:
		dist[u] = []
	if v not in dist:
		dist[v] = []
	dist[u].append(v)
	dist[v].append(u)
	if i == 0:
		root = u
a = {}
a[root] = 1
q = [root]
while q:
	top = q.pop()
	for e in dist[top]:
		if e not in a:
			a[e] = -a[top]
			q.append(e)
r = list(a.values()).count(1)
print(r * (n - r) - n + 1)


from sys import stdin
input = lambda : stdin.readline().strip()
from math import ceil, sqrt, factorial, gcd
n = int(input())
d = {i: set() for i in range(1, n + 1)}
a = set()
b = set()
for i in range(n - 1):
	(x, y) = map(int, input().split())
	d[x].add(y)
	d[y].add(x)
stack = [1]
while stack:
	i = stack.pop()
	if i in a:
		a.add(i)
		for j in d[i]:
			b.add(j)
			d[j].remove(i)
			stack.append(j)
	else:
		b.add(i)
		for j in d[i]:
			a.add(j)
			d[j].remove(i)
			stack.append(j)
print(len(a) * len(b) - n + 1)


from collections import defaultdict
n = int(input())
d = defaultdict(list)
for _ in range(n - 1):
	(a, b) = input().split(' ')
	a = int(a)
	b = int(b)
	d[a - 1] += [b - 1]
	d[b - 1] += [a - 1]
visited = [1] + [0] * n
queue = [0]
while queue:
	k = queue.pop()
	for i in d[k]:
		if not visited[i]:
			visited[i] = -visited[k]
			queue += [i]
k = visited.count(1)
print(k * (n - k) - n + 1)


import queue

def read():
	n = int(input())
	edges = []
	for i in range(n - 1):
		edges.append(tuple(map(int, input().split(' '))))
	return (n, edges)

def parse_matrix(n, edges):
	matrix = [[0 for i in range(n + 1)] for j in range(n + 1)]
	for (a, b) in edges:
		matrix[a][b] = 1
		matrix[b][a] = 1
	return matrix

def parse_relations(n, edges):
	relations = {}
	for (a, b) in edges:
		if not relations.get(a):
			relations[a] = []
		if not relations.get(b):
			relations[b] = []
		relations[a].append(b)
		relations[b].append(a)
	return relations

def chop(relations, res, fr, flag):
	q = queue.Queue()
	q.put(fr)
	res[fr] = flag
	while not q.empty():
		fr = q.get()
		flag = 3 - res[fr]
		for v in relations[fr]:
			if res[v] == 0:
				q.put(v)
				res[v] = flag

def compute(n, edges):
	relations = parse_relations(n, edges)
	res = [0] * (n + 1)
	chop(relations, res, 1, 1)
	(s1, s2) = (0, 0)
	for i in res[1:]:
		if i == 1:
			s1 += 1
		else:
			s2 += 1
	return s1 * s2 - (n - 1)
(n, edges) = read()
new_edges_count = compute(n, edges)
print(new_edges_count)


from collections import defaultdict

class Graph:

	def __init__(self):
		self.graph = defaultdict(list)

	def addedge(self, v, w):
		self.graph[v].append(w)
		self.graph[w].append(v)

	def dfs(self, s):
		visited = [False for i in range(len(self.graph) + 1)]
		color = [-1 for i in range(len(self.graph) + 1)]
		stack = []
		stack.append(s)
		color[s] = 1
		while len(stack) != 0:
			s = stack[-1]
			stack.pop()
			if not visited[s]:
				visited[s] = True
			for node in self.graph[s]:
				if color[s] == 1:
					color[node] = 0
				else:
					color[node] = 1
				if not visited[node]:
					stack.append(node)
		return color
n = int(input())
g = Graph()
for i in range(n - 1):
	(u, v) = map(int, input().split())
	g.addedge(u, v)
l = g.dfs(1)
a = l.count(1)
b = l.count(0)
print(a * b - n + 1)


import sys

def main():
	numNodes = [int(x) for x in sys.stdin.readline().rsplit()][0]
	adjList = {}
	nodeColors = {}
	unmarked = {}
	for i in range(1, numNodes + 1):
		adjList[i] = []
		unmarked[i] = True
	for line in sys.stdin.read().split('\n'):
		lineUnpacked = [int(x) for x in line.rsplit()]
		if len(lineUnpacked) < 2:
			continue
		(node1, node2) = lineUnpacked
		adjList[node1].append(node2)
		adjList[node2].append(node1)
	bfsList = []
	bfsList.append(1)
	nodeColors[1] = True
	unmarked[1] = False
	set1 = [1]
	set2 = []
	while len(bfsList) > 0:
		nodeConsidered = bfsList.pop(0)
		colorConsidered = nodeColors[nodeConsidered]
		newNodes = [x for x in adjList[nodeConsidered] if unmarked[x]]
		newNodes = list(newNodes)
		for node in newNodes:
			unmarked[node] = False
			nodeColors[node] = not colorConsidered
		bfsList.extend(newNodes)
		if colorConsidered:
			set2.extend(newNodes)
		else:
			set1.extend(newNodes)
	count = 0
	for node in set1:
		count = count + len(set2) - len(adjList[node])
	return count
print(main())


n = int(input())
uv = [[int(x) for x in input().split()] for _ in range(n - 1)]
a = -n + 1
li = [[] for _ in range(n + 1)]
for p in uv:
	li[p[0]].append(p)
	li[p[1]].append(p)
first = 0
second = 0
queue = [1]
seen = set()
while queue:
	first += len(queue)
	a += len(queue) * second
	q2 = []
	for p in queue:
		seen.add(p)
		adjs = li[p]
		for adj in adjs:
			other = adj[0] if adj[0] != p else adj[1]
			if other in seen:
				continue
			q2.append(other)
	(first, second) = (second, first)
	queue = q2
print(a)


from collections import deque, defaultdict
typ = defaultdict(int)
p = defaultdict(list)
n = int(input())
for _ in range(n - 1):
	tmp = list(map(int, input().split()))
	(u, v) = (tmp[0], tmp[1])
	p[u].append(v)
	p[v].append(u)
deq = deque()
deq.append((1, 1))
s1 = 0
s2 = 0
while len(deq):
	cur = deq.popleft()
	(v, t) = (cur[0], cur[1])
	typ[v] = t
	if t == 1:
		s1 += 1
	else:
		s2 += 1
	for i in p[v]:
		if not typ[i]:
			deq.append((i, t * 2 % 3))
print(s1 * s2 - n + 1)


import sys
import threading
from collections import defaultdict
sys.setrecursionlimit(10 ** 6)
threading.stack_size(10 ** 8)
bipartite_set = defaultdict(int)

def main():
	input_list = get_input()
	print(solve(input_list))

def get_input():
	input_list = []
	for line in sys.stdin:
		input_list.append(line.rstrip('\n'))
	return input_list

def generate_graph(input_list):
	graph = defaultdict(set)
	edges = [[int(x) for x in y.split(' ')] for y in input_list[1:]]
	for edge in edges:
		graph[edge[0]].add(edge[1])
		graph[edge[1]].add(edge[0])
	return graph

def solve(input_list):
	global bipartite_set
	graph = generate_graph(input_list)
	generate_bipartite_sets(graph)
	num_edges = 0
	for edge in graph:
		num_edges += len(graph[edge])
	return int(bipartite_set['U'] * bipartite_set['V'] - num_edges / 2)

def generate_bipartite_sets(graph):
	global bipartite_set
	bipartite_set['U'] = 0
	bipartite_set['V'] = 0
	dfs(graph, 1, set(), 0)
	return None

def dfs(graph, vertex, visited, depth):
	global bipartite_set
	if vertex not in visited:
		visited.add(vertex)
		if depth % 2 == 0:
			bipartite_set['U'] += 1
		else:
			bipartite_set['V'] += 1
		for adjacent in graph[vertex]:
			dfs(graph, adjacent, visited, depth + 1)
	return None
t = threading.Thread(target=main)
t.start()
t.join()


from collections import defaultdict, deque
G = defaultdict(set)
n = int(input())
for _ in range(n - 1):
	(U, V) = input().split()
	G[U].add(V)
	G[V].add(U)
queue = deque([('1', 0)])
seen = {'1'}
c = [0, 0]
while queue:
	(U, x) = queue.popleft()
	c[x] += 1
	for V in G[U]:
		if V not in seen:
			queue.append((V, 1 - x))
			seen.add(V)
print(c[0] * c[1] - n + 1)


n = int(input())
G = []
for i in range(n):
	G.append([])
for i in range(n - 1):
	(u, v) = [int(x) - 1 for x in input().split()]
	G[u].append((v, u))
	G[v].append((u, v))
options = G[0]
visited = [0] * n
visited[0] = 1
colors = [0] * n
while options:
	t = options.pop()
	if visited[t[0]] == 0:
		visited[t[0]] = 1
		colors[t[0]] = 1 - colors[t[1]]
		options.extend(G[t[0]])
x = sum(colors)
print(x * (n - x) - n + 1)


n = int(input())
li = [[] for i in range(n + 1)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	li[a].append(b)
	li[b].append(a)
stack = [(1, 1)]
(i, j) = (0, 0)
visited = [False] * (n + 1)
(set1, set2) = (0, 0)
while len(stack) != 0:
	item = stack.pop()
	visited[item[0]] = True
	if item[1] == 1:
		set1 += 1
	else:
		set2 += 1
	for i in range(len(li[item[0]])):
		if not visited[li[item[0]][i]]:
			stack.append((li[item[0]][i], 2 if item[1] == 1 else 1))
print(set1 * set2 - (n - 1))


n = int(input())
d = {}
s1 = set()
s2 = set()
ans = 0
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	if u not in d:
		d[u] = {v}
	else:
		d[u].add(v)
	if v not in d:
		d[v] = {u}
	else:
		d[v].add(u)
stack = [1]
while stack:
	i = stack.pop()
	if i in s1:
		for j in d[i]:
			s2.add(j)
			d[j].remove(i)
			stack.append(j)
	else:
		s2.add(i)
		for j in d[i]:
			s1.add(j)
			d[j].remove(i)
			stack.append(j)
print(len(s1) * len(s2) - (n - 1))


n = int(input())
adj = [[[], 0, 0] for i in range(n)]
for i in range(n - 1):
	(u, v) = map(int, input().split())
	adj[u - 1][0].append(v - 1)
	adj[v - 1][0].append(u - 1)
queue = [0]
while queue:
	curr_v = queue.pop(0)
	adj[curr_v][2] = 1
	for u in adj[curr_v][0]:
		if not adj[u][2]:
			queue.append(u)
			adj[u][1] = adj[curr_v][1] + 1
ev = 0
n_ev = 0
for el in adj:
	if el[1] % 2 == 0:
		ev += 1
	else:
		n_ev += 1
ans = 0
for el in adj:
	if el[1] % 2 == 0:
		ans += n_ev - len(el[0])
	else:
		ans += ev - len(el[0])
print(ans // 2)


n = int(input())
l = [1] + [0] * n
d = [[] for _ in range(n)]
c = [0]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	d[a - 1] += [b - 1]
	d[b - 1] += [a - 1]
while c:
	x = c.pop()
	for y in d[x]:
		if not l[y]:
			c += [y]
			l[y] = -l[x]
r = l.count(1)
print(r * (n - r) - n + 1)


n = int(input())
e = {}
for i in range(n - 1):
	(a, b) = map(int, input().split(' '))
	x = e.get(a, [])
	x.append(b)
	e[a] = x
	x = e.get(b, [])
	x.append(a)
	e[b] = x
c = set()
d = set()
c.add(1)
temp = [1]
seen = set()
while len(temp) > 0:
	i = temp.pop(0)
	seen.add(i)
	if i in c:
		for j in e[i]:
			d.add(j)
			if j not in seen:
				temp.append(j)
	else:
		for j in e[i]:
			c.add(j)
			if j not in seen:
				temp.append(j)
x = len(c)
y = len(d)
print(x * y - n + 1)


n = int(input())
d = {}
for i in range(1, n + 1):
	d[i] = []
for _ in range(n - 1):
	(u, v) = map(int, input().split(' '))
	d[u].append(v)
	d[v].append(u)
arr = [-1] * (n + 1)
visited = [False] * (n + 1)
stack = [1]
visited[1] = True
arr[1] = 0
while len(stack) != 0:
	x = stack.pop(0)
	for i in d[x]:
		if not visited[i]:
			arr[i] = 1 - arr[x]
			stack.append(i)
			visited[i] = True
zero = 0
one = 0
for i in range(1, n + 1):
	if arr[i] == 0:
		zero += 1
	else:
		one += 1
print(zero * one - (n - 1))


n = int(input())
from collections import defaultdict
E = defaultdict(list)
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	E[a].append(b)
	E[b].append(a)
stack = [1]
visited = {1}
c = 0
d = 0
turn = True
while stack:
	nstack = []
	for v in stack:
		for u in E[v]:
			if u not in visited:
				nstack.append(u)
				visited.add(u)
	if turn:
		d += len(stack)
	else:
		c += len(stack)
	turn = not turn
	stack = nstack
print(c * d - (n - 1))


from collections import Counter
nodes_nr = int(input())
node_idx___neigh_idxes = []
for _ in range(nodes_nr):
	node_idx___neigh_idxes.append([])
for _ in range(nodes_nr - 1):
	(node_idx1, node_idx2) = (int(x) - 1 for x in input().split())
	node_idx___neigh_idxes[node_idx1].append(node_idx2)
	node_idx___neigh_idxes[node_idx2].append(node_idx1)
node_idx___group = [-1] * nodes_nr
stack = []
stack.append(0)
node_idx___group[0] = 0
while stack:
	curr_node_idx = stack.pop()
	for neigh_idx in node_idx___neigh_idxes[curr_node_idx]:
		if node_idx___group[neigh_idx] == -1:
			if node_idx___group[curr_node_idx] == 0:
				node_idx___group[neigh_idx] = 1
			else:
				node_idx___group[neigh_idx] = 0
			stack.append(neigh_idx)
counter = Counter(node_idx___group)
ans = counter[0] * counter[1] - nodes_nr + 1
print(ans)


import math
import sys
from collections import defaultdict
from collections import Counter
from collections import deque
import bisect
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
ilele = lambda : map(int, input().split())
alele = lambda : list(map(int, input().split()))

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)]
INF = 10 ** 18
MOD = 10 ** 9 + 7
first = 1
G = defaultdict(list)

def addEdge(a, b):
	G[a].append(b)
	G[b].append(a)

def BFSUtil(queue, vis, level):
	while queue:
		s = queue.popleft()
		for child in G.get(s, []):
			if vis[child] == False:
				queue.append(child)
				level[child] = level[s] + 1
				vis[child] = True

def nodesatlevel(node, N):
	vis = [False for i in range(N + 1)]
	level = {}
	queue = deque()
	level[node] = 0
	queue.append(node)
	vis[node] = True
	BFSUtil(queue, vis, level)
	return level
mark = {}
N = int(input())
for i in range(N - 1):
	(u, v) = ilele()
	addEdge(u, v)
root = 1
mark = nodesatlevel(root, N)
len1 = 0
len2 = 0
for j in mark.values():
	if j % 2 == 0:
		len1 += 1
	else:
		len2 += 1
Ans = 0
print(len1 * len2 - (N - 1))


import math
import collections
import bisect
import heapq
import time
import random
N = int(input())
(s, t) = (set(), set())
edges = collections.defaultdict(list)
for i in range(N - 1):
	(u, v) = map(int, input().split())
	edges[u].append(v)
	edges[v].append(u)
s.add(1)
q = [1]
while q:
	(s, t) = (t, s)
	p = []
	for u in q:
		for v in edges[u]:
			if v not in s:
				s.add(v)
				p.append(v)
	q = p
ns = len(s)
nt = len(t)
print(ns * nt - (N - 1))


import collections, sys, threading
sys.setrecursionlimit(10 ** 9)
threading.stack_size(67108864)
de = [0] * 1000000
adjlist = list()
visited = [0] * 1000000
(even, odd) = (0, 0)

def dfs(s, depth):
	global even
	global odd
	de[s] = depth
	visited[s] = 1
	if depth % 2 == 0:
		even = even + 1
	else:
		odd = odd + 1
	for i in range(0, len(adjlist[s])):
		v = adjlist[s][i]
		if visited[v] == 0:
			dfs(v, depth + 1)

def main():
	n = int(input())
	for i in range(0, n + 1):
		adjlist.append(list())
	for i in range(0, n - 1):
		hi = input()
		yo = hi.split()
		a = int(yo[0])
		b = int(yo[1])
		adjlist[a].append(b)
		adjlist[b].append(a)
	dfs(1, 0)
	tot = 0
	for i in range(1, n + 1):
		if de[i] % 2 == 0:
			tot = tot + odd - len(adjlist[i])
		else:
			tot = tot + even - len(adjlist[i])
	print(int(tot / 2))
thread = threading.Thread(target=main)
thread.start()


read = lambda : tuple(map(int, input().split()))
n = read()[0]
eds = []
g = {}
k = {}
for i in range(n - 1):
	(u, v) = read()
	r = u
	k[v] = True
	if not u in g:
		g[u] = [v]
	else:
		g[u] += [v]
	if not v in g:
		g[v] = [u]
	else:
		g[v] += [u]

def req(vl, visited):
	vs = []
	for v in vl:
		if v in g and (not v in visited):
			vs += [el for el in g[v] if not el in visited]
			visited[v] = True
	return vs
vs = [r]
k = 0
z = [0, 1]
visited = {}
while True:
	vs = req(vs, visited)
	if len(vs) == 0:
		break
	z[k % 2] += len(vs)
	k += 1
print(z[0] * z[1] - n + 1)


n = int(input())
g1 = {}
g2 = {}
gr = [[] for i in range(n)]
for i in range(n - 1):
	(x, y) = map(int, input().strip().split())
	gr[x - 1].append(y)
	gr[y - 1].append(x)
par = {}
for i in range(n):
	if i + 1 not in par:
		par[i + 1] = 1
		g1[i + 1] = 1
		st = [i + 1]
		while st:
			u = st.pop()
			for x in gr[u - 1]:
				if x not in par:
					par[x] = 1
					st.append(x)
					if u in g1:
						g2[x] = 1
					else:
						g1[x] = 1
ans = 0
for x in g1:
	ans += n - len(g1) - len(gr[x - 1])
print(ans)


from collections import defaultdict
from collections import deque
n = int(input())
d = defaultdict(list)
for i in range(n - 1):
	(u, v) = map(int, input().split())
	d[u].append(v)
	d[v].append(u)
visited = [0] * (n + 1)
c = {}
(nr, nb) = (0, 0)
q = deque()
q.append(1)
visited[1] = 1
c[1] = 'R'
nr = nr + 1
while q:
	i = q.popleft()
	co = 'R' if c[i] == 'B' else 'B'
	for j in d[i]:
		if visited[j] == 0:
			visited[j] = 1
			c[j] = co
			if co == 'R':
				nr = nr + 1
			else:
				nb = nb + 1
			q.append(j)
ans = 0
for i in d:
	if c[i] == 'R':
		ans = ans + nb - len(d[i])
	else:
		ans = ans + nr - len(d[i])
print(ans // 2)


from collections import defaultdict
from queue import Queue as Q
n = int(input())
e = defaultdict(list)
for i in range(n - 1):
	(x, y) = tuple(map(int, input().split()))
	e[x].append(y)
	e[y].append(x)

def bfs(v):
	mark = defaultdict(int)
	q = Q()
	q.put(v)
	mark[v] = 1
	while not q.empty():
		v = q.get()
		for i in e[v]:
			if mark[i] == 0:
				mark[i] = mark[v] * -1
				q.put(i)
	return sum((value == 1 for value in mark.values()))
a = bfs(1)
print(a * (n - a) - (n - 1))


import sys
import threading
sys.setrecursionlimit(300000)
threading.stack_size(10 ** 8)

def main():

	def dfs(vertex, used, g, color):
		used[vertex] = color
		color *= -1
		if color == 1:
			rw[1] += 1
		else:
			rw[0] += 1
		for start in g[vertex]:
			if used[start] == 0:
				dfs(start, used, g, color)
	n = int(input())
	g = [set() for s in range(n + 1)]
	used = [0] * (n + 1)
	rw = [0] * 2
	for _ in range(n - 1):
		(a, b) = map(int, input().split())
		g[a].add(b)
		g[b].add(a)
	dfs(1, used, g, 1)
	print(rw[0] * rw[1] - n + 1)
t = threading.Thread(target=main)
t.start()
t.join()


from math import *
import threading
import sys
from collections import defaultdict
from pprint import pprint
sys.setrecursionlimit(300000)
threading.stack_size(10 ** 8)
mod = 10 ** 9
inf = 10 ** 15
yes = 'YES'
no = 'NO'
import os
import sys
from io import BytesIO, IOBase
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')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def npr(n, r):
	return factorial(n) // factorial(n - r) if n >= r else 0

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(n - r)) if n >= r else 0

def lower_bound(li, num):
	answer = -1
	start = 0
	end = len(li) - 1
	while start <= end:
		middle = (end + start) // 2
		if li[middle] >= num:
			answer = middle
			end = middle - 1
		else:
			start = middle + 1
	return answer

def upper_bound(li, num):
	answer = -1
	start = 0
	end = len(li) - 1
	while start <= end:
		middle = (end + start) // 2
		if li[middle] <= num:
			answer = middle
			start = middle + 1
		else:
			end = middle - 1
	return answer

def abs(x):
	return x if x >= 0 else -x

def binary_search(li, val):
	ans = -1
	lb = 0
	ub = len(li) - 1
	while lb <= ub:
		mid = (lb + ub) // 2
		if li[mid] > val:
			ub = mid - 1
		elif val > li[mid]:
			lb = mid + 1
		else:
			ans = mid
			break
	return ans

def kadane(x):
	sum_so_far = 0
	current_sum = 0
	for i in x:
		current_sum += i
		if current_sum < 0:
			current_sum = 0
		else:
			sum_so_far = max(sum_so_far, current_sum)
	return sum_so_far

def pref(li):
	pref_sum = [0]
	for i in li:
		pref_sum.append(pref_sum[-1] + i)
	return pref_sum

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	li = []
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, len(prime)):
		if prime[p]:
			li.append(p)
	return li

def primefactors(n):
	factors = []
	while n % 2 == 0:
		factors.append(2)
		n //= 2
	for i in range(3, int(sqrt(n)) + 1, 2):
		while n % i == 0:
			factors.append(i)
			n //= i
	if n > 2:
		factors.append(n)
	return factors

def prod(li):
	ans = 1
	for i in li:
		ans *= i
	return ans

def dist(a, b):
	d = abs(a[1] - b[1]) + abs(a[2] - b[2])
	return d

def power_of_n(x, n):
	cnt = 0
	while x % n == 0:
		cnt += 1
		x //= n
	return cnt

def main():
	for _ in range(1):
		n = int(input())
		d = {}
		for i in range(n - 1):
			(a, b) = map(int, input().split())
			if a not in d:
				d[a] = [b]
			else:
				d[a] += [b]
			if b not in d:
				d[b] = [a]
			else:
				d[b] += [a]
		color = [-1] * n

		def dfs(n, col):
			color[n - 1] = col
			for child in d[n]:
				if color[child - 1] == -1:
					dfs(child, col ^ 1)
		dfs(1, 1)
		ans = color.count(0) * color.count(1) - n + 1
		print(ans)
t = threading.Thread(target=main)
t.start()
t.join()


n = int(input())
a = []
visited = []
tovisit = []
for i in range(n + 1):
	a.append([])
	visited.append(0)
for i in range(n - 1):
	(u, v) = map(int, input().split())
	a[u].append(v)
	a[v].append(u)
i = 0
tovisit.append((1, 1))
while len(tovisit) > 0:
	(x, y) = tovisit.pop()
	if visited[x]:
		pass
	else:
		visited[x] = y
		for i in a[x]:
			tovisit.append((i, -1 * y))
set1 = 0
set2 = 0
for i in range(1, n + 1):
	if visited[i] == 1:
		set1 += 1
	else:
		set2 += 1
print(set1 * set2 - (n - 1))


n = int(input())
tr = {}
for i in range(1, n + 1):
	tm = []
	tr[i] = tm
for i in range(n - 1):
	(x, y) = map(int, input().strip().split(' '))
	tr[x].append(y)
	tr[y].append(x)
a = set({})
b = set({})
sv = 0
q = [1]
ans = 0
a.add(1)
while len(q) > 0:
	x = q.pop(0)
	if a.__contains__(x):
		sv = 0
	elif b.__contains__(x):
		sv = 1
	for i in tr[x]:
		if sv == 0:
			if b.__contains__(i) == False:
				b.add(i)
				q.append(i)
		elif sv == 1:
			if a.__contains__(i) == False:
				a.add(i)
				q.append(i)
for i in a:
	ans += len(b) - len(tr[i])
print(ans)


(WHITE, BLACK) = (0, 1)

def dfs(adj, node_colors):
	stk = [0]
	node_colors[0] = WHITE
	while stk:
		node = stk.pop()
		for i in range(len(adj[node])):
			if node_colors[adj[node][i]] == -1:
				node_colors[adj[node][i]] = 1 - node_colors[node]
				stk.append(adj[node][i])
n = int(input())
adj = [[] for _ in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	adj[a - 1].append(b - 1)
	adj[b - 1].append(a - 1)
node_colors = [-1] * n
dfs(adj, node_colors)
n_nodes = [node_colors.count(WHITE), node_colors.count(BLACK)]
print(sum([n_nodes[1 - node_colors[i]] - len(adj[i]) for i in range(n)]) // 2)


def solve(vertices, edge):
	table = {i: [] for i in range(1, vertices + 1)}
	visited = [False] * (vertices + 1)
	setA = 0
	setB = 0
	putSetA = True
	for (i, j) in edge:
		table[i].append(j)
		table[j].append(i)
	queue = [edge[0][0]]
	while len(queue) > 0:
		index = 0
		length = len(queue)
		while index < length:
			if visited[queue[index]]:
				index += 1
				continue
			if putSetA:
				setA += 1
			else:
				setB += 1
			queue.extend(table[queue[index]])
			visited[queue[index]] = True
			index += 1
		queue = queue[index:]
		if putSetA:
			putSetA = False
		else:
			putSetA = True
	return setA * setB - (vertices - 1)
v = int(input())
ed = []
for _ in range(v - 1):
	ed.append(list(map(int, input().split())))
print(solve(v, ed))


import sys
n = int(sys.stdin.readline().strip())
neighbours = {}
for i in range(n - 1):
	(u, v) = (int(x) for x in sys.stdin.readline().strip().split(' '))
	if u in neighbours:
		neighbours[u].append(v)
	else:
		neighbours[u] = [v]
	if v in neighbours:
		neighbours[v].append(u)
	else:
		neighbours[v] = [u]
start = list(neighbours.keys())[0]
stack = [(start, True)]
visited = set()
A = 0
B = 0
while stack:
	(curr, colour) = stack.pop()
	if curr in visited:
		continue
	visited.add(curr)
	if colour:
		A += 1
	else:
		B += 1
	for neighbour in neighbours[curr]:
		if neighbour not in visited:
			stack.append((neighbour, not colour))
total_edges = A * B
print(total_edges - n + 1)


n = int(input())
edges = [[] for i in range(n)]
for i in range(n - 1):
	(u, v) = map(int, input().split())
	edges[u - 1].append(v - 1)
	edges[v - 1].append(u - 1)
colors = [-1 for i in range(n)]
dfs = [(0, 0)]
while len(dfs) > 0:
	(node, color) = dfs.pop()
	colors[node] = color
	for neighbor in edges[node]:
		if colors[neighbor] == -1:
			dfs.append((neighbor, 1 - color))
blue = len([x for x in colors if x == 0])
red = n - blue
total_graph_edges = blue * red
print(blue * red - (n - 1))


from collections import deque
n = int(input())
adj = [[] for i in range(n)]
for i in range(n - 1):
	(u, v) = input().split()
	(u, v) = (int(u), int(v))
	adj[u - 1].append(v - 1)
	adj[v - 1].append(u - 1)
queue = deque()
queue.append((0, 0))
h = [0 for i in range(n)]
h_even = 1
h_odd = 0
while len(queue) > 0:
	tmp = queue.pop()
	p = tmp[1]
	u = tmp[0]
	for v in adj[u]:
		if v == p:
			continue
		h[v] = h[u] + 1
		if h[v] % 2 == 0:
			h_even += 1
		else:
			h_odd += 1
		queue.append((v, u))
print(h_even * h_odd - n + 1)


n = int(input())
stack = []
stack.append([])
stack.append([])
ab = [0, 0]
minn = 100000
d = set()
c = [[] for i in range(n)]
for i in range(n - 1):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	c[min(u, v)].append(max(u, v))
	c[max(u, v)].append(min(u, v))
	if minn > min(u, v):
		minn = min(u, v)
d.add(minn)
stack[0].append(minn)
while len(stack[0]) or len(stack[1]) or len(d) != n:
	for i in range(2):
		if len(stack[i]):
			ab[i] += 1
			k = stack[i].pop()
			for s in range(len(c[k])):
				if c[k][s] not in d:
					d.add(c[k][s])
					stack[2 - i - 1].append(c[k][s])
cou = ab[0] * ab[1]
print(cou - n + 1)


n = int(input())
color = [-1 for i in range(n + 1)]
graph = {}
for _ in range(n - 1):
	(a, b) = list(map(int, input().split(' ')))
	if a in graph:
		graph[a].append(b)
	else:
		graph[a] = [b]
	if b in graph:
		graph[b].append(a)
	else:
		graph[b] = [a]
remaining = 1
col = 0
next = [1]
while next != []:
	tempo = []
	for node in next:
		color[node] = col
		for neighbor in graph[node]:
			if color[neighbor] == -1:
				tempo.append(neighbor)
	col = 1 - col
	next = tempo[:]
pair = color.count(0)
impair = color.count(1)
print(pair * impair - (n - 1))


import sys
(MOD, mod) = (1000000007, 998244353)
from collections import deque, Counter, OrderedDict, defaultdict

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

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

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

def is_bipartite(graph):
	n = len(graph)
	color = [-1] * (n + 1)
	for start in range(1, n + 1):
		if color[start] == -1:
			color[start] = 0
			stack = [start]
			while stack:
				parent = stack.pop()
				for child in graph[parent]:
					if color[child] == -1:
						color[child] = 1 - color[parent]
						stack.append(child)
					elif color[parent] == color[child]:
						return (False, color)
	return (True, color[1:])
n = int(input())
graph = defaultdict(list)
for i in range(n - 1):
	(x, y) = get_ints()
	graph[x].append(y)
	graph[y].append(x)
(a, color) = is_bipartite(graph)
Arr1 = []
Arr2 = []
for i in range(n):
	if color[i] == 0:
		Arr1.append(i + 1)
	else:
		Arr2.append(i + 1)
count = 0
n1 = len(Arr1)
n2 = len(Arr2)
for i in Arr1:
	count += n2 - len(graph[i])
for i in Arr2:
	count += n1 - len(graph[i])
print(count // 2)


n = int(input())
g = [[] for _ in range(n + 1)]
for _ in range(n - 1):
	(u, v) = list(map(int, input().split()))
	g[u].append(v)
	g[v].append(u)
st = [(1, 0, 0)]
m = 0
while st:
	(u, p, c) = st.pop()
	m += c
	st.extend(((v, u, 1 - c) for v in g[u] if v != p))
print(m * (n - m) - n + 1)


n = int(input())
g = [[] for _ in range(n)]
for _ in range(n - 1):
	(a, b) = map(lambda x: int(x) - 1, input().split())
	g[a].append(b)
	g[b].append(a)
from collections import deque

def solve(n, g):
	visited = []
	cols = []
	for _ in range(n):
		visited.append(0)
		cols.append(None)
	visited[0] = 1
	cnt_A = 0
	cnt_B = 0
	nodes = deque([(0, 0)])
	while nodes:
		(node, col) = nodes.popleft()
		cols[node] = col
		if col == 0:
			cnt_A += 1
		else:
			cnt_B += 1
		for nb in g[node]:
			if not visited[nb]:
				nodes.append((nb, 0 if col == 1 else 1))
				visited[nb] = 1
	count = 0
	cnts = [cnt_A, cnt_B]
	for (col, node) in zip(cols, range(n)):
		other_cnt = cnts[0 if col == 1 else 1]
		count += max(0, other_cnt - len(g[node]))
	return count // 2
print(solve(n, g))


from collections import defaultdict
n = int(input())
edges = defaultdict(list)
for i in range(n - 1):
	(v1, v2) = [int(x) for x in input().split()]
	edges[v1].append(v2)
	edges[v2].append(v1)
counts = [0, 0]
visited = set()
queue = [(1, 0)]
while len(queue) > 0:
	(v, c) = queue.pop()
	visited.add(v)
	counts[c] += 1
	for node in edges[v]:
		if node not in visited:
			queue.append((node, 1 - c))
print(counts[0] * counts[1] - n + 1)


from collections import deque
n = int(input())
graph = dict(((i, set()) for i in range(1, n + 1)))
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	graph[u].add(v)
	graph[v].add(u)
red = set()
purple = set()
visited = {1}
Q = deque([(1, True)])
while Q:
	(cur, label) = Q.popleft()
	if label:
		red.add(cur)
	else:
		purple.add(cur)
	for nei in graph[cur]:
		if nei not in visited:
			visited.add(nei)
			Q.append((nei, not label))
print(sum((len(purple) - len(graph[r]) for r in red)))


n = int(input())
l = [0] * n
d = {}
d = [[] for _ in range(n)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	d[a - 1].append(b)
	d[b - 1].append(a)
l[0] = 1
check = [1]
while check:
	x = check.pop()
	for y in d[x - 1]:
		if not l[y - 1]:
			check.append(y)
			l[y - 1] = -1 * l[x - 1]
red = l.count(1)
print(red * (n - red) - n + 1)


LEFT = 0
RIGHT = 1

def get_ints():
	return [int(n) for n in input().split()]
import sys
a = get_ints()
assert len(a) == 1
n = a[0]
links = [set() for i in range(n)]
for i in range(n - 1):
	a = get_ints()
	assert len(a) == 2
	for j in range(2):
		a[j] -= 1
	links[a[0]].add(a[1])
	links[a[1]].add(a[0])
count = [0, 0]
looked = [False for i in range(n)]
stack = dict()
stack[0] = LEFT
while stack:
	(index, side) = stack.popitem()
	if not looked[index]:
		looked[index] = True
		count[side] += 1
		for i in links[index]:
			stack[i] = 1 - side
res = count[LEFT] * count[RIGHT] - n + 1
print('%d' % res)


import sys
sys.setrecursionlimit(300005)
n = int(input())
g = [[] for i in range(n)]
used = [0] * n
for i in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	g[a].append(b)
	g[b].append(a)
x = 0
y = 0
q = [(0, 1)]
used[0] = 1
while len(q) != 0:
	(v, color) = q.pop()
	for vert in g[v]:
		if used[vert] == 0:
			used[vert] = 3 - color
			q.append((vert, 3 - color))
for i in range(n):
	if used[i] == 1:
		x += 1
	else:
		y += 1
print(x * y - n + 1)


from collections import deque, Counter, OrderedDict, defaultdict

def is_bipartite(graph):
	n = len(graph)
	color = [-1] * (n + 1)
	for start in range(1, n + 1):
		if color[start] == -1:
			color[start] = 0
			stack = [start]
			while stack:
				parent = stack.pop()
				for child in graph[parent]:
					if color[child] == -1:
						color[child] = 1 - color[parent]
						stack.append(child)
					elif color[parent] == color[child]:
						return (False, color)
	return (True, color[1:])
n = int(input())
graph = defaultdict(list)
for i in range(n - 1):
	(x, y) = map(int, input().split())
	graph[x].append(y)
	graph[y].append(x)
(a, color) = is_bipartite(graph)
Arr1 = []
Arr2 = []
for i in range(n):
	if color[i] == 0:
		Arr1.append(i + 1)
	else:
		Arr2.append(i + 1)
count = 0
n1 = len(Arr1)
n2 = len(Arr2)
for i in Arr1:
	count += n2 - len(graph[i])
for i in Arr2:
	count += n1 - len(graph[i])
print(count // 2)


n = int(input())
g = [[] for i in range(n)]
for _ in range(n - 1):
	(s, t) = map(int, input().split())
	g[s - 1].append(t - 1)
	g[t - 1].append(s - 1)
q = [0]
color = [1] + [0] * n
while q:
	node = q.pop()
	for to in g[node]:
		if not color[to]:
			q.append(to)
			color[to] = -color[node]
x = color.count(1)
y = n - x
print(x * y - (n - 1))


from collections import defaultdict
G = defaultdict(set)
n = int(input())
for _ in range(n - 1):
	(U, V) = input().split()
	G[U].add(V)
	G[V].add(U)
stack = [('1', 0)]
seen = {'1'}
c = [0, 0]
while stack:
	(U, x) = stack.pop()
	c[x] += 1
	for V in G[U]:
		if V not in seen:
			stack.append((V, 1 - x))
			seen.add(V)
print(c[0] * c[1] - n + 1)


double_graph = {}
n = int(input())
R = set()
L = set()
for i in range(n - 1):
	(a1, a2) = input().split()
	if a1 not in double_graph.keys():
		double_graph[a1] = []
	if a2 not in double_graph.keys():
		double_graph[a2] = []
	double_graph[a1].append(a2)
	double_graph[a2].append(a1)
stack = [('1', 0)]
visited = {'1'}
L_R = [0, 0]
while stack:
	(a1, count) = stack.pop()
	L_R[count] += 1
	for a2 in double_graph[a1]:
		if a2 not in visited:
			stack.append((a2, 1 - count))
			visited.add(a2)
ans = L_R[0] * L_R[1] - n + 1
print(ans)


import sys
from collections import defaultdict
input = __import__('sys').stdin.readline
adj = defaultdict(list)
n = int(input())
for i in range(n - 1):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	adj[u].append(v)
	adj[v].append(u)
color = [-1] * n
for i in range(n):
	if color[i] == -1:
		color[i] = 0
		stack = [i]
		while stack:
			node = stack.pop()
			for x in adj[node]:
				if color[x] == -1:
					color[x] = color[node] ^ 1
					stack.append(x)
left = color.count(0)
right = n - left
print(left * right - (n - 1))


n = int(input())
edges = dict()
for i in range(n - 1):
	[v1, v2] = list(map(int, input().split()))
	edges.setdefault(v1, [])
	edges[v1].append(v2)
	edges.setdefault(v2, [])
	edges[v2].append(v1)
visited = [False] * (n + 1)
queue = [(1, False)]
curr = 0
(cntb, cntnotb) = (0, 0)
while curr < len(queue):
	(el, b) = queue[curr]
	visited[el] = True
	if b:
		cntb += 1
	else:
		cntnotb += 1
	for neigh in edges[el]:
		if not visited[neigh]:
			queue.append((neigh, not b))
	curr += 1
print(cntb * cntnotb - (n - 1))


def TotalEdges(graph):
	total = 0
	for i in graph:
		total += len(graph[i])
	return int(total / 2)

def DFS(graph, vertex, isVisited, colors):
	stack = [vertex]
	while stack:
		curr = stack.pop()
		if not isVisited[curr - 1]:
			isVisited[curr - 1] = True
			if colors[curr - 1] == 0:
				colors[curr - 1] = 1
			for kid in graph[curr]:
				stack.append(kid)
				colors[kid - 1] = 3 - colors[curr - 1]

def Solve(graph, n):
	colors = [0] * n
	isVisited = [False] * n
	for i in graph:
		DFS(graph, i, isVisited, colors)
	first = 0
	second = 0
	for i in colors:
		if i == 1:
			first += 1
		else:
			second += 1
	print(first * second - TotalEdges(graph))

def main():
	n = int(input())
	graph = {}
	for i in range(1, n + 1):
		graph[i] = []
	parents = {}
	for i in range(1, n + 1):
		parents[i] = []
	for i in range(n - 1):
		(start, end) = map(int, input().split())
		graph[start].append(end)
		graph[end].append(start)
	Solve(graph, n)
main()


def bfs():
	cur = 0
	que = [1]
	status[1] = 1
	while cur != len(que):
		u = que[cur]
		for v in p[u]:
			if status[v] == 0:
				status[v] = 0 - status[u]
				que.append(v)
		cur += 1
n = int(input())
p = [[] for _ in range(n + 10)]
for i in range(n - 1):
	(u, v) = map(int, input().split())
	p[u].append(v)
	p[v].append(u)
status = [0 for _ in range(n + 10)]
bfs()
cnt = 0
for x in status:
	if x == 1:
		cnt += 1
answer = cnt * (n - cnt) - (n - 1)
print(answer)


import collections
n = int(input())
g = [[] for _ in range(n + 1)]
rd = [0] * (n + 1)
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	g[u].append(v)
	g[v].append(u)
	rd[u] += 1
	rd[v] += 1
flag = [-1] * (n + 1)
js = [0] * 2
q = [1]
b = 0
flag[1] = 0
while q:
	js[b] += len(q)
	nq = []
	for c in q:
		flag[c] = b
		for nc in g[c]:
			if flag[nc] == -1:
				nq.append(nc)
	b ^= 1
	q = nq[:]
ans = 0
for i in range(1, n + 1):
	ans += js[1 - flag[i]] - rd[i]
print(ans >> 1)


from sys import stdin, stdout, setrecursionlimit
import threading

class Tail_Recursion_Optimization:

	def __init__(self, recursion_limit, stack_size):
		setrecursionlimit(recursion_limit)
		threading.stack_size(stack_size)
		return None

class SOLVE:

	def dfs(self, u, node, color, A, B):
		(A if color[u] else B).append(u)
		for v in node[u]:
			if color[v] == None:
				color[v] = color[u] ^ 1
				self.dfs(v, node, color, A, B)
		return 0

	def solve(self):
		R = stdin.readline
		W = stdout.write
		ans = []
		n = int(R())
		node = [[] for i in range(n + 1)]
		for i in range(n - 1):
			(u, v) = [int(x) for x in R().split()]
			node[u].append(v)
			node[v].append(u)
		color = [None for i in range(n + 1)]
		(A, B) = ([], [])
		color[1] = 1
		self.dfs(1, node, color, A, B)
		total = 0
		(a, b) = (len(A), len(B))
		for i in range(1, n + 1):
			total += (b if color[i] else a) - len(node[i])
		total //= 2
		W('%d' % total)
		return 0

def main():
	s = SOLVE()
	s.solve()
Tail_Recursion_Optimization(10 ** 7, 2 ** 26)
threading.Thread(target=main).start()


n = int(input())
edges = {}
start = None
edge_count = 0
for _ in range(n - 1):
	(u, v) = map(int, input().strip().split())
	if u in edges:
		edges[u].add(v)
	else:
		edges[u] = {v}
	if v in edges:
		edges[v].add(u)
	else:
		edges[v] = {u}
	edge_count += 1
	if start is None:
		start = u
(A, B) = (set(), set())
visited = {start}
stack = [(start, True)]
while stack:
	(n, i) = stack.pop()
	if i:
		A.add(n)
	else:
		B.add(n)
	for neighb in edges[n]:
		if neighb not in visited:
			visited.add(neighb)
			stack.append((neighb, not i))
print(len(A) * len(B) - edge_count)


import sys

def solve():
	n = int(sys.stdin.readline())
	g = [set() for _ in range(n + 1)]
	count = 0
	for _ in range(n - 1):
		(a, b) = map(int, sys.stdin.readline().split(' '))
		g[a].add(b)
		g[b].add(a)
	(red, blue) = (set(), set())
	nodes = [1]
	while nodes:
		node = nodes.pop()
		if node not in red and node not in blue or node in red:
			red.add(node)
			for other_node in g[node]:
				if other_node not in blue:
					blue.add(other_node)
					nodes.append(other_node)
		else:
			for other_node in g[node]:
				if other_node not in red:
					red.add(other_node)
					nodes.append(other_node)
	for red_node in red:
		count += len(blue) - len(g[red_node])
	sys.stdout.write(str(count))
solve()


class CodeforcesTask862BSolution:

	def __init__(self):
		self.result = ''
		self.n = 0
		self.tree = []

	def read_input(self):
		self.n = int(input())
		for x in range(self.n - 1):
			self.tree.append([int(y) for y in input().split(' ')])

	def process_task(self):
		graph = [[] for x in range(self.n)]
		label = [-1] * self.n
		for edge in self.tree:
			graph[edge[0] - 1].append(edge[1])
			graph[edge[1] - 1].append(edge[0])
		to_visit = [(1, True)]
		while to_visit:
			visiting = to_visit.pop(-1)
			if label[visiting[0] - 1] == -1:
				label[visiting[0] - 1] = visiting[1]
				to_visit += [(x, not visiting[1]) for x in graph[visiting[0] - 1]]
		b1 = label.count(True)
		b2 = label.count(False)
		self.result = str(b1 * b2 - self.n + 1)

	def get_result(self):
		return self.result
Solution = CodeforcesTask862BSolution()
Solution.read_input()
Solution.process_task()
print(Solution.get_result())


from collections import defaultdict

def checkbi(hash, node):
	queue = [node]
	s1 = {node}
	s2 = set()
	while queue != []:
		z = queue.pop(-1)
		if z in s1:
			yo = 1
		else:
			yo = 0
		for i in hash[z]:
			if i not in s1 and i not in s2:
				if yo == 1:
					s2.add(i)
				else:
					s1.add(i)
				queue.append(i)
			elif i in s1 and yo == 1 or (i in s2 and yo == 0):
				return False
	return (s1, s2)
n = int(input())
hash = defaultdict(list)
for i in range(n - 1):
	(a, b) = map(int, input().split())
	hash[a].append(b)
	hash[b].append(a)
(s1, s2) = checkbi(hash, 1)
ans = 0
for i in s1:
	ans += len(s2) - len(hash[i])
print(ans)


def bfs(d):
	queue = [[0, 0]]
	mark = {i: False for i in range(n)}
	(part1, part2) = (0, 0)
	while queue:
		q = queue.pop(0)
		(v, e) = (q[0], q[1])
		if e == 0:
			part1 += 1
		else:
			part2 += 1
		e = 1 - e
		mark[v] = True
		for (i, x) in enumerate(d[v]):
			if mark[x] == False:
				queue.append([x, e])
	return (part1, part2)
n = int(input())
d = {}
from sys import stdin
for i in range(n - 1):
	(a, b) = map(int, stdin.readline().split())
	(a, b) = (a - 1, b - 1)
	if d.get(a) == None:
		d[a] = []
	if d.get(b) == None:
		d[b] = []
	d[a].append(b)
	d[b].append(a)
(part1, part2) = bfs(d)
print(part1 * part2 - n + 1)


import math
import random
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
import threading
from collections import defaultdict
threading.stack_size(10 ** 8)
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
sys.setrecursionlimit(300000)
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')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class TreeNode:

	def __init__(self, k, v):
		self.key = k
		self.value = v
		self.left = None
		self.right = None
		self.parent = None
		self.height = 1
		self.num_left = 1
		self.num_total = 1

class AvlTree:

	def __init__(self):
		self._tree = None

	def add(self, k, v):
		if not self._tree:
			self._tree = TreeNode(k, v)
			return
		node = self._add(k, v)
		if node:
			self._rebalance(node)

	def _add(self, k, v):
		node = self._tree
		while node:
			if k < node.key:
				if node.left:
					node = node.left
				else:
					node.left = TreeNode(k, v)
					node.left.parent = node
					return node.left
			elif node.key < k:
				if node.right:
					node = node.right
				else:
					node.right = TreeNode(k, v)
					node.right.parent = node
					return node.right
			else:
				node.value = v
				return

	@staticmethod
	def get_height(x):
		return x.height if x else 0

	@staticmethod
	def get_num_total(x):
		return x.num_total if x else 0

	def _rebalance(self, node):
		n = node
		while n:
			lh = self.get_height(n.left)
			rh = self.get_height(n.right)
			n.height = max(lh, rh) + 1
			balance_factor = lh - rh
			n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
			n.num_left = 1 + self.get_num_total(n.left)
			if balance_factor > 1:
				if self.get_height(n.left.left) < self.get_height(n.left.right):
					self._rotate_left(n.left)
				self._rotate_right(n)
			elif balance_factor < -1:
				if self.get_height(n.right.right) < self.get_height(n.right.left):
					self._rotate_right(n.right)
				self._rotate_left(n)
			else:
				n = n.parent

	def _remove_one(self, node):
		replacement = node.left or node.right
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = replacement
			else:
				node.parent.right = replacement
			replacement.parent = node.parent
			node.parent = None
		else:
			self._tree = replacement
			replacement.parent = None
		node.left = None
		node.right = None
		node.parent = None
		self._rebalance(replacement)

	def _remove_leaf(self, node):
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = None
			else:
				node.parent.right = None
			self._rebalance(node.parent)
		else:
			self._tree = None
		node.parent = None
		node.left = None
		node.right = None

	def remove(self, k):
		node = self._get_node(k)
		if not node:
			return
		if AvlTree._is_leaf(node):
			self._remove_leaf(node)
			return
		if node.left and node.right:
			nxt = AvlTree._get_next(node)
			node.key = nxt.key
			node.value = nxt.value
			if self._is_leaf(nxt):
				self._remove_leaf(nxt)
			else:
				self._remove_one(nxt)
			self._rebalance(node)
		else:
			self._remove_one(node)

	def get(self, k):
		node = self._get_node(k)
		return node.value if node else -1

	def _get_node(self, k):
		if not self._tree:
			return None
		node = self._tree
		while node:
			if k < node.key:
				node = node.left
			elif node.key < k:
				node = node.right
			else:
				return node
		return None

	def get_at(self, pos):
		x = pos + 1
		node = self._tree
		while node:
			if x < node.num_left:
				node = node.left
			elif node.num_left < x:
				x -= node.num_left
				node = node.right
			else:
				return (node.key, node.value)
		raise IndexError('Out of ranges')

	@staticmethod
	def _is_left(node):
		return node.parent.left and node.parent.left == node

	@staticmethod
	def _is_leaf(node):
		return node.left is None and node.right is None

	def _rotate_right(self, node):
		if not node.parent:
			self._tree = node.left
			node.left.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.left
			node.left.parent = node.parent
		else:
			node.parent.right = node.left
			node.left.parent = node.parent
		bk = node.left.right
		node.left.right = node
		node.parent = node.left
		node.left = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	def _rotate_left(self, node):
		if not node.parent:
			self._tree = node.right
			node.right.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.right
			node.right.parent = node.parent
		else:
			node.parent.right = node.right
			node.right.parent = node.parent
		bk = node.right.left
		node.right.left = node
		node.parent = node.right
		node.right = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	@staticmethod
	def _get_next(node):
		if not node.right:
			return node.parent
		n = node.right
		while n.left:
			n = n.left
		return n

class SegmentTree1:

	def __init__(self, data, default=2 ** 51, func=lambda a, b: a & b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] < key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def binary(x, length):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] >= k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater

def main():
	for _ in range(1):
		n = int(input())
		d = {}
		for i in range(n - 1):
			(a, b) = map(int, input().split())
			if a not in d:
				d[a] = [b]
			else:
				d[a] += [b]
			if b not in d:
				d[b] = [a]
			else:
				d[b] += [a]
		color = [-1] * n

		def dfs(n, col):
			color[n - 1] = col
			for child in d[n]:
				if color[child - 1] == -1:
					dfs(child, col ^ 1)
		dfs(1, 1)
		ans = color.count(0) * color.count(1) - n + 1
		print(ans)
t = threading.Thread(target=main)
t.start()
t.join()


def main():
	n = int(input())
	adj_list = {i: [] for i in range(n + 1)[1:]}
	for i in range(n - 1):
		(u, v) = [int(inp) for inp in input().split()]
		adj_list[u].append(v)
		adj_list[v].append(u)
	visited = {i: False for i in range(n + 1)[1:]}
	node_type = {i: None for i in range(n + 1)[1:]}
	(node_1, node_2) = [0, 0]
	stack = []
	stack.append(1)
	visited[1] = True
	node_type[1] = 1
	node_1 += 1
	while stack:
		v = stack.pop()
		for nbr in adj_list[v]:
			if not visited[nbr]:
				visited[nbr] = True
				stack.append(nbr)
				if node_type[v] is 1:
					node_type[nbr] = 2
					node_2 += 1
				else:
					node_type[nbr] = 1
					node_1 += 1
	ans = 0
	for i in range(n + 1)[1:]:
		if node_type[i] is 1:
			ans += node_2 - len(adj_list[i])
		else:
			ans += node_1 - len(adj_list[i])
	print(ans // 2)
main()


import queue
n = int(input())
edges = [[] for _ in range(n + 5)]
for _ in range(n - 1):
	(u, v) = input().split()
	(u, v) = (int(u), int(v))
	edges[u].append(v)
	edges[v].append(u)
num_of_nodes = [0] * int(n + 5)
q = queue.Queue()
q.put((1, 0, -1))
while not q.empty():
	(node, level, father) = q.get()
	num_of_nodes[level] += 1
	for next_node in edges[node]:
		if not father == next_node:
			q.put((next_node, level + 1, node))
print(sum(num_of_nodes[::2]) * sum(num_of_nodes[1::2]) - n + 1)


from collections import *
import bisect
import heapq

def ri():
	return int(input())

def rl():
	return list(map(int, input().split()))

def dfs():
	to_visit = deque()
	to_visit.append(0)
	while to_visit:
		parent = to_visit.popleft()
		for child in graph[parent]:
			if colors[child] == -1:
				colors[child] = 1 - colors[parent]
				to_visit.append(child)
n = ri()
colors = [-1] * n
colors[0] = 1
graph = [[] for _ in range(n)]
for i in range(n - 1):
	(u, v) = rl()
	u -= 1
	v -= 1
	graph[u].append(v)
	graph[v].append(u)
dfs()
C = Counter(colors)
if n == 1:
	print('0')
	sys.exit()
ans = 0
for u in range(n):
	color = colors[u]
	degree = len(graph[u])
	ans += C[1 - color] - degree
print(ans // 2)


from sys import stdin, stdout, setrecursionlimit
import heapq
from math import gcd, ceil, sqrt
from collections import Counter, deque
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations
ii1 = lambda : int(stdin.readline().strip())
is1 = lambda : stdin.readline().strip()
iia = lambda : list(map(int, stdin.readline().strip().split()))
isa = lambda : stdin.readline().strip().split()
setrecursionlimit(100000)
mod = 1000000007

def partition(d):
	queue = deque([1, None])
	(zero, one, temp) = ([], [], [])
	seen = set()
	flag = 0
	while len(queue):
		cur = queue.popleft()
		if cur == None:
			if len(queue):
				queue.append(None)
			if flag == 0:
				zero.extend(temp)
			else:
				one.extend(temp)
			temp = []
			flag ^= 1
		elif cur not in seen:
			seen.add(cur)
			temp.append(cur)
			for neigh in d.get(cur, []):
				queue.append(neigh)
	return [set(one), set(zero)]
n = ii1()
d = {}
for i in range(n - 1):
	(a, b) = iia()
	d.setdefault(a, []).append(b)
	d.setdefault(b, []).append(a)
(zero, one) = partition(d)
res = 0
for i in zero:
	res += len(one) - len(d[i])
print(res)


n = int(input())
d = [[] for _ in range(n + 1)]
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	d[u] += [v]
	d[v] += [u]
l = [None] * (n + 1)
l[1] = 1
temp = [1]
while temp:
	top = temp.pop()
	for x in d[top]:
		if l[x] == None:
			l[x] = 1 - l[top]
			temp.append(x)
s = l.count(1)
print(s * (n - s) - n + 1)


count = [0] * 2
n = int(input())
graph = [[] for _ in range(n + 1)]
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	graph[u].append(v)
	graph[v].append(u)
stack = [(1, 0, 0)]
while stack:
	(node, parent, color) = stack.pop()
	count[color] += 1
	for i in graph[node]:
		if i != parent:
			stack.append((i, node, 1 - color))
print(count[0] * count[1] - (n - 1))


from collections import defaultdict

def dfs(g, n):
	(a1, a2) = (0, 0)
	q = []
	q.append((1, 1))
	visited = [True] * (n + 1)
	visited[1] = False
	a1 += 1
	while len(q) != 0:
		(c, v) = q.pop()
		for i in g[c]:
			if visited[i]:
				visited[i] = False
				if v == 1:
					a2 += 1
					q.append((i, 0))
				else:
					a1 += 1
					q.append((i, 1))
	return a1 * a2 - (n - 1)
g = defaultdict(list)
n = int(input())
for i in range(n - 1):
	(u, v) = map(int, input().split())
	g[u].append(v)
	g[v].append(u)
a = dfs(g, n)
print(a)


from collections import defaultdict
n = int(input())
bl = 0
wh = 0
di = {}
di = defaultdict(lambda : [], di)
di[0] = [1]
visited = [False] * n
col = {}
col = defaultdict(lambda : -1, col)
col[0] = 0
for i in range(n - 1):
	(x, y) = map(int, input().split())
	l = di[x]
	l.append(y)
	di[x] = l
	m = di[y]
	m.append(x)
	di[y] = m
visited = [False] * (n + 1)
visited[0] = True
stack = [0]
color = 0
cnt = 0
while True:
	if cnt >= n:
		break
	s = stack.pop()
	color = col[s]
	if visited[s] == True:
		for i in di[s]:
			if visited[i] == False:
				visited[i] = True
				bl = bl - color + 1
				stack.append(i)
				col[i] = 1 - color
				cnt = cnt + 1
print((n - bl) * bl - n + 1)


from collections import Counter as cntr
from math import inf

def cin():
	return map(int, input().split(' '))
n = int(input())
devil = {i: [] for i in range(n)}
for i in range(n - 1):
	(a, b) = cin()
	a -= 1
	b -= 1
	devil[a].append(b)
	devil[b].append(a)
visited = [False for i in range(n)]
q = [[0, 0]]
visited[0] = True
a = 0
b = 0
while q:
	(idx, color) = q.pop()
	if color:
		a += 1
	else:
		b += 1
	for v in devil[idx]:
		if visited[v] == False:
			visited[v] = True
			q.append([v, 1 - color])
print(a * b - n + 1)


class Graph:

	def __init__(self, v):
		self.v = v
		self.visited = [False for _ in range(v)]
		self.array = [[] for _ in range(v)]

	def addEdge(self, u, v):
		self.array[u].append(v)
		self.array[v].append(u)

def solve():
	n = int(input())
	g = Graph(n)
	for i in range(n - 1):
		(u, v) = list(map(int, input().split()))
		g.addEdge(u - 1, v - 1)
	queue = [0]
	g.visited[0] = True
	cnt = len(queue)
	nodes_odd = 0
	nodes_even = 1
	level = 0
	while queue:
		parent = queue.pop(0)
		g.visited[parent] = True
		cnt -= 1
		for i in range(len(g.array[parent])):
			if not g.visited[g.array[parent][i]]:
				queue.append(g.array[parent][i])
		if cnt == 0 and (not len(queue) == 0):
			level += 1
			if level % 2 == 0:
				nodes_even += len(queue)
			else:
				nodes_odd += len(queue)
			cnt = len(queue)
	ans = nodes_even * nodes_odd
	ans = ans - (n - 1)
	print(ans)
solve()


import collections
n = int(input(''))
graph = collections.defaultdict(list)
for i in range(n - 1):
	edge = list(map(int, input('').split(' ')))
	graph[edge[0]].append(edge[1])
	graph[edge[1]].append(edge[0])
visited = [False] * (n + 1)
red = 0
green = 0
color = 0
stack = [(1, 0)]
while stack:
	(node, color) = stack.pop(0)
	visited[node] = True
	if color == 0:
		red += 1
	else:
		green += 1
	for children in graph[node]:
		if visited[children] == False:
			stack.append((children, (color + 1) % 2))
print(red * green - (n - 1))


from collections import defaultdict
n = int(input())
graph = defaultdict(list)
for i in range(n - 1):
	edge = list(map(int, input().split(' ')))
	graph[edge[0]] += [edge[1]]
	graph[edge[1]] += [edge[0]]
cs = [0, 0]
size = 0
vs = [-1] * (n + 3)
ps = [-1] * (n + 3)
ss = [-1] * (n + 3)
vs[size] = 1
ps[size] = -1
ss[size] = 0
size += 1
while size > 0:
	v = vs[size - 1]
	prev = ps[size - 1]
	side = ss[size - 1]
	size -= 1
	cs[side] += 1
	for next in graph[v]:
		if next != prev:
			vs[size] = next
			ps[size] = v
			ss[size] = 1 - side
			size += 1
print(cs[0] * cs[1] - (n - 1))


from collections import deque

def bfs(graph, node, visited, color):
	q = deque()
	q.append(node)
	color[node] = 1
	visited[node] = True
	while q:
		u = q.popleft()
		for i in graph[u]:
			if not visited[i]:
				color[i] = 1 - color[u]
				visited[i] = True
				q.append(i)
			elif color[i] == color[u]:
				return False
	return color
t = int(input())
graph = []
for i in range(t + 1):
	graph.append([])
for _ in range(t - 1):
	(u, v) = [int(p) for p in input().split()]
	graph[u].append(v)
	graph[v].append(u)
c = [-1] * (t + 1)
vis = [False] * (t + 1)
for i in range(1, t + 1):
	if not vis[i]:
		bfs(graph, i, vis, c)
res = bfs(graph, 1, [False] * (t + 1), c)
s1 = 0
s2 = 0
for i in res:
	if i == 1:
		s1 += 1
	elif i == 0:
		s2 += 1
print(s1 * s2 - (t - 1))