The director of your college is planning to send 2 people to the ICPC regionals. He wants them to be from different branches. You will be given a list of pairs of student ids. Each pair is made of students from the same branch. Determine how many pairs of students from different branches they can choose from.
Example 1:
Input:
N=5
P=3
pairs[]={{0,1},
         {2,3},
         {0,4}}
Output:
6
Explanation:
Their are total five studets 0,1,2,3,4.
Students [0,1,4] are from same bracnh while 
[2,3] are from a different one.So we can choose
different pairs like: [0,2],[0,3],[1,2],[1,3],
[4,2],[4,3]
 
Example 2:
Input:
N=4 
P=1
pairs[]={{0,2}}
Output:
5
Explanation:
[0,1],[0,3],[2,1],[2,3] and [1,3] are all possible 
pairs because [0,2],[1] and [3] all belongs to 
different branches.
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function numberOfPairs() which takes the 2d array pairs[], its size P and an integer N representing total number of students as input parameters and returns the total number of pairs(as explianed in the question)..
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
 
Constraint:
1<=N<=10^{5}
1<=P<=10^{4}
0<=P[i][0],P[i][1]

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Graph algorithms

Data structures

Spanning trees

Starter code: from typing import List





from typing import List





class Solution:

    def numberOfPairs(self, a : List[int], pairs : List[List[int]]) -> int:

        # code here

        



Solutions:
from typing import List
from typing import List
from collections import deque

class Solution:

	def numberOfPairs(self, a: List[int], pairs: List[List[int]]) -> int:
		visit = [0] * a[0]
		adj = [[] for _ in range(a[0])]
		for i in pairs:
			adj[i[0]].append(i[1])
			adj[i[1]].append(i[0])

		def fun(u, c):
			visit[u] = 1
			q = deque()
			q.append(u)
			while q:
				t = q.popleft()
				c += 1
				for i in adj[t]:
					if visit[i] == 0:
						visit[i] = 1
						q.append(i)
			return c
		ans = 0
		for i in range(a[0]):
			if visit[i] == 0:
				c = fun(i, 0)
				ans += c * (a[0] - c)
		return ans // 2


from typing import List

class Solution:

	def find(self, x, parent):
		if x == parent[x]:
			return x
		return self.find(parent[x], parent)

	def union(self, a, b, parent, rank):
		xrep = self.find(a, parent)
		yrep = self.find(b, parent)
		if xrep == yrep:
			return
		if rank[xrep] < rank[yrep]:
			parent[xrep] = yrep
		elif rank[xrep] > rank[yrep]:
			parent[yrep] = xrep
		else:
			rank[xrep] += 1
			parent[yrep] = xrep

	def numberOfPairs(self, a: List[int], pairs: List[List[int]]) -> int:
		parent = [i for i in range(a[0])]
		rank = [0 for i in range(a[0])]
		for i in pairs:
			self.union(i[0], i[1], parent, rank)
		dic = {}
		for i in range(a[0]):
			p = self.find(i, parent)
			dic[p] = dic.get(p, 0) + 1
		ans = 0
		res = 0
		for i in dic:
			ans += res * dic[i]
			res += dic[i]
		return ans


from typing import List
from queue import deque

class Solution:

	def numberOfPairs(self, a: List[int], pairs: List[List[int]]) -> int:
		n = a[0]
		graph = [[] for i in range(n)]
		for p in pairs:
			graph[p[0]].append(p[1])
			graph[p[1]].append(p[0])
		visited = set()
		numberOfNodesInEachComponent = []
		for src in range(n):
			if src not in visited:
				queue = deque()
				queue.append(src)
				visited.add(src)
				numberOfNodes = 1
				while queue:
					x = queue.popleft()
					for i in graph[x]:
						if i not in visited:
							visited.add(i)
							queue.append(i)
							numberOfNodes += 1
				numberOfNodesInEachComponent.append(numberOfNodes)
		_sum = sum(numberOfNodesInEachComponent)
		ans = 0
		for i in numberOfNodesInEachComponent:
			_sum -= i
			ans += _sum * i
		return ans

class Solution2:

	def numberOfPairs(self, a: List[int], pairs: List[List[int]]) -> int:
		d = {}
		c = 0
		for i in pairs:
			if i[0] in d:
				d[i[1]] = d[i[0]]
				continue
			if i[1] in d:
				d[i[0]] = d[i[1]]
				continue
			c += 1
			d[i[0]] = c
			d[i[1]] = c
		count = [0] * a[0]
		for i in d.keys():
			count[d[i]] += 1
		ans = 1
		print(count)
		for i in count:
			if i != 0:
				ans *= i
		return ans


from typing import List
from typing import List

class Solution:

	def numberOfPairs(self, a: List[int], pairs: List[List[int]]) -> int:
		n = a[0]
		parent = [-1] * n

		def find(a):
			if parent[a] < 0:
				return a
			parent[a] = find(parent[a])
			return parent[a]

		def merge(a, b):
			nonlocal parent
			a = find(a)
			b = find(b)
			if a == b:
				return
			if parent[a] < parent[b]:
				parent[a] += parent[b]
				parent[b] = a
			else:
				parent[b] += parent[a]
				parent[a] = b
		for (i, j) in pairs:
			merge(i, j)
		branch = []
		for i in parent:
			if i < 0:
				branch.append(i)
		calc = branch[:]
		l = len(branch)
		for i in range(l - 2, -1, -1):
			calc[i] = calc[i] + calc[i + 1]
		ans = 0
		for i in range(0, l - 1):
			ans = ans + branch[i] * calc[i + 1]
		return ans


from typing import List
import collections

class Solution:

	def numberOfPairs(self, X: List[int], P: List[List[int]]) -> int:
		N = X[0]
		g = collections.defaultdict(set)
		for (a, b) in P:
			g[a].add(b)
			g[b].add(a)
		sz = []
		v = set()
		for n in range(N):
			if n not in v:
				sz.append(dfs(n, g, v))
		postfix_sum = [0] * len(sz)
		for i in range(len(sz) - 2, -1, -1):
			postfix_sum[i] = postfix_sum[i + 1] + sz[i + 1]
		ans = 0
		for i in range(len(sz)):
			ans += sz[i] * postfix_sum[i]
		return ans

def dfs(n, g, v):
	v.add(n)
	sz = 1
	for nei in g[n]:
		if nei not in v:
			v.add(nei)
			sz += dfs(nei, g, v)
	return sz


from typing import List
from typing import List

class Solution:

	def numberOfPairs(self, a: List[int], pairs: List[List[int]]) -> int:
		N = a[0]
		P = a[1]
		parent = [i for i in range(N)]
		size = [1] * N
		for i in range(P):
			x = pairs[i][0]
			y = pairs[i][1]
			parent1 = self.find(parent, x)
			parent2 = self.find(parent, y)
			if parent1 != parent2:
				(parent, size) = self.union(parent, size, x, y)
		from collections import Counter
		ans = 0
		par = [self.find(parent, i) for i in range(N)]
		c = Counter(par)
		for i in c:
			ans += (N - c[i]) * c[i]
		return ans // 2

	def union(self, parent, size, a, b):
		x = self.find(parent, a)
		y = self.find(parent, b)
		if x != y:
			if size[x] < size[y]:
				parent[x] = y
				size[y] = size[x] + size[y]
			else:
				parent[y] = x
				size[x] = size[x] + size[y]
		return (parent, size)

	def find(self, parent, a):
		while a != parent[a]:
			parent[a] = parent[parent[a]]
			a = parent[a]
		return a


from typing import List
from typing import List

class Solution:

	def find(self, p1, i, l, vi):
		p1.append(i)
		vi[i] = True
		for x in l[i]:
			if not vi[x]:
				self.find(p1, x, l, vi)

	def numberOfPairs(self, a: List[int], pairs: List[List[int]]) -> int:
		n = a[0]
		p = a[1]
		vi = [False] * n
		l = []
		for i in range(n):
			l.append([])
		for x in pairs:
			l[x[0]].append(x[1])
			l[x[1]].append(x[0])
		an = []
		for i in range(n):
			if not vi[i]:
				p1 = []
				self.find(p1, i, l, vi)
				an.append(len(p1))
		ans = 0
		s = 0
		for i in range(1, len(an)):
			s += an[i]
		pr = [-1] * len(an)
		pr[0] = s
		ans = pr[0] * an[0]
		for i in range(1, len(an) - 1):
			pr[i] = pr[i - 1] - an[i]
			ans += pr[i] * an[i]
		return ans


from typing import List
from typing import List

class Solution:

	def parent(self, x, par):
		if par[x] == x:
			return x
		par[x] = self.parent(par[x], par)
		return par[x]

	def union(self, a, b, par, rank):
		x = self.parent(a, par)
		y = self.parent(b, par)
		if x == y:
			return
		if x < y:
			par[x] = y
		elif x > y:
			par[y] = x
		else:
			par[y] = x
			rank[x] += 1
		return

	def numberOfPairs(self, a: List[int], pairs: List[List[int]]) -> int:
		parent = [i for i in range(a[0])]
		rank = [1 for i in range(a[0])]
		for i in range(a[1]):
			self.union(pairs[i][0], pairs[i][1], parent, rank)
		dec = {}
		for i in range(a[0]):
			parent[i] = self.parent(i, parent)
			if dec.get(parent[i]):
				dec[parent[i]] += 1
			else:
				dec[parent[i]] = 1
		ans = 0
		sm = 0
		for i in dec:
			ans += dec[i] * sm
			sm += dec[i]
		return ans

class IntArray:

	def __init__(self) -> None:
		pass

	def Input(self, n):
		arr = [int(i) for i in input().strip().split()]
		return arr

	def Print(self, arr):
		for i in arr:
			print(i, end=' ')
		print()

class IntMatrix:

	def __init__(self) -> None:
		pass

	def Input(self, n, m):
		matrix = []
		for _ in range(n):
			matrix.append([int(i) for i in input().strip().split()])
		return matrix

	def Print(self, arr):
		for i in arr:
			for j in i:
				print(j, end=' ')
			print()
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		a = IntArray().Input(2)
		pairs = IntMatrix().Input(a[1], a[1])
		obj = Solution()
		res = obj.numberOfPairs(a, pairs)
		print(res)


from typing import List
from typing import List

class Solution:

	def numberOfPairs(self, a: List[int], pairs: List[List[int]]) -> int:
		n = a[0]
		p = a[1]
		parent = [i for i in range(n)]
		rank = [0] * n

		def findp(node):
			if parent[node] == node:
				return node
			parent[node] = findp(parent[node])
			return parent[node]

		def union(x, y):
			if x != y:
				xp = findp(x)
				yp = findp(y)
				if rank[xp] > rank[yp]:
					parent[yp] = xp
				elif rank[xp] < rank[yp]:
					parent[xp] = yp
				else:
					parent[xp] = yp
					rank[yp] += 1
		for i in range(p):
			union(pairs[i][0], pairs[i][1])
		for i in range(n):
			if parent[i] != i:
				parent[i] = findp(i)
		parent
		res = {}
		while parent:
			curr = parent.pop()
			if curr in res:
				res[curr] += 1
			else:
				res[curr] = 1
		ans = []
		for key in res:
			ans.append(res[key])
		tsum = 0
		csumm = sum(ans)
		for i in range(len(ans) - 1):
			csumm -= ans[i]
			tsum += ans[i] * csumm
		return tsum
		return 1

class IntArray:

	def __init__(self) -> None:
		pass

	def Input(self, n):
		arr = [int(i) for i in input().strip().split()]
		return arr

	def Print(self, arr):
		for i in arr:
			print(i, end=' ')
		print()

class IntMatrix:

	def __init__(self) -> None:
		pass

	def Input(self, n, m):
		matrix = []
		for _ in range(n):
			matrix.append([int(i) for i in input().strip().split()])
		return matrix

	def Print(self, arr):
		for i in arr:
			for j in i:
				print(j, end=' ')
			print()
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		a = IntArray().Input(2)
		pairs = IntMatrix().Input(a[1], a[1])
		obj = Solution()
		res = obj.numberOfPairs(a, pairs)
		print(res)


from typing import List
from typing import List

class Solution:

	def solve(self, i, visited, adj, count):
		visited[i] = True
		count[0] += 1
		for j in adj[i]:
			if not visited[j]:
				self.solve(j, visited, adj, count)

	def numberOfPairs(self, a: List[int], pairs: List[List[int]]) -> int:
		adj = [[] for i in range(a[0])]
		for i in range(len(pairs)):
			adj[pairs[i][0]].append(pairs[i][1])
			adj[pairs[i][1]].append(pairs[i][0])
		visited = [False for i in range(a[0])]
		arr = []
		sumi = 0
		for i in range(a[0]):
			if not visited[i]:
				count = [0]
				self.solve(i, visited, adj, count)
				arr.append(count[0])
				sumi += arr[-1]
		res = 0
		for i in range(len(arr)):
			res += arr[i] * (sumi - arr[i])
			sumi -= arr[i]
		return res

class IntArray:

	def __init__(self) -> None:
		pass

	def Input(self, n):
		arr = [int(i) for i in input().strip().split()]
		return arr

	def Print(self, arr):
		for i in arr:
			print(i, end=' ')
		print()

class IntMatrix:

	def __init__(self) -> None:
		pass

	def Input(self, n, m):
		matrix = []
		for _ in range(n):
			matrix.append([int(i) for i in input().strip().split()])
		return matrix

	def Print(self, arr):
		for i in arr:
			for j in i:
				print(j, end=' ')
			print()
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		a = IntArray().Input(2)
		pairs = IntMatrix().Input(a[1], a[1])
		obj = Solution()
		res = obj.numberOfPairs(a, pairs)
		print(res)


class Solution:

	def __init__(self):
		self.num = 0

	def numberOfPairs(self, a, pairs) -> int:
		graph = {i: [] for i in range(a[0])}
		out = []
		for (p1, p2) in pairs:
			graph[p1].append(p2)
			graph[p2].append(p1)
		visit = [False for _ in range(a[0])]
		for i in range(a[0]):
			if visit[i] is False:
				self.num = 0
				self.dfs(i, graph, visit)
				out.append(self.num)
		ans = 0
		temp = 0
		a1 = [0] * len(out)
		for i in range(len(out)):
			a1[i] = temp
			temp += out[i]
		for i in range(len(out)):
			ans += a1[i] * out[i]
		return ans

	def dfs(self, i, graph, visit):
		visit[i] = True
		self.num += 1
		for ele in graph[i]:
			if visit[ele] is False:
				self.dfs(ele, graph, visit)


from typing import List
from typing import List

class Solution:

	def numberOfPairs(self, a: List[int], pairs: List[List[int]]) -> int:
		graph = {}
		(n, e) = (a[0], a[1])
		for i in range(n):
			graph[i] = [i]
		for i in pairs:
			(s, d) = i
			graph[s].append(d)
			graph[d].append(s)
		component = []
		visited = [False for i in range(n)]

		def dfs(v, graph):
			visited[v] = True
			component.append(v)
			for k in graph[v]:
				if visited[k] == False:
					dfs(k, graph)
		output = []
		cumulative = [0 for i in range(n)]
		for i in range(n):
			component = []
			if visited[i] == False:
				dfs(i, graph)
				output.append(len(component))
		n = len(output)
		cumulative = [0 for i in range(n)]
		cumulative[-1] = output[-1]
		for i in range(n - 2, -1, -1):
			cumulative[i] = cumulative[i + 1] + output[i]
		final = 0
		for i in range(n - 1):
			final += output[i] * cumulative[i + 1]
		return final


from typing import List
from typing import List

class Solution:

	def numberOfPairs(self, a: List[int], pairs: List[List[int]]) -> int:
		rank = [0] * a[0]
		parent = [i for i in range(a[0])]

		def get_parent(ele, parent):
			if parent[ele] == ele:
				return ele
			return get_parent(parent[ele], parent)

		def union(i, j, parent):
			pi = get_parent(i, parent)
			pj = get_parent(j, parent)
			if pi == i and pj == j:
				parent[i] = j
				rank[j] += 1
			elif rank[pi] > rank[pj]:
				parent[pj] = pi
				rank[pi] += 1
			else:
				parent[pi] = pj
				rank[pj] += 1
		for i in pairs:
			union(i[0], i[1], parent)
		res = 0
		count = [0] * a[0]
		for i in range(a[0]):
			count[get_parent(i, parent)] += 1
		for i in count:
			if i:
				res += i * (a[0] - i)
		return res // 2


from typing import List
from typing import List

class Solution:

	def numberOfPairs(self, a: List[int], pairs: List[List[int]]) -> int:
		(n, p) = a
		parent = [i for i in range(n)]
		for (x, y) in pairs:
			x_ = x
			y_ = y
			while x_ != parent[x_]:
				x_ = parent[x_]
			while y_ != parent[y_]:
				y_ = parent[y_]
			parent[y_] = x_
			parent[y] = x_
			parent[x] = x_
		for i in range(n):
			i_ = i
			while parent[i_] != i_:
				i_ = parent[i_]
			parent[i] = i_
		d = {}
		for i in range(n):
			d[parent[i]] = d.get(parent[i], 0) + 1
		d = list(d.values())
		n = len(d)
		s = sum(d) ** 2
		s_ = 0
		for i in range(n):
			s_ += d[i] * d[i]
		return (s - s_) // 2


from typing import List

def find(u, par):
	while par[u] != u:
		(u, par[u]) = (par[u], par[par[u]])
	return u

def union(ra, rb, szs, par):
	if szs[ra] > szs[rb]:
		(ra, rb) = (rb, ra)
	par[ra] = rb
	szs[rb] += szs[ra]

class Solution:

	def numberOfPairs(self, a: List[int], pairs: List[List[int]]) -> int:
		N = a[0]
		szs = [1] * N
		par = [i for i in range(N)]
		for (a, b) in pairs:
			ra = find(a, par)
			rb = find(b, par)
			if ra == rb:
				continue
			union(ra, rb, szs, par)
		grpsz = []
		for i in range(N):
			if par[i] == i:
				grpsz.append(szs[i])
		ans = 0
		for v in grpsz:
			ans += v * (N - v)
		ans //= 2
		return ans


from typing import List
from collections import deque
from typing import List

class Solution:

	def numberOfPairs(self, a: List[int], p: List[List[int]]) -> int:
		(n, m) = a
		ar = {i: [] for i in range(n)}
		ed = set()
		for i in p:
			ed.add(tuple(sorted(i)))
		for i in ed:
			ar[i[0]].append(i[1])
			ar[i[1]].append(i[0])
		v = [0] * n
		ans = []
		for i in range(n):
			if v[i] == 0:
				q = deque([i])
				c = 1
				v[i] = 1
				while len(q):
					k = q.popleft()
					for j in ar[k]:
						if v[j] == 0:
							v[j] = 1
							q.append(j)
							c += 1
				ans.append(c)
		k = 0
		l = list(ans)
		for i in range(1, len(l)):
			l[i] += l[i - 1]
		for i in range(len(ans)):
			k += ans[i] * (l[-1] - l[i])
		return k


from typing import List

class Solution:

	def numberOfPairs(self, a: List[int], pairs: List[List[int]]) -> int:
		(N, p) = a
		G = {i: [] for i in range(N)}
		for (a, b) in pairs:
			G[a].append(b)
			G[b].append(a)
		visited = [0] * N

		def dfs(node, visited):
			visited[node] = 1
			self.ans += 1
			for i in G[node]:
				if visited[i] == 0:
					dfs(i, visited)
			return self.ans
		cc = []
		for i in range(N):
			if visited[i] == 0:
				self.ans = 0
				dfs(i, visited)
				cc.append(self.ans)
		n = len(cc)
		t = N * (N - 1) / 2
		for i in range(n):
			t = t - cc[i] * (cc[i] - 1) / 2
		return int(t)


from typing import List
import sys
sys.setrecursionlimit(10 ** 5)

class Solution:

	def findPar(self, u, parent):
		if u == parent[u]:
			return u
		parent[u] = self.findPar(parent[u], parent)
		return parent[u]

	def union(self, u, v, parent):
		u = self.findPar(u, parent)
		v = self.findPar(v, parent)
		if u != v:
			parent[v] = u
		return

	def numberOfPairs(self, a: List[int], pairs: List[List[int]]) -> int:
		parent = [i for i in range(a[0])]
		for (u, v) in pairs:
			self.union(u, v, parent)
		res = 0
		count = [0 for i in range(a[0])]
		for i in range(a[0]):
			pk = self.findPar(i, parent)
			count[pk] += 1
		return sum([i * (a[0] - i) for i in count]) // 2


from typing import List
from typing import List

class Solution:

	def numberOfPairs(self, a: List[int], pairs: List[List[int]]) -> int:
		rank = [0 for i in range(a[0])]
		par = [i for i in range(a[0])]

		def findPar(node):
			if par[node] == node:
				return node
			par[node] = findPar(par[node])
			return par[node]

		def union(u, v):
			if par[u] != par[v]:
				u = findPar(u)
				v = findPar(v)
				if rank[u] < rank[v]:
					par[u] = par[v]
				elif rank[u] > rank[v]:
					par[v] = par[u]
				else:
					par[v] = par[u]
					rank[u] += 1
		grps = [[] for _ in range(a[0])]
		for (u, v) in pairs:
			union(u, v)
		for u in range(a[0]):
			t1 = findPar(u)
			grps[t1].append(u)
		tot = a[0]
		res = 0
		for i in grps:
			tot -= len(i)
			res += len(i) * tot
		return res