Given a connected acyclic graph with n nodes and n-1 edges, count the pair of nodes that are at even distance(number of edges) from each other.
Example 1:
Input:
n = 3
graph = {{}, {2}, {1, 3}, {2}}
Output: 1
Explaination: Here there are three pairs {1,2},{1,3}
and {2,3} and only {1,3} has even distance between them.
i.e           1
             /
            2
           /
          3
Example 2:
Input:
n = 5
graph = {{}, {2,4}, {1,3}, {2}, {1,5}, {4}}
Output: 4
Explaination: There are four pairs {1,3},{1,5},{2,4}
and {3,5} which has even distance.
Your Task:
You don't need to read input or print anything. Your task is to complete the function countOfNodes() which takes the array graph[] (given as Adjacency list) and its size n as input parameters and returns the count of pair of nodes that are at even distance from each other
Expected Time Complexity: O(V+E)
Expected Auxiliary Space: O(V)
Constraints:
1 ≤ n ≤ 10^{4}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Graph algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

    def countOfNodes(self, graph,n):

        # code here

Solutions:
from collections import deque

def bfs(visit, graph, level, i):
	visit[i] = 1
	q = deque()
	q.append([1, 0])
	while q:
		t = q.popleft()
		u = t[0]
		lev = t[1]
		if lev not in level:
			level[lev] = [u]
		else:
			level[lev].append(u)
		for v in graph[u]:
			if visit[v] == 0:
				visit[v] = 1
				q.append([v, lev + 1])

class Solution:

	def countOfNodes(self, graph, n):
		visit = [0] * (n + 1)
		q = deque()
		q.append([1, 0])
		level = {}
		for i in range(1, n + 1):
			if visit[i] == 0:
				bfs(visit, graph, level, i)
		ans = 0
		odd = 0
		even = 0
		for i in level:
			if i % 2 == 0:
				even += len(level[i])
			else:
				odd += len(level[i])
		ans = even * (even - 1) // 2 + odd * (odd - 1) // 2
		return ans


from collections import deque

class Solution:

	def countOfNodes(self, graph, n):
		dist = [-1 for _ in range(n + 1)]
		dist[1] = 0
		q = deque()
		q.append((1, 0))
		while len(q) > 0:
			(node, d) = q.popleft()
			for nb in graph[node]:
				if dist[nb] == -1:
					dist[nb] = d + 1
					q.append((nb, d + 1))
		(odd, even) = (0, 0)
		for i in range(1, n + 1):
			if dist[i] % 2 == 1:
				odd += 1
			else:
				even += 1
		return odd * (odd - 1) // 2 + even * (even - 1) // 2


class Solution:

	def countOfNodes(self, graph, n):
		done = [False] * (n + 1)
		dino = [0] * (n + 1)
		dfs(graph, 1, dino, done, 0)
		even = 0
		odd = 0
		for i in range(1, n + 1):
			if dino[i] % 2 == 0:
				even += 1
			else:
				odd += 1
		ans = (even * (even - 1) + odd * (odd - 1)) // 2
		return ans

def dfs(graph, node, dino, done, c):
	if done[node]:
		return
	done[node] = True
	dino[node] = c
	for i in range(len(graph[node])):
		if not done[graph[node][i]]:
			dfs(graph, graph[node][i], dino, done, c + 1)


def dfs(graph, node, dist, vis, c):
	if vis[node]:
		return
	vis[node] = True
	dist[node] = c
	for i in range(len(graph[node])):
		if not vis[graph[node][i]]:
			dfs(graph, graph[node][i], dist, vis, c + 1)

def countOfNodess(graph, n):
	vis = [False] * (n + 1)
	dist = [0] * (n + 1)
	dfs(graph, 1, dist, vis, 0)
	even = 0
	odd = 0
	for i in range(1, n + 1):
		if dist[i] % 2 == 0:
			even += 1
		else:
			odd += 1
	ans = (even * (even - 1) + odd * (odd - 1)) // 2
	return ans

class Solution:

	def countOfNodes(self, graph, n):
		return countOfNodess(graph, n)


from collections import deque, defaultdict

class Solution:

	def countOfNodes(self, graph, n):
		q = deque()
		result = defaultdict(set)
		q.append((1, 0))
		visited = {i: False for i in graph.keys()}
		while q:
			current = q.popleft()
			visited[current[0]] = True
			oddNeighbors = graph[current[0]]
			result[(current[1] + 1) % 2].add(current[0])
			for o in oddNeighbors:
				if not visited[o]:
					q.append((o, current[1] + 1))
		ct = 0
		n1 = len(result[0])
		n2 = len(result[1])
		if n1 > 0:
			ct += n1 * (n1 - 1) // 2
		if n2 > 0:
			ct += n2 * (n2 - 1) // 2
		return ct


class Solution:

	def countOfNodes(self, graph, n):
		vis = set()
		dist = [0 for i in range(n + 1)]
		q = [1]
		while q:
			node = q.pop()
			distance = dist[node]
			vis.add(node)
			for adjnode in graph[node]:
				if adjnode not in vis:
					dist[adjnode] = distance + 1
					q.append(adjnode)
					vis.add(adjnode)
		(even, odd) = (0, 0)
		for i in range(1, n + 1):
			if dist[i] % 2 == 0:
				even += 1
			else:
				odd += 1
		return even * (even - 1) // 2 + odd * (odd - 1) // 2


class Solution:

	def countOfNodes(self, graph, n):
		queue = []
		depth = [99999999999999999 for i in range(n + 1)]
		visited = [0 for i in range(n + 1)]
		bfs = []
		queue.append(1)
		depth[1] = 0
		visited[1] = 1
		while len(queue) != 0:
			val = queue[0]
			bfs.append(val)
			queue.pop(0)
			for i in graph[val]:
				if visited[i] == 0:
					visited[i] = 1
					queue.append(i)
					depth[i] = depth[val] + 1
		even = 0
		odd = 0
		for i in depth:
			if i % 2 == 0:
				even += 1
			elif i % 2 != 0 and i != 99999999999999999:
				odd += 1
		ans = 0
		if odd > 1:
			ans += odd * (odd - 1) // 2
		if even > 1:
			ans += even * (even - 1) // 2
		return ans


def dfs(vis, graph, dis, node, d):
	vis[node] = True
	dis[node] = d
	for i in graph[node]:
		if vis[i] == False:
			dfs(vis, graph, dis, i, d + 1)

class Solution:

	def countOfNodes(self, graph, n):
		vis = [False] * (n + 1)
		dis = [-1] * (n + 1)
		for i in range(1, n + 1):
			if vis[i] == False:
				dfs(vis, graph, dis, i, 0)
		(even, odd) = (0, 0)
		for i in range(1, len(dis)):
			if dis[i] % 2 == 0:
				even += 1
			else:
				odd += 1
		return (even * (even - 1) + odd * (odd - 1)) // 2


class Solution:

	def countOfNodes(self, x, n):
		d = [0, 0]

		def f(i, p=-1, c=0):
			d[c] += 1
			for j in x[i]:
				if p != j:
					f(j, i, 1 - c)
		f(1)
		return max(0, d[0] * (d[0] - 1) // 2) + max(0, d[1] * (d[1] - 1) // 2)


class Solution:

	def countOfNodes(self, graph, n):
		distance = [0] * (n + 1)
		visit = [False] * (n + 1)
		q = []
		q.append(1)
		while q:
			node = q.pop(0)
			for i in graph[node]:
				if not visit[i]:
					distance[i] = distance[node] + 1
					visit[i] = True
					q.append(i)
		even = 0
		od = 0
		for i in distance:
			if i % 2 == 0:
				even += 1
			else:
				od += 1
		even -= 1
		return even * (even - 1) // 2 + od * (od - 1) // 2


class Solution:

	def countOfNodes(self, graph, n):
		visited = [False for i in range(n + 1)]
		distance = [0 for i in range(n + 1)]

		def dfs(v, grid, dist):
			visited[v] = grid
			for i in grid[v]:
				if visited[i] == False:
					distance[i] = dist + 1
					dfs(i, grid, dist + 1)
		dfs(1, graph, 0)
		even = 0
		odd = 0
		for i in distance:
			if i % 2 == 0:
				even += 1
			else:
				odd += 1
		even -= 1
		output = (even * (even - 1) + odd * (odd - 1)) // 2
		return output


class Solution:

	def countOfNodes(self, graph, n):
		q = []
		q.append([1, 0])
		vis = [False for i in range(n + 1)]
		evenc = 0
		oddc = 0
		while q:
			temp = q.pop(0)
			next_node = temp[0]
			vis[next_node] = True
			curr_dist = temp[1]
			if curr_dist % 2 == 0:
				evenc += 1
			else:
				oddc += 1
			for i in range(len(graph[next_node])):
				if not vis[graph[next_node][i]]:
					q.append([graph[next_node][i], curr_dist + 1])
					vis[graph[next_node][i]] = True
		evenc = evenc * (evenc - 1)
		oddc = oddc * (oddc - 1)
		return (evenc + oddc) // 2


from collections import Counter

def recur(u, adj, dist, d, vis):
	dist[u] = d
	vis[u] = 1
	for v in adj[u]:
		if not vis[v]:
			recur(v, adj, dist, d + 1, vis)

class Solution:

	def countOfNodes(self, adj, n):
		dist = [0] * (n + 1)
		vis = [0] * (n + 1)
		recur(1, adj, dist, 0, vis)
		odd = even = 0
		for v in dist[1:]:
			if v % 2:
				odd += 1
			else:
				even += 1
		ans = odd * (odd - 1) // 2 + even * (even - 1) // 2
		return ans


class Solution:

	def countOfNodes(self, graph, n):
		visit = [False] * (n + 1)
		result = [0] * (n + 1)
		self.dfs(graph, 1, result, visit, 0)
		(even, odd) = (0, 0)
		for i in range(1, n + 1):
			if result[i] % 2 == 0:
				even += 1
			else:
				odd += 1
		val = (even * (even - 1) + odd * (odd - 1)) // 2
		return val

	def dfs(self, graph, node, result, visit, c):
		if visit[node]:
			return
		visit[node] = True
		result[node] = c
		for i in range(len(graph[node])):
			if not visit[graph[node][i]]:
				self.dfs(graph, graph[node][i], result, visit, c + 1)


class Solution:

	def countOfNodes(self, graph, n):
		visited = [0] * (n + 1)
		(countEven, countOdd) = (0, 0)

		def dfs(i, level):
			nonlocal countEven
			if level % 2 == 0:
				countEven += 1
			visited[i] = 1
			for adj in graph[i]:
				if visited[adj] == 0:
					dfs(adj, level + 1)
		dfs(1, 0)
		countOdd = n - countEven
		return countOdd * (countOdd - 1) // 2 + countEven * (countEven - 1) // 2


class Solution:

	def dfs(self, dis, cur, count):
		dis[cur] = count
		for i in graph[cur]:
			if dis[i] == None:
				self.dfs(dis, i, count + 1)

	def countOfNodes(self, graph, n):
		dis = [None] * (n + 1)
		self.dfs(dis, 1, 0)
		even = 0
		odd = 0
		for i in range(1, n + 1):
			if dis[i] % 2 == 0:
				even += 1
			else:
				odd += 1
		ans = even * (even - 1) // 2 + odd * (odd - 1) // 2
		return ans


import collections

class Solution:

	def countOfNodes(self, graph, n):
		q = collections.deque()
		q.append((1, 0))
		visited = set()
		visited.add(1)
		even = set()
		odd = set()
		while q:
			(node, dist) = q.popleft()
			if node != 1:
				if dist % 2 == 0:
					even.add(node)
				else:
					odd.add(node)
			for nodes in graph[node]:
				if nodes not in visited:
					visited.add(nodes)
					q.append((nodes, dist + 1))
		pairs = 0
		pairs += len(even)
		L = len(even)
		for idx in range(1, L + 1):
			pairs += L - idx
		L = len(odd)
		for idx in range(1, L + 1):
			pairs += L - idx
		return pairs
		return 5


class Solution:

	def countOfNodes(self, graph, n):
		q = [1]
		l = [0] * (n + 1)
		visit = [False] * (n + 1)
		visit[1] = True
		level = 0
		while q:
			N = len(q)
			for _ in range(N):
				node = q.pop(0)
				l[node] = level
				visit[node] = True
				for nei in graph[node]:
					if not visit[nei]:
						q.append(nei)
						visit[nei] = True
			level += 1
		(o, e) = (0, 0)
		for i in range(1, n + 1):
			if l[i] % 2:
				o += 1
			else:
				e += 1
		return o * (o - 1) // 2 + e * (e - 1) // 2


class Solution:

	def countOfNodes(self, graph, n):
		red = set()
		blue = set()
		seen = set()

		def DFS(node, color):
			if node in seen:
				return
			if color == 0:
				red.add(node)
			else:
				blue.add(node)
			seen.add(node)
			color = (color + 1) % 2
			for child in graph[node]:
				DFS(child, color)
		DFS(1, 0)
		res = len(red)
		res = res * (res - 1) // 2
		res2 = len(blue)
		res2 = res2 * (res2 - 1) // 2
		return res + res2


from collections import deque

class Solution:

	def countOfNodes(self, graph, n):
		rb = [0] * 2
		c = 0
		q = deque([])
		vis = [False for _ in range(n + 1)]
		q.append(1)
		vis[1] = True
		while len(q):
			s = len(q)
			rb[c] += s
			c = 1 ^ c
			while s > 0:
				el = q.popleft()
				for nb in graph[el]:
					if vis[nb] == False:
						vis[nb] = True
						q.append(nb)
				s -= 1
		return rb[0] * (rb[0] - 1) // 2 + rb[1] * (rb[1] - 1) // 2


class Solution:

	def countOfNodes(self, graph, n):
		even = 1
		odd = 0
		q = []
		q.append(1)
		flag = True
		visited = {1}
		while q:
			p = []
			while q:
				poped = q.pop(0)
				for i in graph[poped]:
					if i not in visited:
						p.append(i)
						visited.add(i)
			if flag:
				odd += len(p)
				flag = False
			else:
				even += len(p)
				flag = True
			q = p
		return even * (even - 1) // 2 + odd * (odd - 1) // 2


class Solution:

	def dfs(self, graph, n, odd, even, iseven, u, vis):
		vis.add(u)
		if iseven:
			even[0] += 1
		else:
			odd[0] += 1
		for i in graph[u]:
			if i not in vis:
				self.dfs(graph, n, odd, even, not iseven, i, vis)

	def countOfNodes(self, graph, n):
		if n < 3:
			return 0
		odd = [0]
		even = [0]
		iseven = True
		vis = set()
		for i in range(1, n + 1):
			if i not in vis:
				self.dfs(graph, n, odd, even, iseven, i, vis)
		ans = 0
		if even[0] > 1:
			ans += (even[0] - 1) * even[0] // 2
		if odd[0] > 1:
			ans += (odd[0] - 1) * odd[0] // 2
		return ans


class Solution:

	def countOfNodes(self, graph, n):
		even = 1
		odd = 0
		queue = [1]
		vis = {1: True}
		flag = True
		while queue:
			tmp = []
			while queue:
				x = queue.pop(0)
				for adj in graph[x]:
					if adj in vis:
						continue
					vis[adj] = True
					tmp.append(adj)
			if flag:
				odd += len(tmp)
				flag = False
			else:
				even += len(tmp)
				flag = True
			queue = tmp
		return even * (even - 1) // 2 + odd * (odd - 1) // 2


class Solution:

	def countOfNodes(self, graph, n):
		(odd, even) = (0, 0)
		visited = set()
		dist = [0] * (n + 1)
		depthSearch(graph, 1, visited, dist, 1)
		for index in range(1, len(dist)):
			if dist[index] & 1:
				odd += 1
			else:
				even += 1
		return (odd * (odd - 1) + even * (even - 1)) // 2

def depthSearch(graph, curr, visited, dist, count):
	if curr in visited:
		return
	visited.add(curr)
	dist[curr] = count
	for node in graph[curr]:
		depthSearch(graph, node, visited, dist, count + 1)


class Solution:

	def countOfNodes(self, graph, n):
		q = []
		q.append(1)
		dist = [0] * n
		visited = [False] * (n + 1)
		while len(q) != 0:
			popped = q.pop(0)
			visited[popped] = True
			for neighbour in graph[popped]:
				if not visited[neighbour]:
					q.append(neighbour)
					dist[neighbour - 1] = dist[popped - 1] + 1
		even = 0
		odd = 0
		for i in dist:
			if i % 2 == 0:
				even += 1
			else:
				odd += 1
		return even * (even - 1) // 2 + odd * (odd - 1) // 2


class Solution:

	def countOfNodes(self, graph, n):

		def dfs(i, c):
			o = e = 0
			if i not in self.vis:
				self.vis.add(i)
				if (c + 1) % 2:
					o += 1
				else:
					e += 1
				for j in graph[i]:
					re = dfs(j, c + 1)
					e += re[1]
					o += re[0]
				return (o, e)
			return (0, 0)
		self.vis = set()
		ans = 0
		for i in graph:
			if i not in self.vis:
				re = dfs(i, -1)
				ans += re[0] * (re[0] - 1) // 2
				ans += re[1] * (re[1] - 1) // 2
		return ans


class Solution:

	def countOfNodes(self, graph, n):

		def dfs(node, count):
			if v[node]:
				return
			v[node] = True
			c[node] = count
			for i in graph[node]:
				if not v[i]:
					dfs(i, count + 1)
		(v, c) = ([False] * (n + 1), [0] * (n + 1))
		dfs(1, 0)
		(e, o) = (0, 0)
		for i in range(1, n + 1):
			if c[i] % 2:
				o += 1
			else:
				e += 1
		return (e * (e - 1) + o * (o - 1)) // 2


from collections import deque

class Solution:

	def countOfNodes(self, graph, n):
		vis = set()
		dist = [-1] * (n + 1)
		q = deque([1])
		dist[1] = 0
		vis.add(1)
		while q:
			x = q.popleft()
			for i in graph[x]:
				if i not in vis:
					dist[i] = dist[x] + 1
					vis.add(i)
					q.append(i)
		a = b = 0
		for i in range(1, len(dist)):
			x = dist[i]
			if x == -1:
				continue
			if x & 1 == 0:
				a += 1
			else:
				b += 1
		return (a * (a - 1) + b * (b - 1)) // 2


import numpy as np

class Solution:

	def countOfNodes(self, graph, n):
		visited = set()
		dist = [0] * len(graph)
		res = []
		q = [1]
		while q:
			node = q.pop(0)
			if node not in visited:
				res.append(node)
				visited.add(node)
			else:
				continue
			p = []
			for vois in graph[node]:
				if vois not in visited:
					p.append(vois)
					dist[vois - 1] = dist[node - 1] + 1
			q = p + q
		even_dist = np.asarray(dist) % 2
		even = even_dist.sum()
		odd = (-1 * (even_dist - 1)).sum()
		return even * (even - 1) // 2 + odd * (odd - 1) // 2


class Solution:

	def countOfNodes(self, graph, n):
		from collections import deque
		visited = set()
		level_stack = []
		stack = deque([(1, 0)])
		while len(stack) > 0:
			(node, level) = stack.pop()
			if node not in visited:
				visited.add(node)
				level_stack.append((node, level))
				for nbr in graph[node]:
					stack.append((nbr, level + 1))
		ans = 0
		odd_level = 0
		even_level = 0
		for i in range(len(level_stack)):
			if level_stack[i][1] % 2 == 0:
				even_level += 1
			else:
				odd_level += 1
		even_level -= 1
		odd_level -= 1
		ans = even_level * (even_level + 1) // 2 + odd_level * (odd_level + 1) // 2
		return ans


class Solution:

	def countOfNodes(self, graph, n):
		distance = [0] * (n + 1)
		visited = [False] * (n + 1)
		queue = []
		queue.append(1)
		distance[1] = 0
		visited[1] = True
		while queue:
			node = queue.pop(0)
			dist = distance[node]
			for neighbour in graph[node]:
				if not visited[neighbour]:
					queue.append(neighbour)
					visited[neighbour] = True
					distance[neighbour] = dist + 1
		even = odd = 0
		for i in range(1, n + 1):
			if distance[i] % 2 == 0:
				even += 1
			else:
				odd += 1
		return even * (even - 1) // 2 + odd * (odd - 1) // 2


class Solution:

	def dfs(self, node, graph, dist, vis, count):
		vis[node] = True
		dist[node] = count
		for it in graph[node]:
			if vis[it] == False:
				self.dfs(it, graph, dist, vis, count + 1)

	def countOfNodes(self, graph, n):
		dist = [0] * (n + 1)
		vis = [False] * (n + 1)
		self.dfs(1, graph, dist, vis, 0)
		countEven = 0
		countOdd = 0
		for i in range(1, len(dist)):
			if dist[i] % 2 == 0:
				countEven += 1
			else:
				countOdd += 1
		ans1 = countEven * (countEven - 1) // 2
		ans2 = countOdd * (countOdd - 1) // 2
		return ans1 + ans2


class Solution:

	def dfs(self, graph, v, visited, lvl, dist):
		if v not in visited:
			visited.add(v)
			dist[v] = lvl
			for nbr in graph[v]:
				if nbr not in visited:
					self.dfs(graph, nbr, visited, lvl + 1, dist)

	def countOfNodes(self, graph, n):
		visited = set()
		dist = [0] * (n + 1)
		self.dfs(graph, 1, visited, 0, dist)
		even = 0
		odd = 0
		for i in range(1, len(dist)):
			if dist[i] % 2 == 0:
				even += 1
			else:
				odd += 1
		return even * (even - 1) // 2 + odd * (odd - 1) // 2


class Solution:

	def countOfNodes(self, g, n):
		a = [0, 0]

		def fun(a, i, p, flag):
			if flag:
				a[0] += 1
			else:
				a[1] += 1
			for j in g[i]:
				if j != p:
					fun(a, j, i, flag ^ True)
		fun(a, 1, -1, True)
		ans = 0
		if a[0] > 1:
			ans += a[0] * (a[0] - 1) // 2
		if a[1] > 1:
			ans += a[1] * (a[1] - 1) // 2
		return ans


from collections import deque

class Solution:

	def countOfNodes(self, graph, n):
		(zeros, ones) = (0, 0)
		(q, visited) = (deque([(1, True)]), set())
		while q:
			(u, value) = q.popleft()
			visited.add(u)
			if value:
				ones += 1
			else:
				zeros += 1
			for v in graph[u]:
				if v not in visited:
					q.append((v, not value))
		return ones * (ones - 1) // 2 + zeros * (zeros - 1) // 2


class Solution:

	def dfs(self, s, p, d):
		self.dp[d] += 1
		for v in self.graph[s]:
			if v != p:
				self.dfs(v, s, 1 - d)

	def countOfNodes(self, graph, n):
		self.dp = [0, 0]
		self.n = n
		self.graph = graph
		self.dfs(1, -1, 0)
		return self.dp[0] * (self.dp[0] - 1) // 2 + self.dp[1] * (self.dp[1] - 1) // 2


class Solution:

	def countOfNodes(self, graph, n):
		visited = [False for i in range(len(graph))]
		arr = [-1 for i in range(len(graph))]

		def dfs(key, count):
			if visited[key - 1]:
				return
			if count % 2 == 0:
				arr[key - 1] = 1
			else:
				arr[key - 1] = 0
			visited[key - 1] = True
			for val in graph[key]:
				dfs(val, count + 1)
		dfs(1, 0)
		even = arr.count(1)
		odd = arr.count(0)
		evenfact = even * (even - 1) // 2
		oddfact = odd * (odd - 1) // 2
		return evenfact + oddfact


from collections import deque

class Solution:

	def countOfNodes(self, graph, n):
		Q = deque()
		vis = set()
		Q.append(1)
		vis.add(1)
		(odd, eve) = (0, 0)
		ans = 0
		x = 0
		while Q:
			x += 1
			l = len(Q)
			for k in range(l):
				temp = Q.popleft()
				if x % 2 == 0:
					ans += odd
					odd += 1
				else:
					ans += eve
					eve += 1
				for i in graph[temp]:
					if i not in vis:
						Q.append(i)
						vis.add(i)
		return ans


class Solution:

	def nc2(self, n):
		return (n - 1) * n // 2

	def countOfNodes(self, graph, n):
		visited = set()
		ans = 0
		for i in range(1, n + 1):
			odd = 0
			even = 0
			root = i
			if root in visited:
				continue
			q = [root]
			j = 0
			while q:
				que = []
				for node in q:
					if node not in visited:
						visited.add(node)
						if j % 2 == 0:
							even += 1
						else:
							odd += 1
						que += graph[node]
				q = que
				j += 1
			ans += self.nc2(even) + self.nc2(odd)
		return ans


class Solution:

	def countOfNodes(self, graph, n):
		queue = [(1, 0)]
		even = 0
		odd = 0
		ans = 0
		visited = defaultdict(bool)
		while queue:
			(v, h) = queue.pop(0)
			visited[v] = True
			if h % 2:
				ans += odd
				odd += 1
			else:
				ans += even
				even += 1
			for c in graph[v]:
				if not visited[c]:
					queue.append((c, h + 1))
		return ans


from collections import deque

class Solution:

	def countOfNodes(self, graph, n):
		ans = [0] * (n + 1)
		q = deque()
		q.append(1)
		visited = [False] * (n + 1)
		visited[1] = True
		while len(q) > 0:
			v = q.popleft()
			dist = ans[v]
			for nbr in graph[v]:
				if visited[nbr] == False:
					q.append(nbr)
					ans[nbr] = dist + 1
					visited[nbr] = True
		(e, o) = (0, 0)
		for i in range(1, n + 1):
			if ans[i] % 2 == 0:
				e += 1
			else:
				o += 1
		return e * (e - 1) // 2 + o * (o - 1) // 2


class Solution:

	def countOfNodes(self, graph, n):
		to_process = [1]
		processed = {1: False}
		evens = 1
		odds = 0
		while to_process:
			curr = to_process.pop()
			temp = graph[curr]
			for n in temp:
				if n in processed:
					continue
				if n not in to_process:
					to_process.append(n)
				processed[n] = not processed[curr]
				(odds, evens) = (odds + int(processed[n]), evens + int(not processed[n]))
		return evens * (evens - 1) // 2 + odds * (odds - 1) // 2


class Solution:

	def countOfNodes(self, graph, n):
		even = 0
		odd = -1
		queu = []
		vis = [0 for i in range(n + 1)]
		par = ['None' for i in range(n + 1)]
		par[1] = 'even'
		queu.append(1)
		vis[1] = 1
		while queu:
			temp = queu.pop(0)
			for i in graph[temp]:
				if vis[i] == 0:
					if par[temp] == 'even':
						par[i] = 'odd'
					if par[temp] == 'odd':
						par[i] = 'even'
					vis[i] = 1
					queu.append(i)
		for i in par:
			if i == 'even':
				even += 1
			else:
				odd += 1
		ans = even * (even - 1) // 2 + odd * (odd - 1) // 2
		return ans


class Solution:

	def countOfNodes(self, graph, n):
		q = []
		visited = [False] * (n + 1)
		dist = [-1] * (n + 1)
		q.append(1)
		visited[1] = True
		dist[1] = 0
		while q:
			x = q[0]
			q.pop(0)
			for ele in graph[x]:
				if visited[ele]:
					continue
				visited[ele] = True
				dist[ele] = dist[x] + 1
				q.append(ele)
		odd = 0
		even = 0
		for ele in dist:
			if ele == -1:
				continue
			if ele % 2 == 0:
				even += 1
			else:
				odd += 1
		ans = even * (even - 1) // 2 + odd * (odd - 1) // 2
		return ans