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

Difficulty: interview

Starter code:

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

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 deque

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


# Махмуд и Ехаб продолжают свои приключения! Каждый житель Злой Страны знает, что Доктор Зло любит двудольные графы, особенно деревья.
#
# Дерево — это связный граф без циклов. Двудольный граф — это граф, вершины которого можно разбить на 2 множества таким образом, что для любого ребра (u, v) графа вершины u и v лежат в разных множествах. Более формальное определение дерева и двудольного графа дано ниже.
#
# Доктор Зло дал Махмуду и Ехабу дерево, состоящее из n рёбер и сказал добавлять рёбра таким образом, чтобы граф оставался двудольным, а также в нём не было петель и кратных рёбер. Какое максимальное число рёбер они могут добавить?
# Входные данные
#
# В первой строке дано целое число n — число вершин в дереве (1 ≤ n ≤ 105).
#
# В следующих n - 1 строках содержатся пары целых чисел u и v (1 ≤ u, v ≤ n, u ≠ v) — описание рёбер дерева.
#
# Гарантируется, что заданный граф является деревом.
# Выходные данные
#
# Выведите одно число — максимальное число рёбер, которые Махмуд и Ехаб могут добавить в граф.
# python3
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)


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)

#!/usr/bin/env python3


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])
        # print(n, out)

assert out % 2 == 0
print(out // 2)



n = int(input())
tr = {}
for i in range(1,n+1):
	tm = []
	tr[i] = tm

for i in range(n-1):
	x,y = list(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)


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


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

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)

#!/usr/bin/env python3
# encoding: utf-8



#----------
# Constants
#----------
LEFT = 0
RIGHT = 1



#----------
# Functions
#----------

# Reads a string from stdin, splits it by space chars, converts each
# substring to int, adds it to a list and returns the list as a result.
def get_ints():
    return [ int(n) for n in input().split() ]



#----------
# Execution start point
#----------

def __starting_point():
    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)

__starting_point()

n=int(input())
l=[0]*n
d={}
d=[[]for _ in range(n)]
for _ in range(n-1):
  a,b=list(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)


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=list(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)


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

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].append(b-1);d[b-1].append(a-1)
while c:
  x=c.pop()
  for y in d[x]:
    if not l[y]:
      c.append(y);l[y]=-1*l[x]
r=l.count(1);print(r*(n-r)-n+1)

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


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


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)
#print(inp)
visited1, visited2 = [0] + [0] * n, [0] + [0] * n
bfs([1])
print(sum(visited1) * sum(visited2) - (n - 1))

"""
6
2 1
3 1
4 1
5 2
2 6
"""


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)
#print(inp)
visited1, visited2 = [0] + [0] * n, [0] + [0] * n
bfs([1])
print(sum(visited1) * sum(visited2) - (n - 1))

"""
6
2 1
3 1
4 1
5 2
2 6
"""


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