You're researching friendships between groups of $n$ new college students where each student is distinctly numbered from $1$ to $n$. At the beginning of the semester, no student knew any other student; instead, they met and formed individual friendships as the semester went on. The friendships between students are:

Bidirectional. If student $\class{ML__boldsymbol}{\boldsymbol{a}}$ is friends with student $\boldsymbol{b}$, then student $\boldsymbol{b}$ is also friends with student $\class{ML__boldsymbol}{\boldsymbol{a}}$.
Transitive. If student $\class{ML__boldsymbol}{\boldsymbol{a}}$ is friends with student $\boldsymbol{b}$ and student $\boldsymbol{b}$ is friends with student $c$, then student $\class{ML__boldsymbol}{\boldsymbol{a}}$ is friends with student $c$. In other words, two students are considered to be friends even if they are only indirectly linked through a network of mutual (i.e., directly connected) friends. 

The purpose of your research is to find the maximum total value of a group's friendships, denoted by $total$. Each time a direct friendship forms between two students, you sum the number of friends that each of the $n$ students has and add the sum to $total$. 

You are given $\textit{q}$ queries, where each query is in the form of an unordered list of $m$ distinct direct friendships between $n$ students. For each query, find the maximum value of $total$ among all possible orderings of formed friendships and print it on a new line.

Input Format

The first line contains an integer, $\textit{q}$, denoting the number of queries. The subsequent lines describe each query in the following format:

The first line contains two space-separated integers describing the respective values of $n$ (the number of students) and $m$ (the number of distinct direct friendships).
Each of the $m$ subsequent lines contains two space-separated integers describing the respective values of $\boldsymbol{x}$ and $y$ (where $x\neq y$) describing a friendship between student $\boldsymbol{x}$ and student $y$.

Constraints

$1\leq q\leq16$  
$1\leq n\leq10^5$   
$1\leq m\leq\text{min}(\frac{n\cdot(n-1)}{2},2\times10^5)$  

Output Format

For each query, print the maximum value of $total$ on a new line.

Sample Input 0
1
5 4
1 2
3 2
4 2
4 3

Sample Output 0
32

Explanation 0

The value of $total$ is maximal if the students form the $m=4$ direct friendships in the following order:

Students $1$ and $2$ become friends: 

We then sum the number of friends that each student has to get $1+1+0+0+0=2$.

Students $2$ and $\begin{array}{c}4\end{array}$ become friends: 

We then sum the number of friends that each student has to get $2+2+0+2+0=6$.

Students $3$ and $\begin{array}{c}4\end{array}$ become friends: 

We then sum the number of friends that each student has to get $3+3+3+3+0=12$.

Students $3$ and $2$ become friends: 

We then sum the number of friends that each student has to get $3+3+3+3+0=12$.

When we add the sums from each step, we get $total=2+6+12+12=32$. We then print $32$ on a new line.

Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Starter code:

Solutions:
def grow(n):
	res = 0
	for i in range(1, n):
		res += i * (i + 1)
	return res

def mark(x):
	z = x
	while z:
		z = z[0]
	if x is not z:
		x[0] = z
	return z

def mark2(x):
	z = x
	while z and type(z) == list:
		z = z[0]
	if x is not z:
		x[0] = z
	return z
T = int(input())
for t in range(T):
	(n, m) = map(int, input().split())
	work = [[] for i in range(n)]
	lost = 0
	for i in range(m):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		mu = mark(work[u])
		mv = mark(work[v])
		if mu is not mv:
			mu.append(mv)
		else:
			lost += 1
	no = 1
	dic = {}
	for i in range(n):
		z = mark2(work[i])
		if not z:
			z.append(no)
			z = no
			no += 1
			dic[z] = 1
		else:
			dic[z] += 1
	res = 0
	cur = 0
	for v in sorted(dic.values(), reverse=True):
		res += grow(v) + (v - 1) * cur
		cur += v * (v - 1)
	res += lost * cur
	print(res)


import sys

class UnionFind:

	def __init__(self):
		self.weights = {}
		self.parents = {}
		self.edges = {}
		self.rootlist = set()

	def __getitem__(self, object):
		if object not in self.parents:
			self.parents[object] = object
			self.weights[object] = 1
			self.edges[object] = 0
			self.rootlist.add(object)
			return object
		path = [object]
		root = self.parents[object]
		while root != path[-1]:
			path.append(root)
			root = self.parents[root]
		for ancestor in path:
			self.parents[ancestor] = root
		return root

	def __iter__(self):
		return iter(self.parents)

	def union(self, *objects):
		roots = [self[x] for x in objects]
		heaviest = max([(self.weights[r], r) for r in roots])[1]
		for r in roots:
			if r != heaviest:
				self.weights[heaviest] += self.weights[r]
				self.parents[r] = heaviest
				self.rootlist.remove(r)

	def union2(self, x, y):
		roots = [self[x], self[y]]
		if roots[0] == roots[1]:
			self.edges[roots[0]] += 1
			return
		heaviest = max([(self.weights[r], r) for r in roots])[1]
		for r in roots:
			if r != heaviest:
				self.weights[heaviest] += self.weights[r]
				self.edges[heaviest] += self.edges[r]
				self.parents[r] = heaviest
				self.rootlist.remove(r)

	def size(self, obj):
		return self.weights[self[obj]]
t = int(input().strip())
for a0 in range(t):
	total = 0
	finished_comp = 0
	sum_e = 0
	u = UnionFind()
	(n, m) = (int(i) for i in input().strip().split())
	for a1 in range(m):
		(x, y) = (int(i) for i in input().strip().split())
		u.union2(x, y)
	s = u.rootlist
	arr = sorted([(u.weights[i], u.edges[i]) for i in s], reverse=True)
	for (w, e) in arr:
		total += w * (w - 1) * (w + 1) // 3 + (w - 1) * finished_comp
		finished_comp += w * (w - 1)
		sum_e += e
	total += sum_e * finished_comp
	print(total)


from collections import deque, defaultdict
cache = deque()
res = []
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	link = defaultdict(list)
	for _ in range(m):
		(x, y) = map(int, input().split())
		link[x].append(y)
		link[y].append(x)
	newnode = [True] * (n + 1)
	cluster = []
	for i in range(1, n + 1):
		if newnode[i]:
			nodenum = 1
			cache.append(i)
			newnode[i] = False
			while cache:
				curr = cache.popleft()
				for j in link[curr]:
					if newnode[j]:
						cache.append(j)
						newnode[j] = False
						nodenum += 1
			if nodenum > 1:
				cluster.append(nodenum)
	cluster.sort(reverse=True)
	k = len(cluster)
	temp = sum(cluster) - k
	llm1 = tuple((l * (l - 1) for l in cluster))
	v = (m - temp) * sum(llm1)
	for i in range(k):
		temp -= cluster[i] - 1
		v += (cluster[i] + 1) * llm1[i] // 3 + temp * llm1[i]
	res.append(v)
print(*res, sep='\n')


import sys
from collections import defaultdict, deque, Counter
from math import factorial, ceil
from time import time
from fractions import gcd
from itertools import product, combinations
DEBUG = False

def P(*args, **kwargs):
	if DEBUG:
		print('\x1b[1;31m' + '\n'.join([str(x) for x in args] + ['{}: {}'.format(k, v) for (k, v) in kwargs.items()]) + '\x1b[0m')
sys.setrecursionlimit(1000000)

def bfs(i, j, adj_list, vis, groups):
	vis.add(j)
	q = deque([j])
	ret = 0
	while len(q) > 0:
		cur = q.popleft()
		groups[cur] = i
		ret += 1
		for neigh in adj_list[cur]:
			if neigh not in vis:
				vis.add(neigh)
				q.append(neigh)
	return ret
q = int(input().strip())
for _ in range(q):
	(n, m) = map(int, input().strip().split())
	adj_list = defaultdict(set)
	vis = set()
	groups = {}
	sizes = {}
	size_e = defaultdict(int)
	edges = []
	ans = 0
	for __ in range(m):
		(x, y) = map(int, input().strip().split())
		edges.append((x, y))
		adj_list[x].add(y)
		adj_list[y].add(x)
	for i in range(1, n + 1):
		if i not in vis:
			size = bfs(i, i, adj_list, vis, groups)
			if size > 1:
				sizes[i] = size
	tmp = 0
	for v in reversed(sorted(sizes.values())):
		ans += (v + 1) * v * (v - 1) // 3 + (v - 1) * tmp
		tmp += v * (v - 1)
	P(ans, tmp)
	for (x, y) in edges:
		size_e[groups[x]] += 1
	old_ans = ans
	for (k, v) in size_e.items():
		ans += (v - sizes[k] + 1) * tmp
	print(ans)


class node:

	def __init__(self, id):
		self.isRoot = True
		self.parent = None
		self.friendship = 0
		self.friends = set()
		self.size = 1
		self.id = id

	def findRoot(self):
		c = self
		while not c.isRoot:
			c = c.parent
		compress = self
		while not compress.isRoot:
			next = compress.parent
			compress.parent = c
			compress = next
		return c

	def getFriendship(self):
		return self.friendship

	def getSize(self):
		return self.size

	def getExtraConnection(self):
		return self.friendship - self.size + 1

	def union(self, other):
		if other in self.friends:
			return
		self_root = self.findRoot()
		other_root = other.findRoot()
		self.friends.add(other)
		other.friends.add(self)
		if self_root.size < other_root.size:
			aux = self_root
			self_root = other_root
			other_root = aux
		if self_root == other_root:
			self_root.friendship += 1
		else:
			other_root.isRoot = False
			other_root.parent = self_root
			self_root.size += other_root.size
			self_root.friendship += other_root.friendship + 1

def getResult(nodes):
	roots = sorted([n for n in nodes if n.isRoot and n.size > 1], key=node.getSize, reverse=True)
	result = 0
	lastconnections = 0
	for r in roots:
		s = r.getSize() - 1
		result = result + lastconnections * s + s * (s + 1) // 2 + s * (s + 1) * (2 * s + 1) // 6
		lastconnections = lastconnections + s * (s + 1)
	duplicateLinks = sum([r.getExtraConnection() for r in roots])
	result = result + duplicateLinks * lastconnections
	return result
t = int(input().strip())
for a0 in range(t):
	(n, m) = input().strip().split(' ')
	(n, m) = [int(n), int(m)]
	nodes = [node(i) for i in range(n)]
	for a1 in range(m):
		(x, y) = input().strip().split(' ')
		(x, y) = [int(x), int(y)]
		nodes[x - 1].union(nodes[y - 1])
	print(getResult(nodes))


q = int(input())

def find(a, parents):
	if parents[a] != a:
		parents[a] = find(parents[a], parents)
	return parents[a]

def join(a, b, parents, ranks, sizes):
	aRoot = find(a, parents)
	bRoot = find(b, parents)
	if aRoot == bRoot:
		return
	if ranks[aRoot] > ranks[bRoot]:
		parents[bRoot] = aRoot
		sizes[aRoot] += sizes[bRoot]
	else:
		parents[aRoot] = bRoot
		sizes[bRoot] += sizes[aRoot]
	if ranks[aRoot] == ranks[bRoot]:
		ranks[bRoot] += 1
for query in range(q):
	(n, m) = map(int, input().split())
	parents = list(range(n))
	ranks = [0] * n
	sizes = [1] * n
	visited = [False] * n
	for friend in range(m):
		(a, b) = map(int, input().split())
		join(a - 1, b - 1, parents, ranks, sizes)
	cliqueSizes = []
	for i in range(n):
		root = find(i, parents)
		if not visited[root]:
			visited[root] = True
			cliqueSizes += [sizes[root]]
	cliqueSizes.sort(reverse=True)
	total = 0
	before = 0
	atTheEnd = m
	for k in cliqueSizes:
		total += before * (k - 1)
		total += (k * k * k - k) // 3
		before += k * (k - 1)
		atTheEnd -= k - 1
	total += before * atTheEnd
	print(total)


def find(group_nrs, x):
	a = x
	while group_nrs[a] != a:
		a = group_nrs[a]
	return a
q = int(input())
for _ in range(q):
	(n, m) = map(int, input().strip().split())
	ships = set()
	for i in range(m):
		(x, y) = map(int, input().strip().split())
		ships.add((x, y))
	group_nrs = list(range(n + 1))
	for (x, y) in sorted(ships):
		if y > x:
			(x, y) = (y, x)
		group_nrs[find(group_nrs, x)] = find(group_nrs, y)
	groups = {}
	for i in range(1, n + 1):
		g = find(group_nrs, i)
		if g not in groups:
			groups[g] = set()
		groups[g].add(i)
	groups = sorted(groups.values(), key=lambda g: len(g), reverse=True)
	nr_redundant = len(ships) - sum((len(group) - 1 for group in groups))
	total = 0
	nr_friendships = 0
	for group in groups:
		if len(group) == 1:
			break
		for done in range(2, len(group) + 1):
			nr_friendships += 2 * (done - 1)
			total += nr_friendships
	total += nr_redundant * nr_friendships
	print(total)


import sys

def strongly_connected_components(vertices, edges):
	identified = set()
	stack = []
	index = {}
	boundaries = []
	for v in vertices:
		if v not in index:
			to_do = [('VISIT', v)]
			while to_do:
				(operation_type, v) = to_do.pop()
				if operation_type == 'VISIT':
					index[v] = len(stack)
					stack.append(v)
					boundaries.append(index[v])
					to_do.append(('POSTVISIT', v))
					to_do.extend(reversed([('VISITEDGE', w) for w in edges[v]]))
				elif operation_type == 'VISITEDGE':
					if v not in index:
						to_do.append(('VISIT', v))
					elif v not in identified:
						while index[v] < boundaries[-1]:
							boundaries.pop()
				elif boundaries[-1] == index[v]:
					boundaries.pop()
					scc = set(stack[index[v]:])
					del stack[index[v]:]
					identified.update(scc)
					yield scc

def val(n, cur_total):
	return (n - 1) * n * (n + 1) // 3 + cur_total * (n - 1)

def max_value(n, links):
	vertices = [i for i in range(1, n + 1)]
	edges = {}
	for (v1, v2) in links:
		edges[v1] = edges.get(v1, []) + [v2]
		edges[v2] = edges.get(v2, []) + [v1]
	for v in vertices:
		if v not in edges:
			edges[v] = []
	sccs = strongly_connected_components(vertices, edges)
	scc_sizes = sorted([len(scc) for scc in sccs], reverse=True)
	result = 0
	cur_friend_total = 0
	extra_links = len(links)
	for size in scc_sizes:
		extra_links -= size - 1
		result += val(size, cur_friend_total)
		cur_friend_total += size * (size - 1)
	result += extra_links * cur_friend_total
	return result
t = int(input().strip())
for a0 in range(t):
	(n, m) = input().strip().split(' ')
	(n, m) = [int(n), int(m)]
	links = []
	for a1 in range(m):
		(x, y) = input().strip().split(' ')
		(x, y) = [int(x), int(y)]
		links.append([x, y])
	print(max_value(n, links))


(fr, h) = ([], [])

def pre(x):
	global fr
	if x != fr[x]:
		fr[x] = pre(fr[x])
	return fr[x]

def union(x, y):
	global fr, h
	(x, y) = (pre(x), pre(y))
	if x != y:
		if h[x] < h[y]:
			(x, y) = (y, x)
		fr[y] = x
		if h[x] == h[y]:
			h[x] += 1

def calc():
	cnt = {}
	global fr, h
	(n, m) = map(int, input().split())
	(fr, h) = (list(range(n)), [0] * n)
	for _ in range(m):
		(x, y) = map(int, input().split())
		union(x - 1, y - 1)
	for t in range(n):
		fr[t] = pre(t)
	for i in range(n):
		cnt[fr[i]] = cnt.setdefault(fr[i], 0) + 1
	(total, cur, ans) = (0, 0, sorted([cnt[key] for key in cnt if cnt[key] > 1], reverse=True))
	for x in ans:
		for i in range(2, x + 1):
			cur += i * 2 - 2
			total += cur
	print(total + cur * (m - sum(ans) + len(ans)))
for _ in range(int(input())):
	calc()


class Disjoints:

	def __init__(self, N):
		self.parents = [None for i in range(N)]
		self.ranks = [0 for i in range(N)]
		self.cyclingarcs = 0

	def makeset(self, x):
		self.parents[x] = x

	def find(self, x):
		if self.parents[x] != None and self.parents[x] != x:
			self.parents[x] = self.find(self.parents[x])
		return self.parents[x]

	def union(self, x, y):
		if self.parents[x] == None:
			self.makeset(x)
		if self.parents[y] == None:
			self.makeset(y)
		xroot = self.find(x)
		yroot = self.find(y)
		if xroot != yroot:
			if self.ranks[xroot] <= self.ranks[yroot]:
				self.parents[xroot] = yroot
				newroot = yroot
			else:
				self.parents[yroot] = xroot
				newroot = xroot
			if self.ranks[xroot] == self.ranks[yroot]:
				self.ranks[newroot] += 1
		else:
			self.cyclingarcs += 1

def sumn(n):
	return int(n * (n + 1) / 2)

def sumn2(n):
	return int(n * (n + 1) * (2 * n + 1) / 6)
T = int(input())
for t in range(T):
	(n, m) = map(int, input().split(' '))
	disjoints = Disjoints(n)
	for i in range(m):
		(x, y) = map(lambda c: int(c) - 1, input().split(' '))
		disjoints.union(x, y)
	ccs = {}
	for i in range(len(disjoints.parents)):
		root = disjoints.find(i)
		ccs[root] = ccs.setdefault(root, 0) + 1
	graphvalue = 0
	total = 0
	for cc in sorted(ccs.items(), key=lambda x: x[1], reverse=True):
		if cc[0] != None:
			total += sumn(cc[1] - 1) + sumn2(cc[1] - 1)
			total += graphvalue * (cc[1] - 1)
			graphvalue += cc[1] * (cc[1] - 1)
	total += disjoints.cyclingarcs * graphvalue
	print(total)


import sys

def sumN(n):
	return n * (n + 1) // 2

def sumN2(n):
	return n * (n + 1) * (2 * n + 1) // 6

def componentSizes(graph):
	visited = [False] * len(graph)
	componentSizes = []
	for (i, v) in enumerate(visited):
		if not v:
			componentSize = 0
			queue = [i]
			visited[i] = True
			while queue:
				j1 = queue.pop()
				componentSize += 1
				for j2 in graph[j1]:
					if not visited[j2]:
						visited[j2] = True
						queue.append(j2)
			componentSizes.append(componentSize)
	componentSizes.sort(key=lambda x: -x)
	return componentSizes

def edgesToGraph(nVerts, edges):
	graph = [[] for _ in range(nVerts)]
	for (v1, v2) in edges:
		graph[v1].append(v2)
		graph[v2].append(v1)
	return graph

def maxFriendValue(componentSizes, nEdges):
	total = 0
	for c in componentSizes:
		assemblyValue = sumN2(c) - sumN(c)
		edgesInSpanningTree = c - 1
		connectedValue = c * (c - 1)
		total += assemblyValue
		nEdges -= edgesInSpanningTree
		total += connectedValue * nEdges
	return total

def solution(nVerts, edges):
	nEdges = len(edges)
	edges = tuple(map(lambda E: tuple((v - 1 for v in E)), edges))
	graph = edgesToGraph(nVerts, edges)
	cSizes = componentSizes(graph)
	return maxFriendValue(cSizes, nEdges)
t = int(input().strip())
for a0 in range(t):
	(n, m) = input().strip().split(' ')
	(n, m) = [int(n), int(m)]
	edges = []
	for a1 in range(m):
		(x, y) = input().strip().split(' ')
		(x, y) = [int(x), int(y)]
		edges.append((x, y))
	print(solution(n, edges))


import sys

class Student:

	def __init__(self):
		self.root = self
		self.n = 1

	def get_root(self):
		if self.root != self:
			return self.root.get_root()
		else:
			return self
for q in range(int(input().strip())):
	(n, m) = [int(i) for i in input().strip().split(' ')]
	students = [Student() for i in range(n)]
	n_idles = 0
	for a1 in range(m):
		(x, y) = [int(i) for i in input().strip().split(' ')]
		root_x = students[x - 1].get_root()
		root_y = students[y - 1].get_root()
		if root_x != root_y:
			if root_x.n >= root_y.n:
				root_y.root = root_x
				root_x.n += root_y.n
			else:
				root_x.root = root_y
				root_y.n += root_x.n
		else:
			n_idles += 1
	groups_sizes = [s.n for s in students if s.root == s and s.n > 1]
	groups_sizes.sort(reverse=True)
	other_groups_fs = 0
	total = 0
	for size in groups_sizes:
		total += size * (size + 1) * (size - 1) // 3 + (size - 1) * other_groups_fs
		other_groups_fs += size * (size - 1)
	total += other_groups_fs * n_idles
	print(total)


import sys
from collections import deque

class Graph:

	def __init__(self, n):
		self.n = n
		self.nodes = {str(i): Node() for i in range(1, n + 1)}

	def connect(self, u, v):
		self.nodes[u].connected_to.append(v)
		self.nodes[v].connected_to.append(u)

	def bfs(self, s):
		layer = 0
		queue = deque([s])
		nodes = 1
		edges = 0
		self.nodes[s].explored = True
		self.nodes[s].layer = layer
		while len(queue) != 0:
			temp = tuple(queue)
			for node in temp:
				queue.popleft()
				for connected_node in self.nodes[node].connected_to:
					edges += 1
					if self.nodes[connected_node].explored == False:
						nodes += 1
						queue.append(connected_node)
						self.nodes[connected_node].layer = layer + 1
						self.nodes[connected_node].explored = True
			layer += 1
		return (nodes, edges // 2)

	def find_connections(self):
		disconnected_regions = []
		disconnected_regions.append(self.bfs('1'))
		for node in self.nodes:
			if self.nodes[node].explored == False:
				disconnected_regions.append(self.bfs(node))
		return disconnected_regions

class Node:

	def __init__(self):
		self.connected_to = []
		self.explored = False
		self.layer = -1
t = int(input().strip())
for a0 in range(t):
	(n, m) = input().strip().split(' ')
	(n, m) = [int(n), int(m)]
	graph = Graph(n)
	for a1 in range(m):
		(x, y) = input().strip().split(' ')
		graph.connect(x, y)
	connections = graph.find_connections()
	connections.sort(key=lambda region: region[0], reverse=True)
	total = 0
	leftover_links = 0
	multiplier = 0
	for group in connections:
		total += 1 / 3 * group[0] * (group[0] + 1) * (group[0] - 1) + (group[0] - 1) * multiplier
		leftover_links += group[1] - (group[0] - 1)
		multiplier += group[0] * (group[0] - 1)
	total += leftover_links * multiplier
	print(int(total))


def base_of(v):
	if prev[v] == v:
		return v
	prev[v] = base_of(prev[v])
	return prev[v]

def unite(a, b):
	a = base_of(a)
	b = base_of(b)
	if a != b:
		if size[a] < size[b]:
			(a, b) = (b, a)
		prev[a] = b
		size[b] += size[a]
		edges[b] += edges[a]
		size[a] = 0
		edges[a] = 0
	edges[b] += 1
q = int(input())
for _ in range(q):
	(n, m) = map(int, input().split())
	prev = [i for i in range(n)]
	size = [1 for i in range(n)]
	edges = [0 for i in range(n)]
	for j in range(m):
		(a, b) = map(lambda x: int(x) - 1, input().split())
		unite(a, b)
	extra_edges = 0
	components = []
	for i in range(n):
		s = size[i]
		if s != 0:
			extra_edges += edges[i] - s + 1
			components.append(s)
	components = sorted(components, reverse=True)
	total = 0
	friends = 0
	for c in components:
		total += (c - 1) * friends
		total += c * (c - 1) * (3 + (2 * c - 1)) // 6
		friends += c * (c - 1)
	total += friends * extra_edges
	print(total)


import sys
t = int(input().strip())
for _ in range(t):
	(n, m) = map(int, input().strip().split(' '))
	ilst = [i for i in range(n)]
	vlst = [0 for i in range(n)]
	total = 0
	inc = 0
	redun = 0
	for _ in range(m):
		(x, y) = map(int, input().strip().split(' '))
		x -= 1
		y -= 1
		while ilst[x] != x:
			x = ilst[x]
		while ilst[y] != y:
			y = ilst[y]
		if ilst[x] != ilst[y]:
			vlst[y] += vlst[x] + 1
			vlst[x] = 0
			ilst[x] = y
		else:
			redun += 1
	mlst = [el for el in vlst if el != 0]
	mlst.sort(reverse=True)
	for el in mlst:
		total += inc * el + el * (el + 1) * (el + 2) // 3
		inc += el * (el + 1)
	total += redun * inc
	print(total)


import sys

class UnionFind(object):

	def __init__(self, N):
		self.id = [i for i in range(N)]
		self.size = [1] * N
		self.components = N

	def _validate_range(self, i):
		if not 0 <= i <= len(self.id) - 1:
			raise IndexError('Index out of range')

	def find(self, i):
		self._validate_range(i)
		while i != self.id[i]:
			self.id[i] = self.id[self.id[i]]
			i = self.id[i]
		return i

	def components(self):
		return self.components

	def connected(self, i, j):
		self._validate_range(i)
		self._validate_range(j)
		root_i = self.find(i)
		root_j = self.find(j)
		return root_i == root_j

	def union(self, i, j):
		self._validate_range(i)
		self._validate_range(j)
		(root_i, root_j) = (self.find(i), self.find(j))
		if root_i == root_j:
			return False
		if self.size[root_i] < self.size[root_j]:
			(root_i, root_j) = (root_j, root_i)
		self.id[root_j] = root_i
		self.size[root_i] += self.size[root_j]
		self.size[root_j] = 0
		self.components -= 1
		return True

def solve(n, m, inp):
	uf = UnionFind(n)
	for new_friendship in range(m):
		(a, b) = map(int, inp.readline().strip().split())
		uf.union(a - 1, b - 1)

	def get_value(n):
		sum_of_squares = n * (n - 1) * (2 * n - 1) // 6
		sum_of_ids = n * (n - 1) // 2
		return sum_of_squares + sum_of_ids

	def brute_count_value(uf, m):
		(total, cur_cache, remaining) = (0, 0, m)
		for item in reversed(sorted(uf.size)):
			remaining -= item - 1
			total += get_value(item) + remaining * (item * (item - 1))
			if item == 0:
				break
		return total
	value = brute_count_value(uf, m)
	return value

def main(inp=sys.stdin):
	q = int(inp.readline().strip())
	for query in range(q):
		(n, m) = map(int, inp.readline().strip().split())
		print(solve(n, m, inp))
main()


import sys
from collections import defaultdict
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	(g, res) = (defaultdict(list), 0)
	for _ in range(m):
		(x, y) = map(int, sys.stdin.readline().split())
		(x, y) = (x - 1, y - 1)
		g[x].append(y)
		g[y].append(x)
	components = []
	visited = [False for _ in range(n)]
	for r in range(n):
		if visited[r]:
			continue
		visited[r] = True
		component_size = 0
		stack = [r]
		while stack:
			curr = stack.pop()
			component_size += 1
			for child in g[curr]:
				if not visited[child]:
					visited[child] = True
					stack.append(child)
		components.append(component_size)
	components = sorted(components)[::-1]
	result = 0
	(redundant, cumsum) = (0, 0)
	for c in components:
		local_cnt = 0
		for i in range(1, c):
			local_cnt = i * (i + 1)
			result += cumsum + local_cnt
		cumsum += local_cnt
	result += (m - (sum(components) - len(components))) * cumsum
	print(result)


class DisjointSet(object):

	def __init__(self):
		self.leader = {}
		self.group = {}

	def add(self, a, b):
		leadera = self.leader.get(a)
		leaderb = self.leader.get(b)
		if leadera is not None:
			if leaderb is not None:
				if leadera == leaderb:
					return
				groupa = self.group[leadera]
				groupb = self.group[leaderb]
				if len(groupa) < len(groupb):
					(a, leadera, groupa, b, leaderb, groupb) = (b, leaderb, groupb, a, leadera, groupa)
				groupa |= groupb
				del self.group[leaderb]
				for k in groupb:
					self.leader[k] = leadera
			else:
				self.group[leadera].add(b)
				self.leader[b] = leadera
		elif leaderb is not None:
			self.group[leaderb].add(a)
			self.leader[a] = leaderb
		else:
			self.leader[a] = self.leader[b] = a
			self.group[a] = {a, b}
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	ans = 0
	ds = DisjointSet()
	for __ in range(m):
		(v1, v2) = map(int, input().split())
		ds.add(v1, v2)
	prev_sum = 0
	useful_connection = 0
	group_len_arr = sorted([len(x) for x in ds.group.values()], reverse=True)
	for a in group_len_arr:
		useful_connection += a - 1
		ans += a * (a - 1) * (a + 1) // 3 + prev_sum * (a - 1)
		prev_sum += a * (a - 1)
	ans += prev_sum * (m - useful_connection)
	print(ans)


import sys
from functools import reduce
from operator import add

def bfs(graph, start):
	(visited, queue) = (set(), [start])
	points = []
	while queue:
		vertex = queue.pop(0)
		if vertex not in visited:
			visited.add(vertex)
			queue.extend(graph[vertex] - visited)
			visited_len = len(visited)
			if visited_len > 1:
				points.append((visited_len - 1) * visited_len)
	return (visited, points)
t = int(input().strip())
for a0 in range(t):
	(n, m) = input().strip().split(' ')
	(n, m) = [int(n), int(m)]
	vertexes = set(range(1, n + 1))
	graph = {k: set() for k in range(1, n + 1)}
	cons = set()
	for a1 in range(m):
		(x, y) = input().strip().split(' ')
		(x, y) = [int(x), int(y)]
		cons.add((x, y))
		graph[x].add(y)
		graph[y].add(x)
	ccp = []
	final = 0
	while vertexes:
		(visited, points) = bfs(graph, next(iter(vertexes)))
		ccp.append(points)
		vertexes = vertexes - visited
	ccp = sorted(ccp, key=lambda x: len(x), reverse=True)
	final_list = ccp.pop(0)
	while ccp:
		current_max = final_list[-1]
		to_add = [num + current_max for num in ccp[0]]
		ccp.pop(0)
		final_list.extend(to_add)
	list_queue = [final_list[-1]] * (len(cons) - len(final_list))
	final_list.extend(list_queue)
	final = reduce(add, final_list)
	print(final)


import sys

def compute_idx(edges):
	h = {}
	for (a, b) in edges:
		if a in h:
			h[a].append(b)
		else:
			h[a] = [b]
		if b in h:
			h[b].append(a)
		else:
			h[b] = [a]
	return h

def get_comp(c, a):
	x = a
	while True:
		if c[x] == x:
			return x
		else:
			y = c[x]
			c[x] = c[y]
			x = y

def compute_comps(edges):
	c = {}
	for (a, b) in edges:
		c[a] = a
		c[b] = b
	for (a, b) in edges:
		aa = get_comp(c, a)
		bb = get_comp(c, b)
		t = min(aa, bb)
		c[aa] = t
		c[bb] = t
		c[a] = t
		c[b] = t
	for a in c:
		c[a] = get_comp(c, a)
	return c

def comp_sizes(c):
	s = {}
	for a in c:
		cc = c[a]
		if cc in s:
			s[cc] += 1
		else:
			s[cc] = 1
	return s

def comp_edges(c, edges):
	t = {}
	for (a, b) in edges:
		cc = c[a]
		if cc in t:
			t[cc] += 1
		else:
			t[cc] = 1
	return t

def value(s, t):
	x1 = s * (s + 1) // 2
	x2 = s * (s + 1) * (2 * s + 1) // 6
	return x2 - x1
t = int(input().strip())
for a0 in range(t):
	(n, m) = input().strip().split(' ')
	(n, m) = [int(n), int(m)]
	edges = []
	for a1 in range(m):
		e = tuple((int(x) for x in input().strip().split(' ')))
		edges.append(e)
	c = compute_comps(edges)
	s = comp_sizes(c)
	t = comp_edges(c, edges)
	q = sorted([(s[x], t[x]) for x in s], reverse=True)
	rv = 0
	prev = 0
	extra = 0
	for (ss, tt) in q:
		vv = value(ss, tt)
		rv += vv + (ss - 1) * prev
		prev += (ss - 1) * ss
		extra += tt - ss + 1
	rv += extra * prev
	print(rv)


q = int(input())
hlist = [0] * 100100
for _ in range(q):
	c_sums = 0
	c_neigh = {}
	(n, m) = [int(x) for x in input().split()]
	for bond in range(m):
		(a, b) = [int(x) - 1 for x in input().split()]
		if a in c_neigh:
			c_neigh[a].append(b)
		else:
			c_neigh[a] = [b]
		if b in c_neigh:
			c_neigh[b].append(a)
		else:
			c_neigh[b] = [a]
	c_found = [False] * n
	c_group_size = []
	c_unnec = 0
	for contact in range(n):
		if not c_found[contact] and contact in c_neigh:
			c_found[contact] = True
			hb = 0
			hs = 0
			bonds = 0
			hlist[hs] = contact
			hs += 1
			while hb != hs:
				i = hlist[hb]
				hb += 1
				bonds += len(c_neigh[i])
				for f in c_neigh[i]:
					if not c_found[f]:
						c_found[f] = True
						hlist[hs] = f
						hs += 1
			c_group_size.append(hs)
			c_unnec += bonds // 2 - (hs - 1)
	total = 0
	friendships = 0
	c_group_size.sort(reverse=True)
	for i in c_group_size:
		total += friendships * (i - 1) + (i - 1) * i * (i + 1) // 3
		friendships += i * (i - 1)
	total += c_unnec * friendships
	print(total)


from collections import defaultdict
import sys
t = int(input().strip())
for a0 in range(t):
	(n, m) = input().strip().split(' ')
	(n, m) = [int(n), int(m)]
	blobs = defaultdict(set)
	masters = defaultdict(int)
	totalsz = 0
	sz = 0
	for a1 in range(m):
		(x, y) = input().strip().split(' ')
		(x, y) = [int(x), int(y)]
		if x not in masters and y not in masters:
			blobs[x].add(x)
			blobs[x].add(y)
			masters[x] = x
			masters[y] = x
			sz += 2
		elif y not in masters:
			blobs[masters[x]].add(y)
			masters[y] = masters[x]
			sz += 2 * (len(blobs[masters[x]]) - 1)
		elif x not in masters:
			blobs[masters[y]].add(x)
			masters[x] = masters[y]
			sz += 2 * (len(blobs[masters[x]]) - 1)
		elif masters[x] != masters[y]:
			mx = masters[x]
			my = masters[y]
			if len(blobs[mx]) >= len(blobs[my]):
				smaller = my
				larger = mx
			else:
				smaller = mx
				larger = my
			ls = len(blobs[smaller])
			ll = len(blobs[larger])
			sz -= ls * (ls + 1) + ll * (ll + 1)
			sz += (ls + ll) * (ls + ll + 1)
			for node in blobs[smaller]:
				masters[node] = larger
			blobs[larger].update(blobs[smaller])
			blobs[smaller] = set()
		totalsz += sz
	totalsz = 0
	sz = 0
	totalrounds = 0
	blobss = [(len(b), b) for b in blobs.values()]
	blobss.sort(reverse=True)
	for (_, b) in blobss:
		rounds = len(b) - 1
		totalrounds += rounds
		prevszs = sz * rounds
		toadd = rounds * (rounds + 1)
		toaddtotal = int(toadd * (rounds + 2) / 3)
		totalsz += prevszs + toaddtotal
		sz += toadd
	totalsz += (m - totalrounds) * sz
	print(totalsz)


import sys
t = int(input().strip())
for a0 in range(t):
	(n, m) = input().strip().split(' ')
	(n, m) = [int(n), int(m)]
	GroupIden = [-1 for i in range(n)]
	NewGroupInd = 0
	GroupDict = {}
	for a1 in range(m):
		(x, y) = input().strip().split(' ')
		(x, y) = [int(x) - 1, int(y) - 1]
		Groupx = GroupIden[x]
		Groupy = GroupIden[y]
		if Groupx == -1 and Groupy == -1:
			GroupDict[NewGroupInd] = [x, y]
			GroupIden[x] = NewGroupInd
			GroupIden[y] = NewGroupInd
			NewGroupInd += 1
		elif Groupx == Groupy:
			pass
		elif min([Groupx, Groupy]) == -1:
			ActiveGroup = max([Groupx, Groupy])
			if Groupx == -1:
				GroupIden[x] = ActiveGroup
				GroupDict[ActiveGroup].append(x)
			elif Groupy == -1:
				GroupIden[y] = ActiveGroup
				GroupDict[ActiveGroup].append(y)
		else:
			ActiveGroup = max([Groupx, Groupy])
			MergingGroup = min([Groupx, Groupy])
			for i in GroupDict[MergingGroup]:
				GroupDict[ActiveGroup].append(i)
				GroupIden[i] = ActiveGroup
			del GroupDict[MergingGroup]
			nGroup = len(GroupDict[ActiveGroup])
	GroupSizes = []
	for keys in GroupDict:
		GroupSizes.append(len(GroupDict[keys]))
	GroupSizes.sort()
	GroupSizes.reverse()
	IncVal = 0
	Count = 0
	IncCount = 0
	for Groups in GroupSizes:
		for Size in range(2, Groups + 1):
			IncVal += 2 * (Size - 1)
			Count += IncVal
			IncCount += 1
	Count += (m - IncCount) * IncVal
	print(Count)


from collections import deque

def clusters(n, m, E):
	nodes = set(E.keys())
	C = []
	while nodes:
		Q = deque()
		start = nodes.pop()
		Q.appendleft(start)
		visited = set([start])
		while Q:
			cur = Q.pop()
			for neigh in E[cur]:
				if neigh not in visited:
					visited.add(neigh)
					Q.appendleft(neigh)
		nodes -= visited
		nedges = sum((len(E[x]) for x in visited))
		C.append((len(visited), nedges // 2))
	return C

def task(N, M, E):
	C = sorted(clusters(N, M, E), reverse=True)
	total = 0
	togo = 0
	curfriendship = 0
	for (n, e) in C:
		togo += e - n + 1
		total += (n - 1) * n * (n + 1) // 3 + (n - 1) * curfriendship
		curfriendship += n * (n - 1)
	total += togo * curfriendship
	return total
Q = int(input())
for q in range(Q):
	(n, m) = map(int, input().split())
	edges = [[int(x) for x in input().split()] for _ in range(m)]
	E = {}
	for (a, b) in edges:
		if a not in E:
			E[a] = [b]
		else:
			E[a].append(b)
		if b not in E:
			E[b] = [a]
		else:
			E[b].append(a)
	t1 = task(n, m, E)
	print(t1)


from collections import Counter

class UnionFind:

	def __init__(self, n):
		self.parent = list(range(n))
		self.rank = [0] * n

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

	def union(self, a, b):
		aRoot = self.find(a)
		bRoot = self.find(b)
		if aRoot != bRoot:
			if self.rank[aRoot] < self.rank[bRoot]:
				self.parent[aRoot] = bRoot
			else:
				self.parent[bRoot] = aRoot
				if self.rank[aRoot] == self.rank[bRoot]:
					self.rank[aRoot] += 1

def maxfriends(n, friends):
	groups = UnionFind(n)
	for (a, b) in friends:
		groups.union(a - 1, b - 1)
	c = Counter((groups.find(i) for i in range(n)))
	total = 0
	turns = 0
	waiting = 0
	for v in sorted(c.values(), reverse=True):
		total += (v * v - 1) * v // 3 + waiting * (v - 1)
		waiting += v * (v - 1)
		turns += v - 1
	total += waiting * (len(friends) - turns)
	return total
for _ in range(int(input())):
	(n, m) = (int(x) for x in input().split())
	friends = [(int(x) for x in input().split()) for _ in range(m)]
	print(maxfriends(n, friends))


import sys
import itertools

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

def add_edge_to_inc(inc, n1, n2):
	r = inc.get(n1, set())
	r.add(n2)
	inc[n1] = r

def iterate_spanning_trees(nodes_set, inc):
	to_process = set(nodes_set)
	while to_process:
		res_tree = {}
		res_nodes = set()
		start_node = to_process.pop()
		queue = [start_node]
		while queue:
			node = queue.pop()
			for inc_node in inc.get(node, set()):
				if inc_node not in to_process:
					continue
				add_edge_to_inc(res_tree, node, inc_node)
				queue.append(inc_node)
				to_process.discard(inc_node)
				res_nodes.add(inc_node)
			res_nodes.add(node)
			to_process.discard(node)
		yield (res_tree, res_nodes)

def count_value(trees, orig_inc):
	value = 0
	rest_value = 0
	extras = 0
	for (tree_nodes, inc) in trees:
		total_edges = 0
		for node in tree_nodes:
			total_edges += len(orig_inc[node])
		total_edges //= 2
		tree_edges = len(tree_nodes) - 1
		for i in range(1, tree_edges + 1):
			value += i * (i + 1) + rest_value
		if tree_edges < total_edges:
			extras += total_edges - tree_edges
		rest_value += tree_edges * (tree_edges + 1)
	value += rest_value * extras
	return value

def count_of_friends(node, inc):
	count = 0
	visited = set()
	queue = [node]
	while queue:
		n = queue.pop()
		if n in visited:
			continue
		if n != node:
			count += 1
		visited.add(n)
		for inc_n in inc.get(n, set()):
			if inc_n in visited:
				continue
			queue.append(inc_n)
	return count

def value_of_inc(nodes, inc):
	value = 0
	for n in nodes:
		f = count_of_friends(n, inc)
		value += f
	return value

def count_value_full(perm, inc):
	curr_inc = {}
	total_value = 0
	for (n1, n2) in perm:
		add_edge_to_inc(curr_inc, n1, n2)
		add_edge_to_inc(curr_inc, n2, n1)
		dval = value_of_inc(set(inc.keys()), curr_inc)
		total_value += dval
	return total_value

def brute_force(inc, pairs):
	best_value = 0
	best_perm = None
	for perm in itertools.permutations(pairs):
		value = count_value_full(perm, inc)
		if value > best_value:
			best_value = value
			best_perm = perm
	return (best_value, best_perm)
q_count = read_ints()[0]
for _ in range(q_count):
	(nodes, edges) = read_ints()
	inc = {}
	nodes_set = set()
	pairs = []
	for _ in range(edges):
		(a, b) = read_ints()
		nodes_set.add(a)
		nodes_set.add(b)
		add_edge_to_inc(inc, a, b)
		add_edge_to_inc(inc, b, a)
		pairs.append((a, b))
	trees = []
	for (spanning_tree, tree_nodes) in iterate_spanning_trees(nodes_set, inc):
		trees.append((tree_nodes, spanning_tree))
	trees.sort(key=lambda p: len(p[0]), reverse=True)
	value = count_value(trees, inc)
	print(value)
pass


import sys

class Node:

	def __init__(self, i):
		self.parent = self
		self.rank = 0
		self.index = i
		self.cluster_size = 0

	def union(self, y):
		xRoot = self.find()
		yRoot = y.find()
		if xRoot == yRoot:
			return
		if xRoot.rank < yRoot.rank:
			xRoot.parent = yRoot
		elif yRoot.rank < xRoot.rank:
			yRoot.parent = xRoot
		else:
			yRoot.parent = xRoot
			xRoot.rank += 1

	def find(self):
		if self.parent != self:
			self.parent = self.parent.find()
		return self.parent

def from_block(x):
	return x * (x - 1) * (x + 1) // 3
t = int(input().strip())
for a0 in range(t):
	(n, m) = input().strip().split(' ')
	(n, m) = [int(n), int(m)]
	nodes = [Node(i) for i in range(n)]
	for a1 in range(m):
		(x, y) = input().strip().split(' ')
		(x, y) = [int(x) - 1, int(y) - 1]
		nodes[x].union(nodes[y])
	for i in range(n):
		nodes[i].find().cluster_size += 1
	sizes = list(reversed(sorted([x.cluster_size for x in nodes if x.cluster_size > 0])))
	left_edges = m
	result = 0
	sizes_index = 0
	while m > 0 and sizes_index < len(sizes):
		current_size = sizes[sizes_index]
		sizes_index += 1
		if current_size <= m:
			result += from_block(current_size)
			result += current_size * (current_size - 1) * (m - current_size + 1)
		else:
			result += from_block(m)
		m -= current_size - 1
	print(result)


def count_components(G, N):
	from collections import Counter
	marks = N * [0]

	def markCC(start, mark):
		if marks[start]:
			return mark
		marks[start] = mark
		stack = [start]
		while stack:
			for e in G[stack.pop()]:
				if not marks[e]:
					marks[e] = mark
					stack.append(e)
		return mark + 1
	mark = 1
	for start in range(N):
		mark = markCC(start, mark)
	return sorted(Counter(marks).values(), reverse=True)

def read_graph():
	from collections import defaultdict
	(V, E) = map(int, input().split())
	G = defaultdict(set)
	for _ in range(E):
		(b, e) = map(lambda sn: int(sn) - 1, input().split())
		G[b].add(e)
		G[e].add(b)
	return (G, V, E)

def solve(listCC, E):
	res = 0
	for m in listCC:
		res += (m - 1) * m * (m + 1) // 3
		E -= m - 1
		res += m * (m - 1) * E
	return res
for _ in range(int(input())):
	(G, V, E) = read_graph()
	listCC = count_components(G, V)
	print(solve(listCC, E))


from collections import defaultdict

class Node:
	__slots__ = ('id', 'extras', 'parent', 'rank')

	def __init__(self, n):
		self.id = n
		self.extras = 0
		self.parent = self
		self.rank = 0

def union(x, y):
	x_root = find(x)
	y_root = find(y)
	if x_root == y_root:
		x_root.extras += 1
		return
	if x_root.rank < y_root.rank:
		x_root.parent = y_root
	elif x_root.rank > y_root.rank:
		y_root.parent = x_root
	else:
		y_root.parent = x_root
		x_root.rank += 1

def find(x):
	if x.parent != x:
		x.parent = find(x.parent)
	return x.parent
for _ in range(int(input().strip())):
	(n, m) = [int(x) for x in input().strip().split(' ')]
	forest = [Node(x + 1) for x in range(n)]
	for _ in range(m):
		(u, v) = [int(x) for x in input().strip().split(' ')]
		union(forest[u - 1], forest[v - 1])
	groups = defaultdict(int)
	extras = [0] * (n + 1)
	for node in forest:
		root = find(node)
		if node != root:
			groups[root.id] += 1
		extras[root.id] += node.extras
	groups = sorted(map(list, map(reversed, groups.items())), reverse=True)
	sizes_so_far = 0
	total = 0
	extra = 0
	for (group, gid) in groups:
		temp = group * (1 + group) * (2 + group) // 3
		total += group * sizes_so_far + temp
		sizes_so_far += group * (group + 1)
		extra += extras[gid]
	total += extra * sizes_so_far
	print(total)


from heapq import heappop, heappush
from collections import deque
t = int(input().strip())
for a0 in range(t):
	(n, m) = input().strip().split(' ')
	(n, m) = [int(n), int(m)]
	d = dict()
	total = 0
	last = 0
	for i in range(1, n + 1):
		d[i] = set([i])
	for a1 in range(m):
		(x, y) = input().strip().split(' ')
		(x, y) = sorted([int(x), int(y)])
		d[x].add(y)
		d[y].add(x)
	master = set()
	h = []
	for k in d.keys():
		if k not in master:
			master.add(k)
			q = deque()
			q.append(k)
			size = 0
			while len(q) > 0:
				node = q.pop()
				size += 1
				for i in d[node]:
					if i not in master:
						master.add(i)
						q.append(i)
			heappush(h, -size)
	extras = 0
	while len(h) > 0:
		k = -heappop(h)
		for i in range(1, k):
			total += i * (i + 1) + extras
			m -= 1
		extras += k * (k - 1)
	total += m * extras
	print(total)


def max_friendships(num_students, friendships):
	friendlists = [list() for _ in range(num_students + 1)]
	for (f1, f2) in friendships:
		friendlists[f1].append(f2)
		friendlists[f2].append(f1)
	uncliqued = [True] * (num_students + 1)
	cliques = list()
	for i in range(num_students + 1):
		if uncliqued[i]:
			size = 0
			todo = [i]
			uncliqued[i] = False
			while todo:
				j = todo.pop()
				size += 1
				for k in friendlists[j]:
					if uncliqued[k]:
						todo.append(k)
						uncliqued[k] = False
			cliques.append(size)
	cliques.sort(reverse=True)
	total = 0
	friends = 0
	friendships_added = 0
	for n in cliques:
		for inc in range(2, n * 2, 2):
			friends += inc
			total += friends
			friendships_added += 1
	return total + friends * (len(friendships) - friendships_added)
for _ in range(int(input())):
	(num_students, num_friendships) = [int(x) for x in input().split()]
	friendships = list()
	for _ in range(num_friendships):
		friendships.append(tuple([int(x) for x in input().split()]))
	print(max_friendships(num_students, friendships))


def dfs(d, u):
	s = [u]
	while s:
		v = s.pop()
		if not visited[v]:
			visited[v] = True
			s.extend(d[v])
for _ in range(int(input())):
	(n, m) = [int(a) for a in input().split()]
	d = dict(zip(list(range(n)), [[] for i in range(n)]))
	for i in range(m):
		(x, y) = [int(a) - 1 for a in input().split()]
		d[x].append(y)
		d[y].append(x)
	count = 0
	comps = []
	visited = [False] * n
	for u in d:
		if not visited[u]:
			dfs(d, u)
			newcount = visited.count(True)
			comps.append(newcount - count)
			count = newcount
	comps.sort(reverse=True)
	total = sum((x * (x - 1) * (x + 1) // 3 for x in comps))
	for x in comps:
		m -= x - 1
		total += m * x * (x - 1)
	print(total)


import sys
from collections import Counter

def find_root(node):
	while parts[node] != node:
		node = parts[node]
	return node
for _ in range(int(input())):
	(n, m) = [int(p) for p in input().split()]
	parts = [q for q in range(n)]
	for _ in range(m):
		(x, y) = [int(x) - 1 for x in input().split()]
		x_root = find_root(x)
		y_root = find_root(y)
		if x_root < y_root:
			parts[y] = x_root
			parts[y_root] = x_root
		else:
			parts[x] = y_root
			parts[x_root] = y_root
	for node in range(n):
		parts[node] = find_root(node)
	parts = [part[1] for part in Counter(parts).most_common() if part[1] != 1]
	total = 0
	sub_total = 0
	cur_part_size = 1
	part = 0
	for i in range(m):
		sub_total += 2 * cur_part_size
		total += sub_total
		cur_part_size += 1
		if cur_part_size == parts[part]:
			part += 1
			if part == len(parts):
				total += sub_total * (m - i - 1)
				break
			cur_part_size = 1
	print(total)


from queue import Queue
from itertools import chain

def bfs(start, g, visited):
	count = 0
	q = Queue()
	q.put((None, start))
	while not q.empty():
		(prev, node) = q.get()
		if visited[node]:
			continue
		visited[node] = True
		count += 1
		if prev != None:
			g[prev].remove(node)
			g[node].remove(prev)
		for w in g[node]:
			q.put((node, w))
	return count

def main():
	(n, m) = map(int, input().split())
	nodes = range(1, n + 1)
	g = {node: set() for node in nodes}
	for _ in range(m):
		(u, v) = map(int, input().split())
		g[u].add(v)
		g[v].add(u)
	friends = []
	visited = {node: False for node in nodes}
	for node in nodes:
		if visited[node]:
			continue
		count = bfs(node, g, visited) - 1
		if count > 0:
			friends.append(count)
	friends.sort(reverse=True)
	total = 0
	all_components = 0
	for count in friends:
		this = count * (count + 1) * (count + 2) // 3
		others = all_components * count
		total += this + others
		all_components += count * (count + 1)
	endpoints = list(chain.from_iterable(g.values()))
	assert len(endpoints) % 2 == 0
	junk_edges = len(endpoints) // 2
	total += all_components * junk_edges
	print(total)
for case in range(int(input())):
	main()


import sys
t = int(input().strip())
for a0 in range(t):
	(n, m) = input().strip().split(' ')
	(n, m) = [int(n), int(m)]
	root = [i for i in range(n + 1)]
	cluster = [set({i}) for i in range(n + 1)]
	extra = 0
	size = dict()
	for i in range(n + 1):
		size[i] = 1
	for a1 in range(m):
		(x, y) = input().strip().split(' ')
		(x, y) = [int(x), int(y)]
		rootx = root[x]
		rooty = root[y]
		if rootx != rooty:
			if len(cluster[rootx]) < len(cluster[rooty]):
				smaller = rootx
				bigger = rooty
			else:
				smaller = rooty
				bigger = rootx
			for u in cluster[smaller]:
				root[u] = bigger
				cluster[bigger].add(u)
			size[bigger] = len(cluster[bigger])
			size.pop(smaller)
		else:
			extra += 1
	for i in range(n + 1):
		if i in size and size[i] == 1:
			size.pop(i)
	ordered = sorted(size.values(), reverse=True)
	total = 0
	f = 0
	for k in ordered:
		for i in range(2, k + 1):
			total += f + i * (i - 1)
		f += k * (k - 1)
	total += extra * f
	print(total)


adjacencies = []
visited = []
import sys
q = int(input().strip())

def visit(vert):
	toadd = []
	if visited[vert] == False:
		toVisit = []
		toVisit.append(vert)
		while len(toVisit) > 0:
			current = toVisit.pop()
			if visited[current] == False:
				toadd.append(current)
				visited[current] = True
				for v in adjacencies[current]:
					toVisit.append(v)
	return toadd

def formula(size):
	return int(size * (size + 1) * (size + 2) / 3)
for i in range(q):
	(n, m) = map(int, input().strip().split(' '))
	adjacencies = []
	for v in range(n):
		adjacencies.append([])
	for j in range(m):
		(a, b) = map(int, input().strip().split(' '))
		adjacencies[a - 1].append(b - 1)
		adjacencies[b - 1].append(a - 1)
	visited = [False] * n
	connectedComponents = []
	for v in range(n):
		comp = visit(v)
		if len(comp) > 1:
			connectedComponents.append(comp)
	extraPieces = 0
	compLengths = []
	for subgraph in connectedComponents:
		connections = 0
		for v in subgraph:
			connections += len(adjacencies[v])
		connections = connections / 2
		extra = connections - len(subgraph) + 1
		extraPieces += extra
		compLengths.append(len(subgraph))
	compLengths.sort(reverse=True)
	friendCount = 0
	total = 0
	for j in compLengths:
		friendCount += formula(j - 1)
		friendCount += total * (j - 1)
		total += j * (j - 1)
	friendCount += extraPieces * total
	print(int(friendCount))


import sys

def q(n, lst):
	v_to_cc = list(range(n))
	cc = [[v] for v in range(n)]
	for (x, y) in lst:
		cx = v_to_cc[x]
		cy = v_to_cc[y]
		vertices_x = cc[cx]
		vertices_y = cc[cy]
		if cx != cy:
			if len(vertices_x) > len(vertices_y):
				(x, y) = (y, x)
				(cx, cy) = (cy, cx)
				(vertices_x, vertices_y) = (vertices_y, vertices_x)
			for v in vertices_x:
				v_to_cc[v] = cy
			cc[cx] = None
			cc[cy] = vertices_y + vertices_x
	total = 0
	sub_total = 0
	steps = 0
	for l in sorted((len(vertices) for vertices in cc if vertices is not None), key=lambda x: -x):
		sub_sub_total = 0
		for i in range(1, l):
			steps += 1
			sub_sub_total = i * (i + 1)
			total += sub_total + sub_sub_total
		sub_total += sub_sub_total
	m = len(lst)
	total += (m - steps) * sub_total
	return total
t = int(input().strip())
for _ in range(t):
	(n, m) = input().strip().split(' ')
	(n, m) = [int(n), int(m)]
	lst = []
	for __ in range(m):
		(x, y) = input().strip().split(' ')
		(x, y) = [int(x), int(y)]
		lst.append((x - 1, y - 1))
	print(q(n, lst))


import sys

def total(conns):
	excess = 0
	ntotal = 0
	maxavail = 0
	for conn in conns:
		comp = conn[0]
		nedg = conn[1]
		nnds = len(comp)
		excess = excess + (nedg - nnds + 1)
		for i in range(2, nnds + 1):
			ntotal = ntotal + maxavail + (i - 1) * i
		maxavail = maxavail + (nnds - 1) * nnds
	for i in range(excess):
		ntotal = ntotal + maxavail
	return ntotal

def walk(adj):
	vstd = set()
	conns = []
	for nd in adj.keys():
		if nd in vstd:
			continue
		comp = []
		nedg = 0
		queue = set([nd])
		while len(queue) != 0:
			crt = queue.pop()
			vstd.add(crt)
			comp.append(crt)
			if crt not in adj:
				continue
			for ngh in adj[crt]:
				if ngh not in vstd:
					queue.add(ngh)
					nedg = nedg + 1
		conns.append((comp, nedg))
		conns.sort(key=lambda x: len(x[0]), reverse=True)
	return conns

def main(argv=sys.argv):
	t = int(input().strip())
	for a0 in range(t):
		(n, m) = input().strip().split(' ')
		(n, m) = [int(n), int(m)]
		adj = {}
		for a1 in range(m):
			(x, y) = input().strip().split(' ')
			(x, y) = [int(x), int(y)]
			if x not in adj:
				adj[x] = [y]
			else:
				adj[x].append(y)
			if y not in adj:
				adj[y] = [x]
			else:
				adj[y].append(x)
		conns = walk(adj)
		print(total(conns))
	return 0
sys.exit(main())


t = int(input().strip())
for a0 in range(t):
	(n, m) = [int(t) for t in input().strip().split(' ')]
	parent = list(range(n))
	children = [[t] for t in range(n)]
	for a1 in range(m):
		(x, y) = [int(t) - 1 for t in input().strip().split(' ')]
		if parent[x] == parent[y]:
			continue
		if len(children[parent[x]]) > len(children[parent[y]]):
			(x, y) = (y, x)
		px = parent[x]
		for z in children[px]:
			children[parent[y]].append(z)
			parent[z] = parent[y]
		children[px] = []
	trees = []
	for (t, c) in enumerate(children):
		if len(c) > 1:
			trees.append(len(c) - 1)
	trees.sort()
	trees.reverse()
	(tot, total) = (0, 0)
	for t in trees:
		total += tot * t + (t + 2) * (t + 1) * t // 3
		tot += (t + 1) * t
	print(total + tot * (m - sum(trees)))


import queue

class Node:

	def __init__(self, value):
		self.visited = False
		self.value = value
		self.neighbors = []

	def add_neighbor(self, node):
		self.neighbors.append(node)
		node.neighbors.append(self)

class FriendGroup:

	def __init__(self, nodes):
		self._nodes = nodes
		self.num_friends = len(nodes)
		self.connections = sum([len(node.neighbors) for node in nodes]) // 2
		self.cycles = self.connections - (self.num_friends - 1)

	def total(self):
		if self.num_friends > 0:
			return self.num_friends * (self.num_friends - 1)
		else:
			return 0

	def get_and_clear_cycles(self):
		cycles = self.cycles
		self.connections -= self.cycles
		self.cycles = 0
		return cycles

	def total_and_clear(self):
		total = 0
		while self.connections > 0:
			total += self.total()
			self.num_friends -= 1
			self.connections -= 1
		return total

	def __lt__(self, other):
		return self.connections < other.connections

def run():
	queries = int(input().strip())
	for _ in range(queries):
		[n, m] = list(map(int, input().split()))
		connections = []
		for i in range(m):
			connections.append(tuple(map(int, input().split())))
		friends = make_graph(connections, n)
		friend_groups = make_friend_groups(friends)
		total = calculate_total(friend_groups)
		print(total)

def calculate_total(friend_groups):
	total = 0
	round_total = sum([group.total() for group in friend_groups])
	rounds_to_clear_cycles = sum([group.get_and_clear_cycles() for group in friend_groups])
	total += round_total * rounds_to_clear_cycles
	group_queue = queue.PriorityQueue()
	for group in friend_groups:
		group_queue.put((group.num_friends, group))
	while not group_queue.empty():
		group = group_queue.get()[1]
		round_total -= group.total()
		rounds_to_clear = group.num_friends - 1
		total += group.total_and_clear() + round_total * rounds_to_clear
	return total

def make_graph(connections, n):
	graph = [Node(i) for i in range(n + 1)]
	for connection in connections:
		graph[connection[0]].add_neighbor(graph[connection[1]])
	return graph[1:]

def make_friend_groups(friends):
	friend_groups = []
	for friend in friends:
		if not friend.visited:
			nodes = DFS(friend)
			if len(nodes) > 1:
				friend_groups.append(FriendGroup(nodes))
	return friend_groups

def DFS(node):
	nodes = []
	stack = [node]
	while stack:
		node = stack.pop()
		if not node.visited:
			node.visited = True
			nodes.append(node)
			for neighbor in node.neighbors:
				if not neighbor.visited:
					stack.append(neighbor)
	return nodes
run()


import sys

def connected_components(neighbors):
	seen = set()

	def component(node):
		nodes = set([node])
		while nodes:
			node = nodes.pop()
			seen.add(node)
			nodes |= neighbors[node] - seen
			yield node
	for node in neighbors:
		if node not in seen:
			yield sum((1 for _ in component(node)))

def getRoots(aNeigh):

	def findRoot(aNode, aRoot):
		while aNode != aRoot[aNode][0]:
			aNode = aRoot[aNode][0]
		return (aNode, aRoot[aNode][1])
	myRoot = {}
	for myNode in aNeigh.keys():
		myRoot[myNode] = (myNode, 0)
	for myI in aNeigh:
		for myJ in aNeigh[myI]:
			(myRoot_myI, myDepthMyI) = findRoot(myI, myRoot)
			(myRoot_myJ, myDepthMyJ) = findRoot(myJ, myRoot)
			if myRoot_myI != myRoot_myJ:
				myMin = myRoot_myI
				myMax = myRoot_myJ
				if myDepthMyI > myDepthMyJ:
					myMin = myRoot_myJ
					myMax = myRoot_myI
				myRoot[myMax] = (myMax, max(myRoot[myMin][1] + 1, myRoot[myMax][1]))
				myRoot[myMin] = (myRoot[myMax][0], -1)
	myToRet = {}
	for myI in aNeigh:
		if myRoot[myI][0] == myI:
			myToRet[myI] = []
	for myI in aNeigh:
		myToRet[findRoot(myI, myRoot)[0]].append(myI)
	return myToRet

def count(n):
	return (n - 1) * n * (n + 1) // 3
t = int(input().strip())
for a0 in range(t):
	(n, m) = input().strip().split(' ')
	(n, m) = [int(n), int(m)]
	Z = {v: set() for v in range(1, n + 1)}
	for a1 in range(m):
		(x, y) = input().strip().split(' ')
		(x, y) = [int(x), int(y)]
		Z[x].add(y)
		Z[y].add(x)
	cc = connected_components(Z)
	L = sorted(list(cc))
	total = 0
	added_value = 0
	connections = 0
	for i in reversed(range(0, len(L))):
		if L[i] == 1:
			break
		connections += L[i] - 1
		total += added_value * (L[i] - 1) + count(L[i])
		added_value += L[i] * (L[i] - 1)
	rest = m - connections
	total += added_value * rest
	print(total)


import sys

class Vertex:

	def __init__(self, data):
		self.data = data
		self.visited = False
		self.colour = 'white'
		self.adjVertices = []

class Tree:

	def __init__(self):
		self.vertexDic = {}
		self.numVertices = 0

	def addVertex(self, data):
		newNode = Vertex(data)
		self.vertexDic[data] = newNode
		self.numVertices += 1

	def addEdge(self, fromV, toV):
		self.vertexDic[fromV].adjVertices.append(self.vertexDic[toV])
		self.vertexDic[toV].adjVertices.append(self.vertexDic[fromV])

	def printTree(self):
		for value in self.vertexDic.values():
			print(value.data, [node.data for node in value.adjVertices])

	def getVertex(self, data):
		return self.vertexDic[data]
cum_arr = [0] * 100000
cum_arr[0] = 0
arr = [0] * 100000
arr[0] = 0
for i in range(1, 100000):
	cum_arr[i] = cum_arr[i - 1] + i * (i + 1)
	arr[i] = i * (i + 1)
t = int(input().strip())
for a0 in range(t):
	(n, m) = [int(i) for i in input().split()]
	T = Tree()
	for i in range(1, n + 1):
		T.addVertex(i)
	for i in range(m):
		edge = [int(i) for i in input().split()]
		(fromV, toV) = (edge[0], edge[1])
		T.addEdge(fromV, toV)

	def DFS(T):
		componentsVertexCount = []
		for vertex in T.vertexDic.values():
			if not vertex.visited:
				componentsVertexCount.append(dfsTraversal(T, vertex, count=[0], nonTreeEdges=[0]))
		return componentsVertexCount

	def dfsTraversal(T, vertex, count, nonTreeEdges):
		stack = []
		stack.append(vertex)
		vertex.visited = True
		vertex.colour = 'grey'
		while len(stack) > 0:
			current_vertex = stack.pop()
			count[0] += 1
			current_vertex.colour = 'black'
			for nbr in current_vertex.adjVertices:
				if nbr.visited and nbr.colour == 'grey':
					nonTreeEdges[0] += 1
				if not nbr.visited:
					stack.append(nbr)
					nbr.visited = True
					nbr.colour = 'grey'
		return (count[0], nonTreeEdges[0])
	componentsVertexCount = DFS(T)
	componentsTreeEdges = [ele[0] - 1 for ele in componentsVertexCount]
	componentsNonTreeEdges = [ele[1] for ele in componentsVertexCount]
	TotalNonTreeEdges = sum(componentsNonTreeEdges)
	componentsTreeEdges.sort(reverse=True)
	ans = 0
	count = 0
	for ele in componentsTreeEdges:
		ans += cum_arr[ele] + ele * count
		count = count + arr[ele]
	ans += TotalNonTreeEdges * count
	print(ans)


import sys

class Disjoint_Set:

	def __init__(self, size):
		self.sets = list(range(0, size + 1))
		self.sizes = dict([(x, 1) for x in self.sets])
		del self.sizes[0]

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

	def union(self, x, y):
		set_x = self.find(x)
		set_y = self.find(y)
		if set_x == set_y:
			return False
		self.sizes[set_x] += self.sizes[set_y]
		del self.sizes[set_y]
		self.sets[set_y] = set_x
		return True

	def size(self, x):
		return self.sizes[self.find(x)]
sum_mem = {}

def solve(n, m):
	forest = Disjoint_Set(n)
	sum = 0
	extra_moves = 0
	for a1 in range(m):
		(x, y) = input().strip().split(' ')
		(x, y) = [int(x), int(y)]
		if not forest.union(x, y):
			extra_moves += 1
	sorted_by_size = list(forest.sizes.values())
	sorted_by_size.sort(reverse=True)
	sum_mem[0] = 0
	sum_mem[1] = 0
	last_move_sum = 0
	for lrg_set in sorted_by_size:
		if lrg_set not in sum_mem:
			for val in range(2, lrg_set + 1):
				sum_mem[val] = sum_mem[val - 1] + val * (val - 1)
		sum += sum_mem[lrg_set] + last_move_sum * (lrg_set - 1)
		last_move_sum += lrg_set * (lrg_set - 1)
	sum += extra_moves * last_move_sum
	return sum
t = int(input().strip())
for a0 in range(t):
	(n, m) = input().strip().split(' ')
	(n, m) = [int(n), int(m)]
	print(solve(n, m))


import sys

def find(d, n):
	if d[n] != n:
		d[n] = find(d, d[n])
	return d[n]

def union(d, rank, size, u, v):
	link(d, rank, size, find(d, u), find(d, v))

def link(d, rank, size, x, y):
	sum = size[x] + size[y]
	size[x] = sum
	size[y] = sum
	if rank[x] > rank[y]:
		d[y] = x
	else:
		d[x] = y
		if rank[x] == rank[y]:
			rank[y] += 1
total = 0
t = int(input().strip())
for a0 in range(t):
	(n, m) = input().strip().split(' ')
	(n, m) = [int(n), int(m)]
	d = [i for i in range(n + 2)]
	size = [1] * (n + 2)
	rank = [0] * (n + 2)
	for a1 in range(m):
		(x, y) = input().strip().split(' ')
		(x, y) = [int(x), int(y)]
		if find(d, x) != find(d, y):
			s1 = size[find(d, x)]
			s2 = size[find(d, y)]
			union(d, rank, size, x, y)
	setSizes = {}
	for e in d:
		if d[e] == e and size[e] > 1:
			setSizes[e] = size[e]
	setCount = 0
	setSum = 0
	total = 0
	for size in sorted(setSizes.values(), reverse=True):
		setCount += size - 1
		for i in range(2, size + 1):
			total += setSum + i * (i - 1)
		setSum += size * (size - 1)
	if setCount < m:
		total += setSum * (m - setCount)
	print(total)


from collections import deque
import sys

def bfs(x, graph, ids, label):
	with_label = 0
	ids[x] = label
	q = deque([x])
	while q:
		cur = q.popleft()
		with_label += 1
		for child in graph[cur]:
			if ids[child] == -1:
				ids[child] = label
				q.append(child)
	return with_label

def main():
	(n, m) = input().strip().split(' ')
	(n, m) = [int(n), int(m)]
	graph = [list() for _ in range(n + 1)]
	for _ in range(m):
		(x, y) = input().strip().split(' ')
		(x, y) = [int(x), int(y)]
		graph[x].append(y)
		graph[y].append(x)
	next_id = 0
	ids = [-1 for _ in range(n + 1)]
	sizes = []
	for i in range(1, n + 1):
		if ids[i] == -1:
			sizes.append(bfs(i, graph, ids, next_id))
			next_id += 1
	sizes.sort(reverse=True)
	cur = 0
	total = 0
	end_edges = m
	for size in sizes:
		end_edges -= size - 1
		for i in range(1, size):
			cur -= i * (i - 1)
			cur += i * (i + 1)
			total += cur
	total += end_edges * cur
	print(total)
q = int(input().strip())
for _ in range(q):
	main()


import sys
from collections import defaultdict
from collections import deque

def bfs(n, edges, visited, starting_node):
	q = deque([starting_node])
	edge_count = 0
	node_count = 0
	while q:
		node = q.popleft()
		if visited[node]:
			continue
		node_count += 1
		visited[node] = True
		for neighbor in edges[node]:
			edge_count += 1
			q.append(neighbor)
	return (node_count, edge_count // 2)

def find_connected_components(n, edges):
	connected_components = []
	visited = [False] * (n + 1)
	for i in range(1, n + 1):
		if not visited[i]:
			connected_components.append(bfs(n, edges, visited, i))
	return sorted(connected_components, key=lambda x: x[0], reverse=True)

def solve():
	(n, m) = input().strip().split(' ')
	(n, m) = [int(n), int(m)]
	edges = defaultdict(list)
	for _ in range(m):
		(x, y) = input().strip().split(' ')
		(x, y) = [int(x), int(y)]
		edges[x].append(y)
		edges[y].append(x)
	result = 0
	edges_so_far = 0
	connected_components = find_connected_components(n, edges)
	for (node_count, edge_count) in connected_components:
		result += node_count * (node_count + 1) * (2 * node_count + 1) // 6 - (node_count + 1) * node_count // 2
		edges_so_far += node_count - 1
		result += (m - edges_so_far) * (node_count - 1) * node_count
	print(result)
t = int(input().strip())
for _ in range(t):
	solve()


import sys
from heapq import *

def conv(pairs):
	adjlist = {}
	for i in range(len(pairs)):
		pair = pairs[i]
		u = pair[0]
		v = pair[1]
		if u in adjlist:
			adjlist[u].append(v)
		else:
			adjlist[u] = [v]
		if v in adjlist:
			adjlist[v].append(u)
		else:
			adjlist[v] = [u]
	return adjlist

def bfs(s, adj):
	q = [s]
	group = []
	counter = 0
	visited[s] = 1
	vis = [0] * (n + 1)
	while q:
		c = heappop(q)
		vis[c] = 1
		group.append(c)
		a = adj[c]
		for i in range(len(a)):
			nxt = a[i]
			if not vis[nxt]:
				counter += 1
			if visited[nxt]:
				continue
			visited[nxt] = 1
			heappush(q, nxt)
	return [group, counter]
for _ in range(int(input())):
	(n, m) = input().strip().split(' ')
	(n, m) = [int(n), int(m)]
	visited = [0] * (n + 1)
	pairs = []
	for _ in range(m):
		(x, y) = input().strip().split(' ')
		(x, y) = [int(x), int(y)]
		pairs.append([x, y])
	adj = conv(pairs)
	groups = []
	for s in adj:
		if visited[s]:
			continue
		groups.append(bfs(s, adj))
	groups = sorted(groups, key=lambda x: len(x[0]), reverse=True)
	total = 0
	previousFriends = 0
	nbAllPairs = 0
	for (group, usPairs) in groups:
		k = len(group) - 1
		nbAllPairs += usPairs - k
		partialTotal = k * (k + 1) * (2 * k + 1) // 6 + k * (k + 1) // 2 + previousFriends * k
		previousFriends += k * (k + 1)
		total += partialTotal
	total += nbAllPairs * previousFriends
	print(total)


import sys
t = int(input().strip())
for a0 in range(t):
	(n, m) = input().strip().split(' ')
	(n, m) = [int(n), int(m)]
	group = {}
	group_leader = {}
	for i in range(n):
		group_leader[i + 1] = i + 1
		group[i + 1] = [i + 1]
		extras = 0
	for a1 in range(m):
		(x, y) = input().strip().split(' ')
		(x, y) = [int(x), int(y)]
		if group_leader[x] == group_leader[y]:
			extras += 1
			continue
		new_leader = min(group_leader[x], group_leader[y])
		if group_leader[x] == new_leader:
			group[new_leader] += group[group_leader[y]]
			for z in group[group_leader[y]]:
				if z != y:
					group_leader[z] = new_leader
			del group[group_leader[y]]
			group_leader[y] = new_leader
		else:
			group[new_leader] += group[group_leader[x]]
			for z in group[group_leader[x]]:
				if z != x:
					group_leader[z] = new_leader
			del group[group_leader[x]]
			group_leader[x] = new_leader
	group_list = []
	for el in group:
		group_list.append([el, group[el]])
	group_list.sort(key=lambda x: len(x[1]), reverse=True)
	count = 0
	total = 0
	for g in group_list:
		g_l = len(g[1])
		count += total * (g_l - 1) + (g_l - 1) * g_l * (g_l + 1) // 3
		total += g_l * (g_l - 1)
	count += total * extras
	print(count)


parent = {}
rank = {}
Connection = {}
P = {}

def Make(vertex):
	parent[vertex] = vertex
	rank[vertex] = 0
	Connection[vertex] = []

def Find(vertex):
	if parent[vertex] != vertex:
		parent[vertex] = Find(parent[vertex])
	return parent[vertex]

def Union(vertex1, vertex2):
	root1 = Find(vertex1)
	root2 = Find(vertex2)
	if root1 != root2:
		if rank[root1] > rank[root2]:
			parent[root2] = root1
			Connection.setdefault(root1, []).append(root2)
			if Connection[root2]:
				for value in Connection[root2]:
					Connection.setdefault(root1, []).append(value)
				Connection[root2] = []
			return root1
		else:
			parent[root1] = root2
			Connection.setdefault(root2, []).append(root1)
			if Connection[root1]:
				for value in Connection[root1]:
					Connection.setdefault(root2, []).append(value)
				Connection[root1] = []
			if rank[root1] == rank[root2]:
				rank[root2] += 1
			return root2

def F(side):
	return side * (side - 1)

def FindSum(n, m):
	l = []
	count = 0
	for x in range(1, n + 1):
		if Connection[x]:
			Connection.setdefault(x, []).append(x)
	for x in Connection:
		if Connection[x]:
			l.append(Connection[x])
	l = sorted(l, key=len)
	z = len(l)
	edges = 0
	st_included = []
	already_present = 0
	for st in range(z - 1, -1, -1):
		for y in range(2, len(l[st]) + 1):
			count += F(y) + already_present
		already_present += len(l[st]) * (len(l[st]) - 1)
		edges += len(l[st]) - 1
	count += already_present * (m - edges)
	return count
t = int(input())
for tc in range(t):
	Connection = {}
	(n, m) = list(map(int, input().split()))
	count = 0
	connected = 1
	sum = 0
	for vertex in range(1, n + 1):
		Make(vertex)
	for query in range(1, m + 1):
		(u, v) = list(map(int, input().split()))
		if Find(u) != Find(v):
			x = Union(u, v)
	print(FindSum(n, m))


import random

def solve(n, edges):
	dsu = Dsu(n)
	for pair in edges:
		dsu.unite(*pair)
	size = [[0, 0] for _ in range(n)]
	for i in range(n):
		size[dsu.get(i)][0] += 1
	for pair in edges:
		size[dsu.get(pair[0])][1] += 1
	size = [(v, e) for (v, e) in size if v > 0]
	size.sort(reverse=True)
	ans = 0
	sum = 0
	for (v, e) in size:
		cur = 0
		for i in range(2, v + 1):
			cur = i * (i - 1)
			ans += sum + cur
		sum += cur
	for (v, e) in size:
		ans += (e - v + 1) * sum
	return ans

class Dsu:

	def __init__(self, n):
		self.r = random.Random(1)
		self.p = [i for i in range(n)]

	def get(self, v):
		if self.p[v] == v:
			return v
		self.p[v] = self.get(self.p[v])
		return self.p[v]

	def unite(self, v, u):
		(v, u) = (self.get(v), self.get(u))
		if self.r.getrandbits(1):
			(v, u) = (u, v)
		self.p[v] = u

def test():
	assert solve(5, [(0, 1), (2, 1), (3, 1), (3, 2)]) == 32

def read_test():
	(n, m) = map(int, input().split())
	edges = [tuple([int(s) - 1 for s in input().split()]) for _ in range(m)]
	return (n, edges)
for _ in range(int(input())):
	print(solve(*read_test()))


import sys

class Node(object):

	def __init__(self):
		self.group_number = 0

class Graph(object):

	def __init__(self):
		self.nodes = [0]
		self.groups = [set()]
		self.groups_pop = [0]
		self.groups_size = 1

	def add_node(self, node):
		self.nodes.append(node)
		self.groups[0].add(node)
		self.groups_pop[0] += 1

def added_value(i, memo={2: 2}):
	if i < 2:
		raise ValueError('argument must be larger than 1')
	if i in memo:
		return memo[i]
	memo[i] = added_value(i - 1, memo) + 2 * (i - 1)
	return memo[i]

def main():
	q = int(input())
	for __ in range(q):
		college = Graph()
		(n, m) = map(int, input().strip().split())
		for v in range(1, n + 1):
			college.add_node(Node())
		for i in range(m):
			(n1, n2) = map(int, input().strip().split())
			(student1, student2) = (college.nodes[n1], college.nodes[n2])
			if student1.group_number == 0:
				if student2.group_number == 0:
					college.groups.append({student1, student2})
					college.groups_pop.append(2)
					college.groups_size += 1
					student1.group_number = college.groups_size - 1
					student2.group_number = college.groups_size - 1
					college.groups[0].remove(student1)
					college.groups[0].remove(student2)
					college.groups_pop[0] -= 2
				else:
					college.groups[student2.group_number].add(student1)
					college.groups_pop[student2.group_number] += 1
					college.groups[0].remove(student1)
					college.groups_pop[0] -= 1
					student1.group_number = student2.group_number
			elif student2.group_number == 0:
				college.groups[student1.group_number].add(student2)
				college.groups_pop[student1.group_number] += 1
				college.groups[0].remove(student2)
				college.groups_pop[0] -= 1
				student2.group_number = student1.group_number
			elif student1.group_number != student2.group_number:
				(mx, mn) = (student1.group_number, student2.group_number)
				if college.groups_pop[mx] < college.groups_pop[mn]:
					(mx, mn) = (mn, mx)
				for member in college.groups[mn]:
					member.group_number = mx
				college.groups[mx].update(college.groups[mn])
				college.groups_pop[mx] += college.groups_pop[mn]
				college.groups[mn].clear()
				college.groups_pop[mn] = 0
		node_sets_size = []
		for item in college.groups_pop:
			if item > 1:
				node_sets_size.append(item)
		node_sets_size.sort(reverse=True)
		total = 0
		last_value = 0
		for p in node_sets_size:
			for i in range(2, p + 1):
				total += last_value + added_value(i)
			last_value += added_value(i)
		unused_eduges = m - (sum(node_sets_size) - len(node_sets_size))
		total += last_value * unused_eduges
		print(total)
main()


import sys

class node:

	def __init__(self):
		self.nb = set([])
		self.visited = False

	def addNB(self, nb):
		self.nb.add(nb)

def DFS(nodes):
	sizes = []
	for i in range(len(nodes)):
		size = 0
		S = [i]
		while len(S) > 0:
			v = S.pop()
			if not nodes[v].visited:
				size += 1
				nodes[v].visited = True
				for nb in nodes[v].nb:
					S.append(nb)
		if size > 1:
			sizes.append(size)
	return sizes

def calcTotal(sizes, m):
	sizes = sorted(sizes, reverse=True)
	total = 0
	number = 0
	for size in sizes:
		number += size - 1
		tmp = size * (size + 1) * (2 * size + 1) / 6 - size * (size + 1) / 2
		tmp += size * (size - 1) * (m - number)
		total += tmp
	return int(total)
t = int(input().strip())
for a0 in range(t):
	(n, m) = input().strip().split(' ')
	(n, m) = [int(n), int(m)]
	nodes = [node() for i in range(n)]
	for a1 in range(m):
		(x, y) = input().strip().split(' ')
		(x, y) = [int(x) - 1, int(y) - 1]
		nodes[x].addNB(y)
		nodes[y].addNB(x)
	A = DFS(nodes)
	total = calcTotal(A, m)
	print(total)


import sys

def root(x):
	while x != root_l[x]:
		root_l[x] = root_l[root_l[x]]
		x = root_l[x]
	return x

def cal_max(forest, edges):
	forest = sorted(forest, reverse=True)
	total = 0
	mul = edges
	for tree in forest:
		conn_nodes = tree
		mul -= conn_nodes - 1
		total_now = 0
		for x in range(2, conn_nodes + 1):
			total_now += x * (x - 1)
		total += total_now + conn_nodes * (conn_nodes - 1) * mul
	return total
t = int(input())
for a0 in range(t):
	(n, m) = input().strip().split(' ')
	(n, m) = [int(n), int(m)]
	root_l = [_ for _ in range(n)]
	val_l = [1] * n
	for a1 in range(m):
		(x, y) = input().strip().split(' ')
		(x, y) = [int(x) - 1, int(y) - 1]
		(rootx, rooty) = (root(x), root(y))
		if rootx != rooty:
			val_l[rooty] = val_l[rootx] + val_l[rooty]
			val_l[rootx] = 0
			root_l[rootx] = rooty
	forest = [item for item in val_l if item > 1]
	print(int(cal_max(forest, m)))


t = int(input().strip())
for a0 in range(t):
	(n, m) = input().strip().split(' ')
	(n, m) = [int(n), int(m)]
	f = [0] * n
	p = list(range(n))

	def parent(n):
		if p[n] == n:
			return n
		p[n] = parent(p[n])
		return p[n]

	def merge(u, v):
		(u, v) = (parent(u), parent(v))
		if u != v:
			p[u] = v
			f[v] += f[u] + 1
			f[u] = 0
	for a1 in range(m):
		(x, y) = input().strip().split(' ')
		(x, y) = [int(x) - 1, int(y) - 1]
		merge(x, y)
	(s, t) = (0, 0)
	l = [i for i in f if i != 0]
	l.sort(reverse=True)
	for i in l:
		s += t * i + (i * i * i + 3 * i * i + 2 * i) // 3
		t += i * (i + 1)
	print(s + t * (m - sum(l)))


def inc(n):
	res = 0
	for i in range(1, n):
		res += i * (i + 1)
	return res

def mark(x):
	z = x
	while z:
		z = z[0]
	if x is not z:
		x[0] = z
	return z

def mark2(x):
	z = x
	while z and type(z) == list:
		z = z[0]
	if x is not z:
		x[0] = z
	return z
T = int(input())
for t in range(T):
	(n, m) = map(int, input().split())
	work = [[] for i in range(n)]
	lost = 0
	for i in range(m):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		mu = mark(work[u])
		mv = mark(work[v])
		if mu is not mv:
			mu.append(mv)
		else:
			lost += 1
	no = 1
	dic = {}
	for i in range(n):
		z = mark2(work[i])
		if not z:
			z.append(no)
			z = no
			no += 1
			dic[z] = 1
		else:
			dic[z] += 1
	res = 0
	cur = 0
	for v in sorted(dic.values(), reverse=True):
		res += inc(v) + (v - 1) * cur
		cur += v * (v - 1)
	res += lost * cur
	print(res)


import sys
from collections import deque
t = int(input().strip())
for a0 in range(t):
	(n, m) = input().strip().split(' ')
	(n, m) = [int(n), int(m)]
	friends = [[] for i in range(n)]
	searchedCache = [False for i in range(n)]
	for a1 in range(m):
		(x, y) = input().strip().split(' ')
		(x, y) = [int(x) - 1, int(y) - 1]
		friends[x].append(y)
		friends[y].append(x)
	clusterSizes = []
	for i in range(n):
		if searchedCache[i] == False:
			clusterSize = 1
			searchQueue = deque([i])
			searchedCache[i] = True
			while len(searchQueue) != 0:
				item = searchQueue.pop()
				for friend in friends[item]:
					if searchedCache[friend] == False:
						searchedCache[friend] = True
						clusterSize += 1
						searchQueue.appendleft(friend)
			clusterSizes.append(clusterSize)
	clusterSizes.sort(key=lambda x: -x)
	total = 0
	previousClusterValue = 0
	for cluster in clusterSizes:
		currentFriendshipValue = 0
		for i in range(cluster - 1):
			currentFriendshipValue = (i + 1) * (i + 2)
			total += currentFriendshipValue + previousClusterValue
		previousClusterValue += currentFriendshipValue
	extraConnections = m - (sum(clusterSizes) - len(clusterSizes))
	total += previousClusterValue * extraConnections
	print(total)


import sys
from collections import defaultdict

def calculate(components):
	mst_edges = []
	surplus_edges = 0
	for (n, e) in components:
		surplus_edges += e - n
		mst_edges.append(n)
	mst_edges.sort()
	max_iter = sum([x * (x + 1) for x in mst_edges])
	total = max_iter * surplus_edges
	for i in range(len(mst_edges)):
		while mst_edges[i] > 0:
			total += sum([x * (x + 1) for x in mst_edges])
			mst_edges[i] -= 1
	return total

def query(g):
	components = []
	seen = set()
	for node in g.keys():
		if node not in seen:
			total = 0
			edges = 0
			stack = set([node])
			while stack:
				u = stack.pop()
				seen.add(u)
				total += 1
				edges += len(g[u])
				stack.update(g[u] - seen)
			components.append((total - 1, edges // 2))
	return components
t = int(input().strip())
for a0 in range(t):
	(n, m) = input().strip().split(' ')
	(n, m) = [int(n), int(m)]
	g = defaultdict(set)
	for _ in range(m):
		(x, y) = input().strip().split(' ')
		x = int(x)
		y = int(y)
		g[x].add(y)
		g[y].add(x)
	components = query(g)
	result = calculate(components)
	print(result)


class DisjointSetUnion:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.contar = [1 for i in range(n)]

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

	def juntar(self, x, y):
		w = self.encontrar_raiz(x)
		z = self.encontrar_raiz(y)
		self.parent[z] = w
		self.contar[w] += self.contar[z]

	def misma_componente(self, x, y):
		return self.encontrar_raiz(x) == self.encontrar_raiz(y)

	def nodos_componente(self, x):
		z = self.encontrar_raiz(x)
		return self.contar[z]
T = int(input())
for i in range(T):
	(n, m) = [int(e) for e in input().split()]
	D = DisjointSetUnion(n)
	repetidas = 0
	for edge in range(m):
		(A, B) = [int(e) - 1 for e in input().split()]
		if not D.misma_componente(A, B):
			D.juntar(A, B)
		else:
			repetidas += 1
	componentes = set([])
	tamanio = 0
	elementosComponente = []
	for e in range(n):
		padreNodo = D.encontrar_raiz(e)
		componentes |= set([padreNodo])
		if tamanio != len(componentes):
			tamanio = len(componentes)
			elementosComponente += [D.nodos_componente(padreNodo)]
	elementosComponente.sort(reverse=True)
	calculos = [0 for i in range(elementosComponente[0] + 2)]
	for i in range(2, elementosComponente[0] + 2):
		calculos[i] = i * (i - 1) + calculos[i - 1]
	respuesta = 0
	actual = 0
	for i in range(len(elementosComponente)):
		val = elementosComponente[i]
		if val > 1:
			respuesta += actual * (val - 1) + calculos[val]
			actual += calculos[val] - calculos[val - 1]
	respuesta += actual * repetidas
	print(respuesta)


import os
import sys
import math

def fact(n):
	if n == 1:
		return 1
	if n <= 0:
		return 0
	return n * fact(n - 1)

def v_idx(v):
	return v - 1

def find_set_iterative(sets, set_pntrs, v):
	nodes_to_update = []
	while set_pntrs[v_idx(v)] != -1:
		nodes_to_update.append(v)
		v = set_pntrs[v_idx(v)]
	for node in nodes_to_update:
		set_pntrs[v_idx(node)] = v
	return v

def union_(spntr1, spntr2, sets, set_pntrs):
	sets[v_idx(spntr2)] = sets[v_idx(spntr2)].union(sets[v_idx(spntr1)])
	set_parent(spntr1, spntr2, set_pntrs)

def union(e, sets, set_pntrs):
	if len(sets[v_idx(e[0])]) <= len(sets[v_idx(e[1])]):
		min_v = e[0]
		max_v = e[1]
	else:
		min_v = e[1]
		max_v = e[0]
	union_(min_v, max_v, sets, set_pntrs)

def is_parent(spntr, set_pntrs):
	if set_pntrs[v_idx(spntr)] == -1:
		return True
	else:
		return False

def set_parent(spntr1, spntr2, set_pntrs):
	set_pntrs[v_idx(spntr1)] = spntr2

def swap(sets, cc_edge_counts, i, j):
	tmp = sets[i]
	sets[i] = sets[j]
	sets[j] = tmp
	tmp = cc_edge_counts[i]
	cc_edge_counts[i] = cc_edge_counts[j]
	cc_edge_counts[j] = tmp

def partition2(sets, cc_edge_counts, start, end):
	swap_idx = end
	for i in range(end - 1, start - 1, -1):
		if len(sets[i]) > len(sets[end]):
			swap_idx -= 1
			if i < swap_idx:
				swap(sets, cc_edge_counts, i, swap_idx)
	swap(sets, cc_edge_counts, swap_idx, end)
	return swap_idx

def quicksort(sets, cc_edge_counts, start, end):
	if start < end and start >= 0:
		k = partition2(sets, cc_edge_counts, start, end)
		quicksort(sets, cc_edge_counts, start, k - 1)
		quicksort(sets, cc_edge_counts, k + 1, end)

class Heap:

	def __init__(self):
		self.size = 0
		self.heap = []

	def get_size(self):
		return self.size

	def get_parent_(self, index):
		if index <= 0:
			return None
		p = int(math.ceil(float(index) / 2) - 1)
		return p

	def get_left_(self, index):
		l = 2 * index + 1
		if l < self.size:
			return l
		else:
			return None

	def get_right_(self, index):
		r = 2 * (index + 1)
		if r < self.size:
			return r
		else:
			return None

	def swap_(self, i, j):
		tmp = self.heap[i]
		self.heap[i] = self.heap[j]
		self.heap[j] = tmp

	def print_heap(self):
		for i in self.heap:
			print(i)

	def pop(self):
		if self.size == 0:
			return None
		self.swap_(0, self.size - 1)
		s = self.heap.pop()
		self.size -= 1
		self.heapify(0)
		return s

class MaxHeap(Heap):

	def __init__(self):
		Heap.__init__(self)

	def push(self, s):
		s_idx = self.size
		self.size += 1
		self.heap.append(s)
		parent_idx = self.get_parent_(s_idx)
		while parent_idx is not None and len(self.heap[parent_idx]) < len(s):
			self.swap_(parent_idx, s_idx)
			s_idx = parent_idx
			parent_idx = self.get_parent_(s_idx)

	def heapify(self, index):
		l = self.get_left_(index)
		r = self.get_right_(index)
		if l is None and r is None:
			return
		elif r is None:
			swap_idx = l
		elif l is None:
			swap_idx = r
		elif len(self.heap[l]) >= len(self.heap[r]):
			swap_idx = l
		else:
			swap_idx = r
		if len(self.heap[swap_idx]) > len(self.heap[index]):
			self.swap_(index, swap_idx)
			self.heapify(swap_idx)
q = int(input())
for q_itr in range(q):
	nm = input().split()
	n = int(nm[0])
	m = int(nm[1])
	sets = []
	set_pntrs = []
	result = 0
	redundant_edges = 0
	for i in range(1, n + 1):
		sets.append(set([i]))
		set_pntrs.append(-1)
	for _ in range(m):
		(u, v) = [int(i) for i in input().rstrip().split()]
		u_index = find_set_iterative(sets, set_pntrs, u)
		v_index = find_set_iterative(sets, set_pntrs, v)
		if sets[v_idx(u_index)] is not sets[v_idx(v_index)]:
			union((u_index, v_index), sets, set_pntrs)
		else:
			redundant_edges += 1
	heap = MaxHeap()
	for i in range(n):
		if set_pntrs[i] == -1:
			heap.push(sets[i])
	num_cc = heap.get_size()
	total_friends = 0
	friendship = 0
	while heap.get_size() > 0:
		s = heap.pop()
		for i in range(2, len(s) + 1):
			result += i * (i - 1) + friendship
		friendship += len(s) * (len(s) - 1)
	result += friendship * redundant_edges
	print(result)


def read_test_case():
	(n, m) = (int(i) for i in input().split())
	adj_list = [[] for i in range(n)]
	for i in range(m):
		(v, u) = (int(i) - 1 for i in input().split())
		adj_list[u].append(v)
		adj_list[v].append(u)
	return (n, m, adj_list)

def dfs(adj_list, visited, v):
	(stack, cnt, visited[v]) = ([v], 1, True)
	while len(stack) > 0:
		v = stack.pop()
		for u in adj_list[v]:
			if not visited[u]:
				visited[u] = True
				stack.append(u)
				cnt += 1
	return cnt

def connected_components(n, adj_list):
	visited = [False] * n
	sizes = []
	for v in range(n):
		if not visited[v]:
			sizes.append(dfs(adj_list, visited, v))
	return sizes
for t in range(int(input())):
	(n, m, adj_list) = read_test_case()
	(total, friends, friendships) = (0, 0, 0)
	for size in sorted(connected_components(n, adj_list), reverse=True):
		for i in range(2, size + 1):
			friends += i * (i - 1) - (i - 1) * (i - 2)
			total += friends
			friendships += 1
	total += (m - friendships) * friends
	print(total)


def getParent(n):
	while parent[n] != 0:
		n = parent[n]
	return n

def comb(x):
	return int(x * (x - 1))
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	parent = [0 for _ in range(0, n + 1)]
	size = [1 for _ in range(0, n + 1)]
	fcount = 0
	for i in range(m):
		(f, t) = map(int, input().split())
		fp = getParent(f)
		tp = getParent(t)
		if fp != tp:
			size[fp] += size[tp]
			size[tp] = 1
			parent[tp] = fp
	tsize = []
	for i in size:
		if i > 1:
			tsize.append(i)
	tsize.sort(reverse=True)
	acum = 0
	for i in tsize:
		m -= i - 1
		thisTreeVal = int(i * (i * i - 1) // 3)
		lastTreeVal = i * (i - 1)
		acum += thisTreeVal + lastTreeVal * m
	print(int(acum))


for q in range(int(input())):
	(n, m) = map(int, input().split())
	g = {}
	for i in range(1, n + 1):
		g[i] = []
	for i in range(m):
		(u, v) = map(int, input().split())
		g[u].append(v)
		g[v].append(u)
	visited = [-1] * (n + 1)
	S = 0
	X = 0
	red = 0
	comps = []
	for i in range(1, n + 1):
		if visited[i] == -1:
			Q = [i]
			visited[i] = i
			k = 1
			while len(Q) > 0:
				h = Q.pop(0)
				for to in g[h]:
					if visited[to] == -1:
						visited[to] = h
						Q.append(to)
						k += 1
					elif to != visited[h]:
						red += 1
			if k != 1:
				comps.append(k)
	comps = sorted(comps, reverse=True)
	for k in comps:
		T = k * (k + 1) * (k - 1) // 3
		S = S + T + (k - 1) * X
		X = X + k * (k - 1)
	red = red // 2
	S = S + red * X
	print(S)


def grow(n):
	res = 0
	for i in range(1, n):
		res += i * (i + 1)
	return res

def mark(x):
	z = x
	while z:
		z = z[0]
	if x is not z:
		x[0] = z
	return z

def mark2(x):
	z = x
	while z and type(z) == list:
		z = z[0]
	if x is not z:
		x[0] = z
	return z
T = int(input())
for t in range(T):
	(n, m) = map(int, input().split())
	work = [[] for i in range(n)]
	lost = 0
	for i in range(m):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		mu = mark(work[u])
		mv = mark(work[v])
		if mu is not mv:
			mu.append(mv)
		else:
			lost += 1
	no = 1
	dic = {}
	for i in range(n):
		z = mark2(work[i])
		if not z:
			z.append(no)
			z = no
			no += 1
			dic[z] = 1
		else:
			dic[z] += 1
	res = 0
	cur = 0
	for v in sorted(dic.values(), reverse=True):
		res += grow(v) + (v - 1) * cur
		cur += v * (v - 1)
	res += lost * cur
	print(res)


from collections import defaultdict, deque
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	graph = defaultdict(list)
	for k in range(m):
		(a, b) = map(lambda x: int(x) - 1, input().split())
		graph[a].append(b)
		graph[b].append(a)
	connected_component = [-1 for k in range(n)]
	size_cc = [0] * n
	bonus_edge = 0
	ind_connected_component = -1
	for k in range(n):
		if connected_component[k] == -1:
			ind_connected_component += 1
			connected_component[k] = ind_connected_component
			size_cc[ind_connected_component] = 1
			queue = deque()
			queue.append(k)
			while queue:
				current_node = queue.popleft()
				for neigh in graph[current_node]:
					if connected_component[neigh] == -1:
						queue.appendleft(neigh)
						size_cc[ind_connected_component] += 1
						connected_component[neigh] = ind_connected_component
					else:
						bonus_edge += 1
				for neigh in graph[current_node]:
					graph[neigh].remove(current_node)
				graph[current_node] = []
	size_cc_sorted = sorted(size_cc, reverse=1)
	current_total = 0
	sum_total = 0
	for s in size_cc_sorted:
		for link in range(1, s):
			current_total -= link * (link - 1)
			current_total += link * (link + 1)
			sum_total += current_total
	sum_total += current_total * bonus_edge
	print(sum_total)


def read_test_case():
	(n, m) = (int(i) for i in input().split())
	adj_list = [[] for i in range(n)]
	for i in range(m):
		(v, u) = (int(i) - 1 for i in input().split())
		adj_list[u].append(v)
		adj_list[v].append(u)
	return (n, m, adj_list)

def dfs(adj_list, visited, v):
	(stack, cnt, visited[v]) = ([v], 1, True)
	while len(stack) > 0:
		v = stack.pop()
		for u in adj_list[v]:
			if not visited[u]:
				visited[u] = True
				stack.append(u)
				cnt += 1
	return cnt

def connected_components(n, adj_list):
	visited = [False] * n
	sizes = []
	for v in range(n):
		if not visited[v]:
			sizes.append(dfs(adj_list, visited, v))
	return sizes
for t in range(int(input())):
	(n, m, adj_list) = read_test_case()
	(total, friends, friendships) = (0, 0, 0)
	for size in sorted(connected_components(n, adj_list), reverse=True):
		for i in range(2, size + 1):
			friends += i * (i - 1) - (i - 1) * (i - 2)
			total += friends
			friendships += 1
	total += (m - friendships) * friends
	print(total)


def read_test_case():
	(n, m) = (int(i) for i in input().split())
	adj_list = [[] for i in range(n)]
	for i in range(m):
		(v, u) = (int(i) - 1 for i in input().split())
		adj_list[u].append(v)
		adj_list[v].append(u)
	return (n, m, adj_list)

def dfs(adj_list, visited, v):
	(stack, cnt, visited[v]) = ([v], 1, True)
	while len(stack) > 0:
		v = stack.pop()
		for u in adj_list[v]:
			if not visited[u]:
				visited[u] = True
				stack.append(u)
				cnt += 1
	return cnt

def connected_components(n, adj_list):
	visited = [False] * n
	sizes = []
	for v in range(n):
		if not visited[v]:
			sizes.append(dfs(adj_list, visited, v))
	return sizes
for t in range(int(input())):
	(n, m, adj_list) = read_test_case()
	(total, friends, friendships) = (0, 0, 0)
	for size in sorted(connected_components(n, adj_list), reverse=True):
		for i in range(2, size + 1):
			friends += i * (i - 1) - (i - 1) * (i - 2)
			total += friends
			friendships += 1
	total += (m - friendships) * friends
	print(total)


def read_test_case():
	(n, m) = (int(i) for i in input().split())
	adj_list = [[] for i in range(n)]
	for i in range(m):
		(v, u) = (int(i) - 1 for i in input().split())
		adj_list[u].append(v)
		adj_list[v].append(u)
	return (n, m, adj_list)

def dfs(adj_list, visited, v):
	(stack, cnt, visited[v]) = ([v], 1, True)
	while len(stack) > 0:
		v = stack.pop()
		for u in adj_list[v]:
			if not visited[u]:
				visited[u] = True
				stack.append(u)
				cnt += 1
	return cnt

def connected_components(n, adj_list):
	visited = [False] * n
	sizes = []
	for v in range(n):
		if not visited[v]:
			sizes.append(dfs(adj_list, visited, v))
	return sizes
for t in range(int(input())):
	(n, m, adj_list) = read_test_case()
	(total, friends, friendships) = (0, 0, 0)
	for size in sorted(connected_components(n, adj_list), reverse=True):
		for i in range(2, size + 1):
			friends += i * (i - 1) - (i - 1) * (i - 2)
			total += friends
			friendships += 1
	total += (m - friendships) * friends
	print(total)


def read_test_case():
	(n, m) = (int(i) for i in input().split())
	adj_list = [[] for i in range(n)]
	for i in range(m):
		(v, u) = (int(i) - 1 for i in input().split())
		adj_list[u].append(v)
		adj_list[v].append(u)
	return (n, m, adj_list)

def dfs(adj_list, visited, v):
	(stack, cnt, visited[v]) = ([v], 1, True)
	while len(stack) > 0:
		v = stack.pop()
		for u in adj_list[v]:
			if not visited[u]:
				visited[u] = True
				stack.append(u)
				cnt += 1
	return cnt

def connected_components(n, adj_list):
	visited = [False] * n
	sizes = []
	for v in range(n):
		if not visited[v]:
			sizes.append(dfs(adj_list, visited, v))
	return sizes
for t in range(int(input())):
	(n, m, adj_list) = read_test_case()
	(total, friends, friendships) = (0, 0, 0)
	for size in sorted(connected_components(n, adj_list), reverse=True):
		for i in range(2, size + 1):
			friends += i * (i - 1) - (i - 1) * (i - 2)
			total += friends
			friendships += 1
	total += (m - friendships) * friends
	print(total)


import os
import sys

class UnionFind:

	def __init__(self, n):
		self.arr = []
		self.size = n
		for i in range(n):
			self.arr.append([i, 1])

	def unite(self, x, y):
		a = self.find(x)
		b = self.find(y)
		if a != b:
			if self.arr[a][1] < self.arr[b][1]:
				(a, b) = (b, a)
			self.arr[b][0] = a
			self.arr[a][1] += self.arr[b][1]

	def find(self, x):
		r = x
		while self.arr[r][0] != r:
			r = self.arr[r][0]
		z = x
		while self.arr[z][0] != z:
			w = z
			z = self.arr[z][0]
			self.arr[w][0] = r
		return r

def determineTotalValue(UF, m):
	totalSum = 0
	currentSums = []
	uniqueTrees = []
	for i in range(len(UF.arr)):
		if i == UF.arr[i][0]:
			uniqueTrees.append(UF.arr[i][1])
	uniqueTrees.sort()
	for tree in uniqueTrees:
		currentSums.append(tree * (tree - 1))
	redundant = m - (sum(uniqueTrees) - len(uniqueTrees))
	totalSum += redundant * sum(currentSums)
	for i in range(len(uniqueTrees)):
		while uniqueTrees[i] != 1:
			totalSum += sum(currentSums)
			uniqueTrees[i] -= 1
			currentSums[i] = uniqueTrees[i] * (uniqueTrees[i] - 1)
	return totalSum

def valueOfFriendsship(n, m, friendships):
	UF = UnionFind(n)
	for i in range(len(friendships)):
		UF.unite(friendships[i][0], friendships[i][1])
	return determineTotalValue(UF, m)
q = int(input())
for q_itr in range(q):
	nm = input().split()
	n = int(nm[0])
	m = int(nm[1])
	friendships = []
	for _ in range(m):
		f = list(map(int, input().rstrip().split()))
		friendships.append([f[0] - 1, f[1] - 1])
	result = valueOfFriendsship(n, m, friendships)
	print(str(result))


import os
import sys

class UnionFind:

	def __init__(self, n):
		self.arr = []
		self.size = n
		for i in range(n):
			self.arr.append([i, 1])

	def unite(self, x, y):
		a = self.find(x)
		b = self.find(y)
		if a != b:
			if self.arr[a][1] < self.arr[b][1]:
				(a, b) = (b, a)
			self.arr[b][0] = a
			self.arr[a][1] += self.arr[b][1]

	def find(self, x):
		r = x
		while self.arr[r][0] != r:
			r = self.arr[r][0]
		z = x
		while self.arr[z][0] != z:
			w = z
			z = self.arr[z][0]
			self.arr[w][0] = r
		return r

def determineTotalValue(UF, m):
	totalSum = 0
	currentSums = []
	uniqueTrees = []
	for i in range(len(UF.arr)):
		if i == UF.arr[i][0]:
			uniqueTrees.append(UF.arr[i][1])
	uniqueTrees.sort()
	for tree in uniqueTrees:
		currentSums.append(tree * (tree - 1))
	redundant = m - (sum(uniqueTrees) - len(uniqueTrees))
	totalSum += redundant * sum(currentSums)
	for i in range(len(uniqueTrees)):
		while uniqueTrees[i] != 1:
			totalSum += sum(currentSums)
			uniqueTrees[i] -= 1
			currentSums[i] = uniqueTrees[i] * (uniqueTrees[i] - 1)
	return totalSum

def valueOfFriendsship(n, m, friendships):
	UF = UnionFind(n)
	for i in range(len(friendships)):
		UF.unite(friendships[i][0], friendships[i][1])
	return determineTotalValue(UF, m)
q = int(input())
for q_itr in range(q):
	nm = input().split()
	n = int(nm[0])
	m = int(nm[1])
	friendships = []
	for _ in range(m):
		f = list(map(int, input().rstrip().split()))
		friendships.append([f[0] - 1, f[1] - 1])
	result = valueOfFriendsship(n, m, friendships)
	print(str(result))


import os
import sys

class UnionFind:

	def __init__(self, n):
		self.arr = []
		self.size = n
		for i in range(n):
			self.arr.append([i, 1])

	def unite(self, x, y):
		a = self.find(x)
		b = self.find(y)
		if a != b:
			if self.arr[a][1] < self.arr[b][1]:
				(a, b) = (b, a)
			self.arr[b][0] = a
			self.arr[a][1] += self.arr[b][1]

	def find(self, x):
		r = x
		while self.arr[r][0] != r:
			r = self.arr[r][0]
		z = x
		while self.arr[z][0] != z:
			w = z
			z = self.arr[z][0]
			self.arr[w][0] = r
		return r

def determineTotalValue(UF, m):
	totalSum = 0
	currentSum = 0
	uniqueTrees = []
	for i in range(len(UF.arr)):
		if i == UF.arr[i][0]:
			uniqueTrees.append(UF.arr[i][1])
	uniqueTrees.sort()
	for tree in uniqueTrees:
		currentSum += tree * (tree - 1)
	redundant = m - (sum(uniqueTrees) - len(uniqueTrees))
	totalSum += redundant * currentSum
	for i in range(len(uniqueTrees)):
		while uniqueTrees[i] != 1:
			totalSum += currentSum
			uniqueTrees[i] -= 1
			currentSum += -2 * uniqueTrees[i]
	return totalSum

def valueOfFriendsship(n, m, friendships):
	UF = UnionFind(n)
	for i in range(len(friendships)):
		UF.unite(friendships[i][0], friendships[i][1])
	return determineTotalValue(UF, m)
q = int(input())
for q_itr in range(q):
	nm = input().split()
	n = int(nm[0])
	m = int(nm[1])
	friendships = []
	for _ in range(m):
		f = list(map(int, input().rstrip().split()))
		friendships.append([f[0] - 1, f[1] - 1])
	result = valueOfFriendsship(n, m, friendships)
	print(str(result))


import os
import sys

class UnionFind:

	def __init__(self, n):
		self.arr = []
		self.size = n
		for i in range(n):
			self.arr.append([i, 1])

	def unite(self, x, y):
		a = self.find(x)
		b = self.find(y)
		if a != b:
			if self.arr[a][1] < self.arr[b][1]:
				(a, b) = (b, a)
			self.arr[b][0] = a
			self.arr[a][1] += self.arr[b][1]

	def find(self, x):
		r = x
		while self.arr[r][0] != r:
			r = self.arr[r][0]
		z = x
		while self.arr[z][0] != z:
			w = z
			z = self.arr[z][0]
			self.arr[w][0] = r
		return r

def determineTotalValue(UF, m):
	totalSum = 0
	currentSum = 0
	uniqueTrees = []
	for i in range(len(UF.arr)):
		if i == UF.arr[i][0]:
			uniqueTrees.append(UF.arr[i][1])
	uniqueTrees.sort()
	for tree in uniqueTrees:
		currentSum += tree * (tree - 1)
	redundant = m - (sum(uniqueTrees) - len(uniqueTrees))
	totalSum += redundant * currentSum
	for i in range(len(uniqueTrees)):
		while uniqueTrees[i] != 1:
			totalSum += currentSum
			uniqueTrees[i] -= 1
			currentSum += -2 * uniqueTrees[i]
	return totalSum

def valueOfFriendsship(n, m, friendships):
	UF = UnionFind(n)
	for i in range(len(friendships)):
		UF.unite(friendships[i][0], friendships[i][1])
	return determineTotalValue(UF, m)
q = int(input())
for q_itr in range(q):
	nm = input().split()
	n = int(nm[0])
	m = int(nm[1])
	friendships = []
	for _ in range(m):
		f = list(map(int, input().rstrip().split()))
		friendships.append([f[0] - 1, f[1] - 1])
	result = valueOfFriendsship(n, m, friendships)
	print(str(result))


def grow(n):
	res = 0
	for i in range(1, n):
		res += i * (i + 1)
	return res

def mark(x):
	z = x
	while z:
		z = z[0]
	if x is not z:
		x[0] = z
	return z

def mark2(x):
	z = x
	while z and type(z) == list:
		z = z[0]
	if x is not z:
		x[0] = z
	return z
T = int(input())
for t in range(T):
	(n, m) = map(int, input().split())
	work = [[] for i in range(n)]
	lost = 0
	for i in range(m):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		mu = mark(work[u])
		mv = mark(work[v])
		if mu is not mv:
			mu.append(mv)
		else:
			lost += 1
	no = 1
	dic = {}
	for i in range(n):
		z = mark2(work[i])
		if not z:
			z.append(no)
			z = no
			no += 1
			dic[z] = 1
		else:
			dic[z] += 1
	res = 0
	cur = 0
	for v in sorted(dic.values(), reverse=True):
		res += grow(v) + (v - 1) * cur
		cur += v * (v - 1)
	res += lost * cur
	print(res)


def grow(n):
	res = 0
	for i in range(1, n):
		res += i * (i + 1)
	return res

def mark(x):
	z = x
	while z:
		z = z[0]
	if x is not z:
		x[0] = z
	return z

def mark2(x):
	z = x
	while z and type(z) == list:
		z = z[0]
	if x is not z:
		x[0] = z
	return z
T = int(input())
for t in range(T):
	(n, m) = map(int, input().split())
	work = [[] for i in range(n)]
	lost = 0
	for i in range(m):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		mu = mark(work[u])
		mv = mark(work[v])
		if mu is not mv:
			mu.append(mv)
		else:
			lost += 1
	no = 1
	dic = {}
	for i in range(n):
		z = mark2(work[i])
		if not z:
			z.append(no)
			z = no
			no += 1
			dic[z] = 1
		else:
			dic[z] += 1
	res = 0
	cur = 0
	for v in sorted(dic.values(), reverse=True):
		res += grow(v) + (v - 1) * cur
		cur += v * (v - 1)
	res += lost * cur
	print(res)


def grow(n):
	res = 0
	for i in range(1, n):
		res += i * (i + 1)
	return res

def mark(x):
	z = x
	while z:
		z = z[0]
	if x is not z:
		x[0] = z
	return z

def mark2(x):
	z = x
	while z and type(z) == list:
		z = z[0]
	if x is not z:
		x[0] = z
	return z
T = int(input())
for t in range(T):
	(n, m) = map(int, input().split())
	work = [[] for i in range(n)]
	lost = 0
	for i in range(m):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		mu = mark(work[u])
		mv = mark(work[v])
		if mu is not mv:
			mu.append(mv)
		else:
			lost += 1
	no = 1
	dic = {}
	for i in range(n):
		z = mark2(work[i])
		if not z:
			z.append(no)
			z = no
			no += 1
			dic[z] = 1
		else:
			dic[z] += 1
	res = 0
	cur = 0
	for v in sorted(dic.values(), reverse=True):
		res += grow(v) + (v - 1) * cur
		cur += v * (v - 1)
	res += lost * cur
	print(res)


def grow(n):
	res = 0
	for i in range(1, n):
		res += i * (i + 1)
	return res

def mark(x):
	z = x
	while z:
		z = z[0]
	if x is not z:
		x[0] = z
	return z

def mark2(x):
	z = x
	while z and type(z) == list:
		z = z[0]
	if x is not z:
		x[0] = z
	return z
T = int(input())
for t in range(T):
	(n, m) = map(int, input().split())
	work = [[] for i in range(n)]
	lost = 0
	for i in range(m):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		mu = mark(work[u])
		mv = mark(work[v])
		if mu is not mv:
			mu.append(mv)
		else:
			lost += 1
	no = 1
	dic = {}
	for i in range(n):
		z = mark2(work[i])
		if not z:
			z.append(no)
			z = no
			no += 1
			dic[z] = 1
		else:
			dic[z] += 1
	res = 0
	cur = 0
	for v in sorted(dic.values(), reverse=True):
		res += grow(v) + (v - 1) * cur
		cur += v * (v - 1)
	res += lost * cur
	print(res)