You are given an undirected graph consisting of $n$ vertices and $n$ edges. It is guaranteed that the given graph is connected (i. e. it is possible to reach any vertex from any other vertex) and there are no self-loops and multiple edges in the graph.

Your task is to calculate the number of simple paths of length at least $1$ in the given graph. Note that paths that differ only by their direction are considered the same (i. e. you have to calculate the number of undirected paths). For example, paths $[1, 2, 3]$ and $[3, 2, 1]$ are considered the same.

You have to answer $t$ independent test cases.

Recall that a path in the graph is a sequence of vertices $v_1, v_2, \ldots, v_k$ such that each pair of adjacent (consecutive) vertices in this sequence is connected by an edge. The length of the path is the number of edges in it. A simple path is such a path that all vertices in it are distinct.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of test cases. Then $t$ test cases follow.

The first line of the test case contains one integer $n$ ($3 \le n \le 2 \cdot 10^5$) — the number of vertices (and the number of edges) in the graph.

The next $n$ lines of the test case describe edges: edge $i$ is given as a pair of vertices $u_i$, $v_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$), where $u_i$ and $v_i$ are vertices the $i$-th edge connects. For each pair of vertices $(u, v)$, there is at most one edge between $u$ and $v$. There are no edges from the vertex to itself. So, there are no self-loops and multiple edges in the graph. The graph is undirected, i. e. all its edges are bidirectional. The graph is connected, i. e. it is possible to reach any vertex from any other vertex by moving along the edges of the graph.

It is guaranteed that the sum of $n$ does not exceed $2 \cdot 10^5$ ($\sum n \le 2 \cdot 10^5$).


-----Output-----

For each test case, print one integer: the number of simple paths of length at least $1$ in the given graph. Note that paths that differ only by their direction are considered the same (i. e. you have to calculate the number of undirected paths).


-----Examples-----

Input
3
3
1 2
2 3
1 3
4
1 2
2 3
3 4
4 2
5
1 2
2 3
1 3
2 5
4 3
Output
6
11
18


-----Note-----

Consider the second test case of the example. It looks like that:

There are $11$ different simple paths:

$[1, 2]$;

$[2, 3]$;

$[3, 4]$;

$[2, 4]$;

$[1, 2, 4]$;

$[1, 2, 3]$;

$[2, 3, 4]$;

$[2, 4, 3]$;

$[3, 2, 4]$;

$[1, 2, 3, 4]$;

$[1, 2, 4, 3]$.

Difficulty: HARD
Tags: Tree algorithms

Graph algorithms

Graph traversal

Combinatorics

Starter code:

Solutions:
import sys
try:
	(sys.stdin, sys.stdout) = (open('in.txt', 'r'), open('out.txt', 'w'))
except:
	pass
ii1 = lambda : int(sys.stdin.readline().strip())
is1 = lambda : sys.stdin.readline().strip()
iia = lambda : list(map(int, sys.stdin.readline().strip().split()))
isa = lambda : sys.stdin.readline().strip().split()
mod = int(1000000000.0 + 7)
from collections import *
from math import *
for _ in range(ii1()):
	n = ii1()
	g = [[] for _ in range(n)]
	deg = [0] * n
	count = [1] * n
	for _ in range(n):
		(u, v) = iia()
		u -= 1
		v -= 1
		g[u].append(v)
		g[v].append(u)
		deg[u] += 1
		deg[v] += 1
	dq = deque()
	for i in range(n):
		if deg[i] == 1:
			dq.append((i, -1))
	while dq:
		(v, par) = dq.popleft()
		deg[v] -= 1
		for u in g[v]:
			if u != par and deg[u] != 0:
				count[u] += count[v]
				deg[u] -= 1
				if deg[u] == 1:
					dq.append((u, v))
	res = 0
	for i in range(n):
		if deg[i] != 0:
			res += count[i] * (count[i] - 1) // 2
			res += count[i] * (n - count[i])
	print(res)


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
import threading
sys.setrecursionlimit(300000)
threading.stack_size(10 ** 8)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
for loop in range(int(input())):
	n = int(input())
	lis = [[] for i in range(n)]
	link = [0] * n
	num = [1] * n
	for i in range(n):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		lis[u].append(v)
		lis[v].append(u)
		link[u] += 1
		link[v] += 1
	q = deque([])
	ans = n * (n - 1)
	for i in range(n):
		if link[i] == 1:
			q.append(i)
	while q:
		v = q.popleft()
		link[v] = 0
		for nex in lis[v]:
			if link[nex] != 0:
				num[nex] += num[v]
				link[nex] -= 1
				if link[nex] == 1:
					q.append(nex)
	for i in range(n):
		if link[i] != 0:
			ans -= num[i] * (num[i] - 1) // 2
	print(ans)


from collections import deque
for loop in range(int(input())):
	n = int(input())
	lis = [[] for i in range(n)]
	link = [0] * n
	num = [1] * n
	for i in range(n):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		lis[u].append(v)
		lis[v].append(u)
		link[u] += 1
		link[v] += 1
	q = deque([])
	ans = n * (n - 1)
	for i in range(n):
		if link[i] == 1:
			q.append(i)
	while q:
		v = q.popleft()
		link[v] = 0
		for nex in lis[v]:
			if link[nex] != 0:
				num[nex] += num[v]
				link[nex] -= 1
				if link[nex] == 1:
					q.append(nex)
	for i in range(n):
		if link[i] != 0:
			ans -= num[i] * (num[i] - 1) // 2
	print(ans)


import sys
input = sys.stdin.buffer.readline
t = int(input())
for _ in range(t):
	n = int(input())
	adj = [[] for _ in range(n + 1)]
	indegree = [0 for _ in range(n + 1)]
	for _ in range(n):
		(u, v) = [int(x) for x in input().split()]
		adj[u].append(v)
		adj[v].append(u)
		indegree[u] += 1
		indegree[v] += 1
	visited = [False for _ in range(n + 1)]
	leaves = []
	for node in range(1, n + 1):
		if indegree[node] == 1:
			leaves.append(node)
	subTreeSizes = [1 for _ in range(n + 1)]
	while leaves:
		leaf = leaves.pop()
		visited[leaf] = True
		indegree[leaf] -= 1
		for nex in adj[leaf]:
			if visited[nex] == False:
				subTreeSizes[nex] += subTreeSizes[leaf]
				indegree[nex] -= 1
				if indegree[nex] == 1:
					leaves.append(nex)
	rootsAtCycle = []
	for node in range(1, n + 1):
		if visited[node] == False:
			rootsAtCycle.append(node)
	intraTreeWays = 0
	interTreeWays = 0
	for root in rootsAtCycle:
		size = subTreeSizes[root]
		intraTreeWays += size * (size - 1)
		interTreeWays += 2 * (n - size) * size
	ans = intraTreeWays + interTreeWays
	ans //= 2
	print(ans)


import sys
input = sys.stdin.buffer.readline

def prog():
	for _ in range(int(input())):
		n = int(input())
		adj = [[] for i in range(n + 1)]
		paths = n * (n - 1) // 2
		for i in range(n):
			(u, v) = map(int, input().split())
			adj[u].append(v)
			adj[v].append(u)
		visited = [0] * (n + 1)
		idx_path = [-1] * (n + 1)
		path = []
		s = [1]
		cycle = []
		while s and len(cycle) == 0:
			curr = s[-1]
			if not visited[curr]:
				visited[curr] = 1
				path.append(curr)
				idx_path[curr] = len(path) - 1
				for neighbor in adj[curr]:
					if idx_path[neighbor] == -1 or idx_path[neighbor] == len(path) - 2:
						s.append(neighbor)
					else:
						cycle = path[idx_path[neighbor]:]
			else:
				s.pop()
				if curr == path[-1]:
					idx_path[path.pop()] = -1
		visited = [0] * (n + 1)
		comp_sizes = []
		for i in cycle:
			visited[i] = 1
		for i in cycle:
			s = [i]
			visited[i] = 0
			comp_sizes.append(0)
			while s:
				curr = s[-1]
				if not visited[curr]:
					comp_sizes[-1] += 1
					visited[curr] = 1
					for neighbor in adj[curr]:
						s.append(neighbor)
				else:
					s.pop()
		sz_left = n
		for sz in comp_sizes:
			sz_left -= sz
			paths += sz * sz_left
		print(paths)
prog()


from collections import deque
T = int(input())
r = 1
while r <= T:
	n = int(input())
	neigh = [[] for i in range(n)]
	degree = [0 for i in range(n)]
	visited = [False] * n
	for i in range(n):
		(u, v) = map(int, input().split())
		neigh[u - 1].append(v - 1)
		neigh[v - 1].append(u - 1)
		degree[u - 1] += 1
		degree[v - 1] += 1
	ans = n * (n - 1)
	loop = [True] * n
	for i in range(n):
		if visited[i]:
			continue
		visited[i] = True
		if degree[i] == 1:
			queue = deque()
			queue.append(i)
			while queue:
				j = queue.popleft()
				loop[j] = False
				for ele in neigh[j]:
					degree[ele] -= 1
					if degree[ele] == 1:
						visited[ele] = True
						queue.append(ele)
	visited = [False] * n
	for i in range(n):
		if not loop[i]:
			continue
		temp = neigh[i]
		if len(temp) > 2:
			subbranch = 1
			visited[i] = True
			for ele in temp:
				if loop[ele]:
					continue
				queue = deque([ele])
				visited[ele] = True
				while queue:
					item = queue.popleft()
					subbranch += 1
					for ele in neigh[item]:
						if visited[ele]:
							continue
						visited[ele] = True
						queue.append(ele)
			ans -= subbranch * (subbranch - 1) // 2
	print(ans)
	r += 1


import sys
import threading
from copy import deepcopy
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
sys.setrecursionlimit(201000)
threading.stack_size(16 * 2048 * 2048)

def getnum(index, neigh, visited):
	output = [0, 0]
	endlist = []
	for ele in neigh[index]:
		if visited[ele]:
			continue
		visited[ele] = True
		[end, notend] = getnum(ele, neigh, visited)
		endlist.append(end + 1)
		output[1] += notend + end
	endtot = sum(endlist)
	output[0] += endtot
	notend = 0
	for ele in endlist:
		notend += (endtot - ele) * ele
	output[1] += notend // 2
	return output

def findloop(index, neigh, pre, visited, loop):
	if loop:
		return
	if len(pre) > 1 and index == pre[-2]:
		return
	if visited[index]:
		i = len(pre) - 1
		while pre[i] != index:
			loop.append(pre[i])
			i -= 1
		loop.append(index)
		return
	pre.append(index)
	visited[index] = True
	for ele in neigh[index]:
		findloop(ele, neigh, pre, visited, loop)
		if loop:
			return
	pre.pop()
	visited[index] = False

def main(n, neigh):
	loop = []
	visited = [False] * n
	findloop(0, neigh, [], visited, loop)
	visited = [False] * n
	for loopele in loop:
		visited[loopele] = True
	endlist = []
	notendlist = []
	m = len(loop)
	for i in range(m):
		if len(neigh[loop[i]]) == 2:
			continue
		[end, notend] = getnum(loop[i], neigh, visited)
		endlist.append(end)
		notendlist.append(notend)
	ans = 0
	ans += sum(notendlist)
	ans += m * (m - 1)
	tot = sum(endlist)
	for ele in endlist:
		ans += ele * (2 * m - 1)
		ans += (tot - ele) * ele
	return ans

def solve():
	T = int(input())
	r = 1
	while r <= T:
		n = int(input())
		ans = 0
		neigh = [[] for i in range(n)]
		for i in range(n):
			(p, q) = map(int, input().split())
			neigh[p - 1].append(q - 1)
			neigh[q - 1].append(p - 1)
		ans = main(n, neigh)
		print(ans)
		r += 1
threading.Thread(target=solve).start()


from sys import stdin, stdout
import collections, heapq, bisect, math
input = stdin.readline

def rint():
	return int(input())

def rstr():
	return input().strip()

def rlstr():
	return list(input().strip().split())

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

def main():
	n = rint()
	graph = collections.defaultdict(set)
	queue = collections.deque()
	count = [1] * n
	res = 0
	for _ in range(n):
		(u, v) = rlint()
		u -= 1
		v -= 1
		graph[u].add(v)
		graph[v].add(u)
	for i in range(n):
		if len(graph[i]) == 1:
			queue.append(i)
	while queue:
		u = queue.popleft()
		p = graph[u].pop()
		graph[p].remove(u)
		count[p] += count[u]
		count[u] = 0
		if len(graph[p]) == 1:
			queue.append(p)
	for i in range(n):
		res += count[i] * (count[i] - 1) // 2 + count[i] * (n - count[i])
	print(res)
for _ in range(rint()):
	main()


from collections import defaultdict

def dfs(i):
	global v
	e = [i]
	while e != []:
		x = e.pop(0)
		v[x] = 1
		for i in d[x]:
			if v[i] == -1:
				v[i] = 1
				e.append(i)
for _ in range(int(input())):
	n = int(input())
	d = defaultdict(set)
	for _ in range(n):
		(a, b) = map(int, input().split())
		d[a].add(b)
		d[b].add(a)
	q = []
	for i in range(n + 1):
		if len(d[i]) == 1:
			q.append(i)
	v = [1] * (n + 1)
	v[0] = 0
	while q != []:
		p = q.pop()
		r = d[p].pop()
		v[r] += v[p]
		v[p] = 0
		d[r].remove(p)
		if len(d[r]) == 1:
			q.append(r)
	an = 0
	for i in v:
		an += i * (i - 1) // 2
		an += i * (n - i)
	print(an)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline()

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

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

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

def print_list(l):
	print(' '.join(map(str, l)))
from collections import defaultdict as dc

def find_circle(edge, n):
	father = [0] * (n + 1)
	deep = [0] * (n + 1)
	now = [1]
	k = 1
	while now:
		nex = []
		for node in now:
			for child in edge[node]:
				if child != father[node]:
					if father[child] > 0:
						circle = [child]
						(a, b) = (father[child], node)
						for _ in range(k - deep[a] - 1):
							circle.append(b)
							b = father[b]
						while a != b:
							circle.append(a)
							circle.append(b)
							(a, b) = (father[a], father[b])
						circle.append(a)
						return circle
					father[child] = node
					deep[child] = k
					nex.append(child)
		now = nex
		k += 1
for _ in range(N()):
	n = N()
	edge = dc(list)
	for _ in range(n):
		(u, v) = RL()
		edge[u].append(v)
		edge[v].append(u)
	circle = find_circle(edge, n)
	n_child = [0] * (n + 1)
	for node in circle:
		n_child[node] = 1
	for root in circle:
		now = [root]
		while now:
			node = now.pop()
			for child in edge[node]:
				if n_child[child] == 0:
					n_child[child] = 1
					n_child[root] += 1
					now.append(child)
	res = n * (n - 1)
	for node in circle:
		res += n_child[node] * (n - n_child[node])
	print(res >> 1)


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log, ceil
from collections import defaultdict as dd
from collections import Counter as cc
from bisect import bisect_left as bl
from bisect import bisect_right as br
sys.setrecursionlimit(100000000)
intinp = lambda : int(input().strip())
stripinp = lambda : input().strip()
fltarr = lambda : list(map(float, input().strip().split()))
intarr = lambda : list(map(int, input().strip().split()))
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
MOD = 1000000007
num_cases = intinp()
for _ in range(num_cases):
	n = intinp()
	graph = {}
	counts = {}
	for _ in range(n):
		(a, b) = intarr()
		graph.setdefault(a, set())
		graph.setdefault(b, set())
		counts.setdefault(a, 1)
		counts.setdefault(b, 1)
		graph[a].add(b)
		graph[b].add(a)
	leafs = list((x for x in graph if len(graph[x]) == 1))
	notcycle = set()
	while leafs:
		node = leafs.pop()
		notcycle.add(node)
		for adj in graph[node]:
			graph[adj].remove(node)
			counts[adj] += counts[node]
			if len(graph[adj]) == 1:
				leafs.append(adj)
	ans = 0
	for node in counts:
		if node in notcycle:
			continue
		cnt = counts[node]
		ans += cnt * (cnt - 1) // 2 + cnt * (n - cnt)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	graph = {node: [] for node in range(n)}
	ans = 0
	for edge in range(n):
		(x, y) = map(int, input().split())
		graph[x - 1].append(y - 1)
		graph[y - 1].append(x - 1)
	count = [1 for i in range(n)]
	leaves = []
	for node in range(n):
		if len(graph[node]) == 1:
			leaves.append(node)
	while leaves:
		leaf = leaves.pop()
		neighbor = graph[leaf].pop()
		graph[neighbor].pop(graph[neighbor].index(leaf))
		count[neighbor] += count[leaf]
		count[leaf] = 0
		if len(graph[neighbor]) == 1:
			leaves.append(neighbor)
	for node in range(n):
		ans += count[node] * (n - count[node])
		ans += count[node] * (count[node] - 1) // 2
	print(ans)


import sys, math
import io, os
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
from itertools import permutations, combinations

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

def mdata():
	return list(map(int, data().split()))

def outl(var):
	sys.stdout.write(' '.join(map(str, var)) + '\n')

def out(var):
	sys.stdout.write(str(var) + '\n')
INF = float('inf')
mod = 998244353

def dfs(graph, start=0):
	visited = [False] * n
	par = [0] * n
	stack = [start]
	while stack:
		start = stack.pop()
		if not visited[start]:
			visited[start] = True
			for child in graph[start]:
				if child != par[start]:
					stack.append(child)
					par[child] = start
		else:
			v = start
			cycle = []
			while par[v] != start:
				cycle.append(v)
				v = par[v]
			cycle.append(v)
			break
	return cycle

def dfs1(graph, start):
	cnt = 0
	stack = [start]
	s = set()
	while stack:
		start = stack.pop()
		cnt += 1
		for child in graph[start]:
			if child not in cycle and child not in s:
				stack.append(child)
				s.add(child)
	return cnt
for t in range(int(data())):
	n = int(data())
	graph = [[] for i in range(n)]
	for i in range(n):
		(u, v) = mdata()
		graph[u - 1].append(v - 1)
		graph[v - 1].append(u - 1)
	cycle = set(dfs(graph, 0))
	ans = n * (n - 1)
	for i in cycle:
		k = dfs1(graph, i)
		ans -= k * (k - 1) // 2
	out(ans)


import sys, math, itertools
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush, heapify, nlargest
from copy import deepcopy
mod = 10 ** 9 + 7
INF = float('inf')

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

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

def inpl_1():
	return list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))
for _ in range(inp()):
	n = inp()
	g = [[] for _ in range(n)]
	num = [0] * n
	for i in range(n):
		(a, b) = inpl_1()
		g[a].append(b)
		g[b].append(a)
		num[a] += 1
		num[b] += 1
	cnt = [1] * n
	seen = [False] * n
	q = deque()
	for i in range(n):
		if len(g[i]) == 1:
			q.append(i)
			cnt[i] = 1
	while q:
		now = q.popleft()
		seen[now] = True
		for nx in g[now]:
			if seen[nx]:
				continue
			cnt[nx] += cnt[now]
			cnt[now] = 0
			num[nx] -= 1
			if num[nx] == 1:
				q.append(nx)
	res = 0
	for i in range(n):
		res += cnt[i] * (cnt[i] - 1) // 2
		res += cnt[i] * (n - cnt[i])
	print(res)


import queue

def number_of_simple_path(g, n):
	leafs = queue.Queue()
	for i in range(n):
		if len(g[i]) == 1:
			leafs.put(i)
	val = [1] * n
	while leafs.empty() != True:
		v = leafs.get()
		to = g[v].pop()
		val[to] += val[v]
		val[v] = 0
		g[v].clear()
		g[to].remove(v)
		if len(g[to]) == 1:
			leafs.put(to)
	res = 0
	for i in range(n):
		val_i = val[i]
		res += val_i * (val_i - 1) // 2 + val_i * (n - val_i)
	return res

def main():
	t = int(input())
	for i in range(t):
		n = int(input())
		g = [set() for _ in range(n)]
		for j in range(n):
			(x, y) = map(int, input().split())
			x -= 1
			y -= 1
			g[x].add(y)
			g[y].add(x)
		n_path = number_of_simple_path(g, n)
		print(n_path)
main()


adj = []

def dfs(n, v_):
	par = [-1] * n
	st = [v_]
	par[v_] = -2
	a = -3
	pa = -3
	while st:
		v = st.pop()
		for vv in adj[v]:
			if vv == par[v]:
				continue
			if par[vv] == -1:
				par[vv] = v
				st.append(vv)
			else:
				a = vv
				pa = v
				st = []
				break
	assert a != -3
	spoke = {a}
	vvv = a
	while True:
		vvv = par[vvv]
		if vvv == -2:
			break
		spoke.add(vvv)
	fnd = [0] * n
	vvv = pa
	while True:
		fnd[vvv] = 1
		if vvv in spoke:
			break
		vvv = par[vvv]
		assert vvv != -2
	vvvv = a
	while True:
		fnd[vvvv] = 1
		if vvvv == vvv:
			break
		vvvv = par[vvvv]
		assert vvvv != -2
	return fnd

def dfs2(fnd, v_):
	cnt = 1
	st = [v_]
	while st:
		v = st.pop()
		for vv in adj[v]:
			if not fnd[vv]:
				cnt += 1
				fnd[vv] = 1
				st.append(vv)
	return cnt

def getcd(n):
	_1s = [i for i in range(n) if len(adj[i]) == 1]
	if len(_1s) == 0:
		return ([], 0)
	fnd = dfs(n, _1s[0])
	loops = [i for i in range(n) if fnd[i]]
	k__ = len(loops)
	cd = []
	sub_ = 0
	outs = {}
	for i in loops:
		for vv in adj[i]:
			if not fnd[vv]:
				fnd[vv] = 1
				if i not in outs:
					outs[i] = []
				outs[i].append(vv)
	for ll in outs.values():
		lns = []
		for vv in ll:
			lns.append(dfs2(fnd, vv))
		sub_ += (sum(lns) ** 2 - sum((i * i for i in lns))) // 2
		cd.extend(lns)
	assert sum(cd) + k__ == n
	return (cd, sub_)
import sys
for tt in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	adj = [[] for i in range(n)]
	for i in range(n):
		(a, b) = [int(j) - 1 for j in sys.stdin.readline().split()]
		adj[a].append(b)
		adj[b].append(a)
	(cd, sub_) = getcd(n)
	k = n - sum(cd)
	add_ = sum(cd) ** 2 - sum((i * i for i in cd))
	ans = k * (k - 1) + (n - k) * (2 * k - 1) + sum((cc * (cc - 1) for cc in cd)) // 2 + add_ - sub_
	sys.stdout.write(f'{ans}\n')


import sys
from array import array
import typing as Tp

def input():
	return sys.stdin.buffer.readline().decode('utf-8')

def build_bridge_tree(v_count, edge_count, adj, edge_index):
	from array import array
	from collections import deque
	preorder = [0]
	(parent, order, low) = ([0] + [-1] * v_count, [0] + [-1] * (v_count - 1), [0] * v_count)
	(stack, rem) = ([0], [len(dests) - 1 for dests in adj])
	pre_i = 1
	while stack:
		v = stack.pop()
		while rem[v] >= 0:
			dest = adj[v][rem[v]]
			rem[v] -= 1
			if order[dest] == -1:
				preorder.append(dest)
				order[dest] = low[dest] = pre_i
				parent[dest] = v
				pre_i += 1
				stack.extend((v, dest))
				break
	is_bridge = array('b', [0]) * edge_count
	for v in reversed(preorder):
		for (dest, ei) in zip(adj[v], edge_index[v]):
			if dest != parent[v] and low[v] > low[dest]:
				low[v] = low[dest]
			if dest != parent[v] and order[v] < low[dest]:
				is_bridge[ei] = 1
	bridge_tree = [[] for _ in range(v_count)]
	stack = [0]
	visited = array('b', [1] + [0] * (v_count - 1))
	shrinked = set()
	while stack:
		v = stack.pop()
		dq = deque([v])
		while dq:
			u = dq.popleft()
			for (dest, ei) in zip(adj[u], edge_index[u]):
				if visited[dest]:
					continue
				visited[dest] = 1
				if is_bridge[ei]:
					bridge_tree[v].append(dest)
					bridge_tree[dest].append(v)
					stack.append(dest)
				else:
					shrinked.add(dest)
					shrinked.add(u)
					dq.append(dest)
	return (bridge_tree, shrinked)

def main():
	t = int(input())
	ans = ['-1'] * t
	for ti in range(t):
		n = int(input())
		adj = [[] for _ in range(n)]
		edge_i = [[] for _ in range(n)]
		for (ei, (u, v)) in enumerate((map(int, input().split()) for _ in range(n))):
			adj[u - 1].append(v - 1)
			edge_i[u - 1].append(ei)
			adj[v - 1].append(u - 1)
			edge_i[v - 1].append(ei)
		(bridge_tree, shrinked) = build_bridge_tree(n, n, adj, edge_i)
		res = n * (n - 1)
		visited = [0] * n
		for v in shrinked:
			visited[v] = 1
		for sv in shrinked:
			cnt = 0
			stack = [sv]
			while stack:
				v = stack.pop()
				cnt += 1
				for u in adj[v]:
					if visited[u]:
						continue
					visited[u] = 1
					stack.append(u)
			res -= cnt * (cnt - 1) >> 1
		ans[ti] = str(res)
	sys.stdout.buffer.write(('\n'.join(ans) + '\n').encode('utf-8'))
main()


import sys
input = sys.stdin.buffer.readline
t = int(input())
for _ in range(t):
	n = int(input())
	adj = [set() for __ in range(n + 1)]
	degree = [0 for _ in range(n + 1)]
	for __ in range(n):
		(u, v) = [int(x) for x in input().split()]
		adj[u].add(v)
		adj[v].add(u)
		degree[u] += 1
		degree[v] += 1
	subtreeSize = [1 for _ in range(n + 1)]
	leaves = []
	unvisited = set(range(1, n + 1))
	for i in range(1, n + 1):
		if degree[i] == 1:
			leaves.append(i)
	while leaves:
		leaf = leaves.pop()
		unvisited.remove(leaf)
		nex = next(iter(adj[leaf]))
		adj[nex].remove(leaf)
		subtreeSize[nex] += subtreeSize[leaf]
		if len(adj[nex]) == 1:
			leaves.append(nex)
	ans = 0
	for cycleNode in unvisited:
		subtreeSz = subtreeSize[cycleNode]
		ans += subtreeSz * (subtreeSz - 1) // 2 + subtreeSz * (n - subtreeSz)
	print(ans)


import sys
import threading
from sys import stdin, stdout
sys.setrecursionlimit(10 ** 9)
threading.stack_size(16 * 2048 * 2048)
g_set = set()
g_res = 0

def number_of_simple_paths(n, dic):
	global g_set
	global g_res
	g_set = set()
	g_res = 0
	s = set()
	lst = []
	findloop(1, -1, dic, s, lst)
	if len(g_set) == n:
		return (n - 1) * n
	v_a = []
	for node in g_set:
		lr = dfs(node, -1, dic)
		v_a.append(lr)
	ts = sum(v_a)
	for v in v_a:
		ts -= v
		g_res += v * ts * 2
	return g_res

def findloop(node, pnode, dic, s, lst):
	global g_set
	if node in s:
		return True
	s.add(node)
	lst.append(node)
	for nnode in dic[node]:
		if nnode == pnode:
			continue
		r = findloop(nnode, node, dic, s, lst)
		if r:
			if len(g_set) == 0:
				while lst[-1] != nnode:
					g_set.add(lst.pop())
				g_set.add(lst.pop())
			return True
	lst.pop()
	return False

def dfs(node, pnode, dic):
	global g_set
	global g_res
	count = 1
	c_a = []
	for nnode in dic[node]:
		if nnode == pnode or nnode in g_set:
			continue
		c_a.append(dfs(nnode, node, dic))
		count += c_a[-1]
	tc = count - 1
	lr = 0
	for c in c_a:
		tc -= c
		lr += c * tc
		lr += c
	g_res += lr
	return count

def solve():
	t = int(stdin.readline())
	for _ in range(t):
		n = int(stdin.readline())
		dic = {}
		for _ in range(n):
			(u, v) = map(int, stdin.readline().split())
			if u not in dic:
				dic[u] = []
			if v not in dic:
				dic[v] = []
			dic[u].append(v)
			dic[v].append(u)
		r = number_of_simple_paths(n, dic)
		stdout.write(str(r) + '\n')
threading.Thread(target=solve).start()


import os, sys
from io import BytesIO, IOBase
from copy import deepcopy

def detect_cycle(n, path):
	st = [1]
	visi = [1, 1] + [0] * (n - 1)
	while len(st):
		if not len(path[st[-1]]):
			st.pop()
			continue
		x = path[st[-1]].pop()
		if visi[x]:
			r = st.index(x)
			cy = [st[i] for i in range(r, len(st))]
			return cy
		path[x].remove(st[-1])
		st.append(x)
		visi[x] = 1

def dfs(path, st):
	cou = 0
	while len(st):
		if not len(path[st[-1]]):
			cou += 1
			st.pop()
			continue
		x = path[st[-1]].pop()
		path[x].remove(st[-1])
		st.append(x)
	return cou

def main():
	for _ in range(int(input())):
		n = int(input())
		path = [set() for _ in range(n + 1)]
		for _ in range(n):
			(u1, v1) = map(int, input().split())
			path[u1].add(v1)
			path[v1].add(u1)
		path1 = deepcopy(path)
		cycle = detect_cycle(n, path1)
		for x in range(len(cycle) - 1):
			path[cycle[x]].remove(cycle[x + 1])
			path[cycle[x + 1]].remove(cycle[x])
		path[cycle[0]].remove(cycle[-1])
		path[cycle[-1]].remove(cycle[0])
		ve = [dfs(path, [i]) for i in cycle]
		(ans, su) = (0, sum(ve))
		for i in ve:
			ans += i * (su - i) + i * (i - 1) // 2
		print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import bisect
import collections
import functools
import itertools
import math
import heapq
import random
import string

def repeat(_func=None, *, times=1):

	def decorator(func):

		@functools.wraps(func)
		def wrapper(*args, **kwargs):
			for _ in range(times):
				func(*args, **kwargs)
		return wrapper
	if _func is None:
		return decorator
	else:
		return decorator(_func)

def unpack(func=int):
	return map(func, input().split())

def l_unpack(func=int):
	return list(map(func, input().split()))

def s_unpack(func=int, rev=False):
	return sorted(map(func, input().split()), reverse=rev)

def ml_unpack(n):
	return [int(input()) for _ in range(n)]

def range_n():
	return range(int(input()))

def getint():
	return int(input())

def getmatrix(rows):
	return [list(map(int, input().split())) for _ in range(rows)]

def display_matrix(mat):
	for i in range(len(mat)):
		print(mat[i])

def factor(n):
	d = collections.defaultdict(int)
	while not n % 2:
		d[2] += 1
		n //= 2
	i = 3
	while i * i <= n:
		while not n % i:
			d[i] += 1
			n //= i
		i += 2
	if n > 1:
		d[n] += 1
	return d

class UnionFind:

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

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

	def union(self, x, y):
		x_id = self.find(x)
		y_id = self.find(y)
		if x_id == y_id:
			return
		self.arr[x_id] = y_id

	def count(self):
		hmap = collections.defaultdict(int)
		for node in range(len(self.arr)):
			hmap[self.find(node)] += 1
		return hmap

@repeat(times=getint())
def main():
	n = getint()
	uf = UnionFind(n)
	graph = collections.defaultdict(set)
	for _ in range(n):
		(u, v) = unpack(lambda x: int(x) - 1)
		graph[u].add(v)
		graph[v].add(u)
	leaves = []
	for node in range(n):
		if len(graph[node]) == 1:
			leaves.append((node, node))
	while leaves:
		(leaf, leaf_id) = leaves.pop()
		parent = graph[leaf].pop()
		uf.union(leaf_id, leaf)
		uf.union(leaf_id, parent)
		graph[parent].discard(leaf)
		if len(graph[parent]) == 1:
			leaves.append((parent, leaf_id))
	paths = n * (n - 1)
	hmap = uf.count()
	for node in hmap.values():
		paths -= node * (node - 1) // 2
	print(paths)
main()


import sys
input = sys.stdin.readline
from collections import defaultdict, deque
t = int(input())
for _ in range(t):
	n = int(input())
	ct = [1] * (n + 1)
	deg = [0] * (n + 1)
	d = defaultdict(set)
	for _ in range(n):
		(u, v) = map(int, input().split())
		d[u].add(v)
		d[v].add(u)
		deg[u] += 1
		deg[v] += 1
	hp = deque()
	for i in range(n + 1):
		if deg[i] == 1:
			hp.append(i)
	while hp:
		x = hp.popleft()
		y = d[x].pop()
		d[y].remove(x)
		deg[y] -= 1
		if deg[y] == 1:
			hp.append(y)
		ct[y] += ct[x]
		ct[x] = 0
	ans = 0
	for i in range(1, n + 1):
		ans += ct[i] * (ct[i] - 1) // 2 + ct[i] * (n - ct[i])
	print(ans)


import sys
sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.buffer.readline())

def MI():
	return map(int, sys.stdin.buffer.readline().split())

def MI1():
	return map(int1, sys.stdin.buffer.readline().split())

def LI():
	return list(map(int, sys.stdin.buffer.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def BI():
	return sys.stdin.buffer.readline().rstrip()

def SI():
	return sys.stdin.buffer.readline().rstrip().decode()

def dfs():
	stack = [(0, -1)]
	while stack:
		(u, pu) = stack.pop()
		pp[u] = pu
		for v in to[u]:
			if v == pu:
				continue
			if pp[v] != -10:
				return (u, v)
			stack.append((v, u))
for _ in range(II()):
	n = II()
	to = [[] for _ in range(n)]
	for _ in range(n):
		(u, v) = MI1()
		to[u].append(v)
		to[v].append(u)
	pp = [-10] * n
	(u, v) = dfs()
	cc = [u]
	while u != v:
		u = pp[u]
		cc.append(u)
	cn = len(cc)

	def size(u, i):
		c = u
		stack = [(u, -1)]
		res = 1
		while stack:
			(u, pu) = stack.pop()
			for v in to[u]:
				if v == pu:
					continue
				if u == c and v == cc[i - 1]:
					continue
				if u == c and v == cc[(i + 1) % cn]:
					continue
				stack.append((v, u))
				res += 1
		return res
	ss = []
	for (i, u) in enumerate(cc):
		s = size(u, i)
		ss.append(s)
	ans = n * (n - 1)
	for s in ss:
		ans -= s * (s - 1) // 2
	print(ans)


from bisect import *
from collections import *
from math import gcd, ceil, sqrt, floor, inf
from heapq import *
from itertools import *
from operator import add, mul, sub, xor, truediv, floordiv
from functools import *
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

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

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

def N():
	return int(input())
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
farr = [1]
ifa = []

def fact(x, mod=0):
	if mod:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr) % mod)
	else:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr))
	return farr[x]

def ifact(x, mod):
	global ifa
	ifa.append(pow(farr[-1], mod - 2, mod))
	for i in range(x, 0, -1):
		ifa.append(ifa[-1] * i % mod)
	ifa = ifa[::-1]

def per(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return fact(i) // fact(i - j)
	return farr[i] * ifa[i - j] % mod

def com(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return per(i, j) // fact(j)
	return per(i, j, mod) * ifa[j] % mod

def catalan(n):
	return com(2 * n, n) // (n + 1)

def linc(f, t, l, r):
	while l < r:
		mid = (l + r) // 2
		if t > f(mid):
			l = mid + 1
		else:
			r = mid
	return l

def rinc(f, t, l, r):
	while l < r:
		mid = (l + r + 1) // 2
		if t < f(mid):
			r = mid - 1
		else:
			l = mid
	return l

def ldec(f, t, l, r):
	while l < r:
		mid = (l + r) // 2
		if t < f(mid):
			l = mid + 1
		else:
			r = mid
	return l

def rdec(f, t, l, r):
	while l < r:
		mid = (l + r + 1) // 2
		if t > f(mid):
			r = mid - 1
		else:
			l = mid
	return l

def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def binfun(x):
	c = 0
	for w in arr:
		c += ceil(w / x)
	return c

def lowbit(n):
	return n & -n

def inverse(a, m):
	a %= m
	if a <= 1:
		return a
	return (1 - inverse(m, a) * m) // a % m

class BIT:

	def __init__(self, arr):
		self.arr = arr
		self.n = len(arr) - 1

	def update(self, x, v):
		while x <= self.n:
			self.arr[x] += v
			x += x & -x

	def query(self, x):
		ans = 0
		while x:
			ans += self.arr[x]
			x &= x - 1
		return ans

class DSU:

	def __init__(self, n):
		self.c = [-1] * n

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def find(self, x):
		if self.c[x] < 0:
			return x
		self.c[x] = self.find(self.c[x])
		return self.c[x]

	def union(self, u, v):
		(u, v) = (self.find(u), self.find(v))
		if u == v:
			return False
		if self.c[u] < self.c[v]:
			(u, v) = (v, u)
		self.c[u] += self.c[v]
		self.c[v] = u
		return True

	def size(self, x):
		return -self.c[self.find(x)]

class UFS:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.ranks = [0] * n

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

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			return False
		if self.ranks[pu] >= self.ranks[pv]:
			self.parent[pv] = pu
			if self.ranks[pv] == self.ranks[pu]:
				self.ranks[pu] += 1
		else:
			self.parent[pu] = pv

def Prime(n):
	c = 0
	prime = []
	flag = [0] * (n + 1)
	for i in range(2, n + 1):
		if not flag[i]:
			prime.append(i)
			c += 1
		for j in range(c):
			if i * prime[j] > n:
				break
			flag[i * prime[j]] = prime[j]
			if i % prime[j] == 0:
				break
	return prime

def dij(s, graph):
	d = {}
	d[s] = 0
	heap = [(0, s)]
	seen = set()
	while heap:
		(dis, u) = heappop(heap)
		if u in seen:
			continue
		for v in graph[u]:
			if v not in d or d[v] > d[u] + graph[u][v]:
				d[v] = d[u] + graph[u][v]
				heappush(heap, (d[v], v))
	return d

def GP(it):
	return [[ch, len(list(g))] for (ch, g) in groupby(it)]

class DLN:

	def __init__(self, val):
		self.val = val
		self.pre = None
		self.next = None

@bootstrap
def dfs(u, p):
	path.add(u)
	if u == t:
		yield True
	if len(g[u]) == 1 and p != -1:
		yield False
	for ch in g[u]:
		if ch != p:
			tmp = (yield dfs(ch, u))
			if tmp:
				yield True
			path.remove(ch)
	yield False

@bootstrap
def dfs2(u, p):
	if len(g[u]) == 1 and p != -1:
		cnt[u] = 1
		yield 1
	tmp = 1
	for ch in g[u]:
		if ch != p:
			tmp += (yield dfs2(ch, u))
	cnt[u] = tmp
	yield tmp
t = N()
for i in range(t):
	n = N()
	ans = (n - 1) * n // 2
	g = [[] for i in range(n + 1)]
	uf = UFS(n + 1)
	for i in range(n):
		(u, v) = RL()
		if uf.find(u) != uf.find(v):
			uf.union(u, v)
			g[u].append(v)
			g[v].append(u)
		else:
			r = u
			t = v
	path = set()
	dfs(r, -1)
	path.remove(r)
	path.remove(t)
	cnt = [0] * (1 + n)
	dfs2(r, -1)
	res = []
	for x in path:
		res.append(cnt[x])
	res.sort(reverse=True)
	if res:
		k = res[0] - cnt[t]
		res.append(cnt[t])
		a = cnt[r] - res[0]
		b = cnt[t]
		res = [res[i] - res[i + 1] for i in range(len(res) - 1)]
		ans += a * b + 2 * k + (n - 2 - k) * k + k * (k - 1) // 2
		for x in res:
			ans -= x * (x - 1) // 2
	print(ans)


import sys, os
import heapq, functools, collections
import math, random
from collections import Counter, defaultdict

def solve_(edges, k):
	d = defaultdict(list)
	for (a, b) in edges:
		d[a].append(b)
		d[b].append(a)
	stack = [k]
	visited = {k: None}
	while stack:
		cur = stack.pop()
		for nex in d[cur]:
			if nex in visited:
				if visited[cur] == nex:
					continue
				stack = []
				break
			visited[nex] = cur
			stack.append(nex)
	stack_1 = [cur]
	stack_1_set = set([cur])
	stack_2 = [nex]
	cur = stack_1[0]
	while visited[cur]:
		cur = visited[cur]
		stack_1.append(cur)
		stack_1_set.add(cur)
	cur = stack_2[0]
	while visited[cur]:
		cur = visited[cur]
		stack_2.append(cur)
		if cur in stack_1_set:
			break
	cycle = set(stack_2)
	for x in stack_1:
		if x in cycle:
			break
		cycle.add(x)
	visited = set(cycle)
	res = k * (k - 1)
	for start in cycle:
		stack = d[start]
		count = 0
		while stack:
			cur = stack.pop()
			if cur in cycle:
				continue
			visited.add(cur)
			count += 1
			for nex in d[cur]:
				if nex in visited:
					continue
				stack.append(nex)
				visited.add(nex)
		console(start, count)
		res -= count * (count + 1) // 2
	return res

def console(*args):
	print('\x1b[36m', *args, '\x1b[0m', file=sys.stderr)
	pass
ONLINE_JUDGE = False
if os.path.exists('input.txt'):
	ONLINE_JUDGE = True
if ONLINE_JUDGE:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

	def console(*args):
		pass

def solve(*args):
	if not ONLINE_JUDGE:
		console('----- solving ------')
		console(*args)
		console('----- ------- ------')
	return solve_(*args)
if True:
	inp = iter(sys.stdin.buffer.readlines())
	input = lambda : next(inp)
else:
	input = sys.stdin.buffer.readline
for case_num in range(int(input())):
	nrows = int(input())
	grid = []
	for _ in range(nrows):
		grid.append(list(map(int, input().split())))
	res = solve(grid, nrows)
	print(res)


import sys
input = sys.stdin.readline
import copy
t = int(input())
for tests in range(t):
	n = int(input())
	E = [set() for i in range(n)]
	D = [0] * n
	for i in range(n):
		(x, y) = map(int, input().split())
		x -= 1
		y -= 1
		E[x].add(y)
		E[y].add(x)
		D[x] += 1
		D[y] += 1
	if min(D) == 2:
		print(n * (n - 1))
		continue
	Q = []
	USED = [0] * n
	for i in range(n):
		if D[i] == 1:
			Q.append(i)
			USED[i] = 1
	D2 = [d * 2 for d in D]
	K = [1] * n
	while Q:
		x = Q.pop()
		USED[x] = 1
		for to in E[x]:
			if USED[to] == 0:
				K[to] += K[x]
				D[x] -= 1
				D[to] -= 1
				if D[to] == 1:
					Q.append(to)
	ANS = 0
	for i in range(n):
		k = K[i]
		if USED[i] == 0:
			ANS += (n - k) * k
	USED2 = [0] * n
	K = [1] * n
	for i in range(n):
		if USED[i] == 0:
			for to in E[i]:
				if USED[to] == 0:
					D2[i] -= 1
					D2[to] -= 1
	D2 = [d // 2 for d in D2]
	for i in range(n):
		if USED2[i] == 0 and D2[i] == 1:
			Q2 = [i]
			while Q2:
				x = Q2.pop()
				USED2[x] = 1
				for to in E[x]:
					if USED2[to] == 0:
						if USED[x] == 0 and USED[to] == 0:
							continue
						K[to] += K[x]
						K[x] = 0
						D2[x] -= 1
						D2[to] -= 1
						if D2[to] == 1:
							Q2.append(to)
	for i in range(n):
		if K[i] != 0:
			ANS += K[i] * (K[i] - 1) // 2
	print(ANS)


import sys, os, io
input = sys.stdin.readline
from collections import deque

class LowLink:

	def __init__(self, N, M):
		self.V = N
		self.E = M
		self.edge = [[] for _ in range(self.V)]
		self.edges = [0] * M
		self.visited = [False] * N
		self.parent = [N] * N
		self.order = [N] * N
		self.low = [N] * N

	def add_edges(self, ind=1):
		for i in range(self.E):
			(a, b) = map(int, input().split())
			a -= ind
			b -= ind
			self.edge[a].append(b)
			self.edge[b].append(a)
			self.edges[i] = (a, b)

	def add_edge(self, a, b):
		self.edge[a].append(b)
		self.edge[b].append(a)

	def low_link(self, start):
		self.start = start
		stack = deque([start])
		self.parent[start] = -1
		self.order[start] = 0
		self.cnts = [0] * self.V
		order = 1
		while stack:
			v = stack[-1]
			for u in self.edge[v]:
				if u == self.parent[v]:
					continue
				if self.order[u] < self.order[v]:
					self.low[v] = min(self.low[v], self.order[u])
				elif self.cnts[u] == 0:
					self.order[u] = self.low[u] = order
					self.parent[u] = v
					stack.append(u)
					self.cnts[u] += 1
					order += 1
					break
				elif self.cnts[u] == 1:
					self.low[v] = min(self.low[v], self.low[u])
					self.cnts[u] += 1
			else:
				stack.pop()
		return

	def cycle(self):
		res = [0] * self.V
		for (a, b) in self.edges:
			if G.order[a] > G.order[b]:
				(a, b) = (b, a)
			if G.low[b] <= G.order[a]:
				res[a] = 1
				res[b] = 1
		return res

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = [-1] * n

	def find(self, x):
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
		return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.parents[x] > self.parents[y]:
			(x, y) = (y, x)
		self.parents[x] += self.parents[y]
		self.parents[y] = x

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def roots(self):
		return [i for (i, x) in enumerate(self.parents) if x < 0]

	def members(self, x):
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i) == root]

	def size(self, x):
		return abs(self.parents[self.find(x)])

	def groups(self):
		roots = self.roots()
		r_to_g = {}
		for (i, r) in enumerate(roots):
			r_to_g[r] = i
		groups = [[] for _ in roots]
		for i in range(self.n):
			groups[r_to_g[self.find(i)]].append(i)
		return groups
T = int(input())
ans = [0] * T
for t in range(T):
	n = int(input())
	G = LowLink(n, n)
	G.add_edges(1)
	G.low_link(0)
	cycles = G.cycle()
	uf = UnionFind(n)
	for (a, b) in G.edges:
		if cycles[a] + cycles[b] < 2:
			uf.union(a, b)
	ans[t] = n * (n - 1)
	for r in uf.roots():
		s = uf.size(r)
		ans[t] -= s * (s - 1) // 2
print(*ans, sep='\n')


from collections import deque
for _ in range(int(input())):
	n = int(input())
	G = [[] for _ in range(n)]
	deg = [0] * n
	cnt = [1] * n
	for _ in range(n):
		(i, j) = map(int, input().split())
		i -= 1
		j -= 1
		G[i].append(j)
		G[j].append(i)
		deg[i] += 1
		deg[j] += 1
	q = deque([(i, -1) for i in range(n) if deg[i] == 1])
	while q:
		(i, par) = q.popleft()
		deg[i] -= 1
		for j in G[i]:
			if j != par and deg[j]:
				cnt[j] += cnt[i]
				deg[j] -= 1
				if deg[j] == 1:
					q.append((j, i))
	ans = 0
	for i in range(n):
		if deg[i]:
			ans += cnt[i] * (cnt[i] - 1) // 2
			ans += cnt[i] * (n - cnt[i])
	print(ans)


import sys
import copy
from collections import defaultdict, deque
input = sys.stdin.readline

def dfs(start, graph):
	visited = {start}
	d = deque(graph[start])
	while d:
		v = d.pop()
		visited.add(v)
		d.extend(graph[v] - visited)
	return visited

def find_cycle(start, graph):
	visited = set()
	ograph = copy.deepcopy(graph)
	tree = {}
	d = deque([start])
	while d:
		par = d.pop()
		if par in visited:
			leaf = par
			cycle = [leaf]
			par = tree[par]
			cycle.append(par)
			par = tree[par]
			while par not in graph[leaf]:
				cycle.append(par)
				par = tree[par]
			cycle.append(par)
			return cycle
		visited.add(par)
		sons = ograph[par]
		for son in sons:
			ograph[son].remove(par)
			tree[son] = par
		d.extend(sons)
t = int(input())
for _ in range(t):
	n = int(input())
	graph = defaultdict(set)
	for _ in range(n):
		(ui, vi) = tuple(map(int, input().split(' ')))
		graph[ui].add(vi)
		graph[vi].add(ui)
	cycle = find_cycle(ui, graph)
	for i in range(len(cycle)):
		(u, v) = (cycle[i], cycle[(i + 1) % len(cycle)])
		graph[u].remove(v)
		graph[v].remove(u)
	conn_components = []
	unvisited = set(graph.keys())
	while len(unvisited):
		vis = dfs(unvisited.pop(), graph)
		unvisited -= vis
		conn_components.append(len(vis) - 1)
	simple_paths = n * (n - 1) // 2
	k = len(cycle)
	simple_paths += (n - k) * (k - 1)
	simple_paths += k * (k - 1) // 2
	cc = conn_components
	scc = sum(cc)
	for comp in cc:
		scc -= comp
		simple_paths += comp * scc
	print(simple_paths)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import sys, threading
sys.setrecursionlimit(400000)
threading.stack_size(10 ** 8)

def dfs(x, y):
	global v, e, l, t, adj, l1
	v[x] = 1
	e[x] = t
	l[x] = t
	t += 1
	for i in adj[x]:
		if i == y:
			continue
		if v[i]:
			l[x] = min(l[x], e[i])
			l1[i] = 1
		else:
			dfs(i, x)
			if e[x] >= l[i]:
				l1[x] = 1
			l[x] = min(l[x], l[i])

def dfs1(x):
	global v, e, l, t, adj, l1, c
	v[x] = 1
	c += 1
	for i in adj[x]:
		if not v[i] and (not l1[i]):
			dfs1(i)

def main():
	global v, e, l, t, adj, l1, c
	t = int(input())
	for i in range(t):
		n = int(input())
		v = [0] * (n + 1)
		e = [0] * (n + 1)
		l = [0] * (n + 1)
		t = 0
		adj = [[] for j in range(n + 1)]
		l1 = [0] * (n + 1)
		l2 = []
		for j in range(n):
			(x, y) = map(int, input().split())
			adj[x].append(y)
			adj[y].append(x)
		dfs(1, -1)
		v = [0] * (n + 1)
		for j in range(1, n + 1):
			if l1[j]:
				c = 0
				dfs1(j)
				l2.append(c)
		ans = 0
		for j in l2:
			ans += j * (j - 1) // 2
			ans += (n - j) * j
		print(ans)
p = threading.Thread(target=main)
p.start()
p.join()


def count_paths_n(graph):
	n = len(graph)
	factors = [1] * n
	leaves = [vertex for vertex in range(n) if len(graph[vertex]) == 1]
	while leaves:
		new_leaves = []
		for leave in leaves:
			assert len(graph[leave]) == 1
			neighbor = next(iter(graph[leave]))
			factors[neighbor] += factors[leave]
			__remove_vertex(graph, leave)
			neighbor_power = len(graph[neighbor])
			assert neighbor_power >= 1
			if neighbor_power == 1:
				new_leaves.append(neighbor)
		leaves = new_leaves
	cycle_members_factors = [factors[vertex] for vertex in range(n) if __has_vertex(graph, vertex)]
	paths_n_through_odd_edge = (sum(cycle_members_factors) ** 2 - sum((factor ** 2 for factor in cycle_members_factors))) // 2
	paths_n_ignoring_odd_edge = n * (n - 1) // 2
	paths_n = paths_n_through_odd_edge + paths_n_ignoring_odd_edge
	return paths_n

def __remove_vertex(graph, vertex):
	for neighbor in graph[vertex]:
		graph[neighbor].remove(vertex)
	graph[vertex] = None

def __has_vertex(graph, vertex):
	return vertex < len(graph) and graph[vertex] is not None

def __main():
	t = int(input())
	for i_t in range(t):
		n = int(input())
		graph = [[] for vertex in range(n)]
		for i_edge in range(n):
			(v1, v2) = [int(x) - 1 for x in input().split()]
			graph[v1].append(v2)
			graph[v2].append(v1)
		result = count_paths_n(graph)
		print(result)
__main()


from functools import cmp_to_key
from collections import deque
from heapq import heappush, heappop
from math import log, ceil
import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def ii():
	return int(inp())

def li(lag=0):
	l = list(map(int, inp().split()))
	if lag != 0:
		for i in range(len(l)):
			l[i] += lag
	return l

def mi(lag=0):
	matrix = list()
	for i in range(n):
		matrix.append(li(lag))
	return matrix

def sli():
	return list(map(str, inp().split()))

def print_list(lista, space=' '):
	print(space.join(map(str, lista)))

class TreeNode:

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

class AvlTree:

	def __init__(self):
		self._tree = None

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

class UnionFind:

	def __init__(self, n):
		self.parent = list(range(n))
		self.size = [1] * n
		self.num_sets = n

	def find(self, a):
		to_update = []
		while a != self.parent[a]:
			to_update.append(a)
			a = self.parent[a]
		for b in to_update:
			self.parent[b] = a
		return self.parent[a]

	def merge(self, a, b):
		a = self.find(a)
		b = self.find(b)
		if a == b:
			return
		if self.size[a] < self.size[b]:
			(a, b) = (b, a)
		self.num_sets -= 1
		self.parent[b] = a
		self.size[a] += self.size[b]

	def set_size(self, a):
		return self.size[self.find(a)]

	def __len__(self):
		return self.num_sets

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

def bisect_left(a, x):
	left = 0
	right = len(a)
	while left < right:
		mid = (left + right) // 2
		if a[mid] < x:
			left = mid + 1
		else:
			right = mid
	return left

def bisect_right(a, x):
	left = 0
	right = len(a)
	while left < right:
		mid = (left + right) // 2
		if a[mid] > x:
			right = mid
		else:
			left = mid + 1
	return left

def bisect_elements(a, x):
	return bisect_right(a, x) - bisect_left(a, x)

def custom_sort(lista):

	def cmp(x, y):
		if x + y > y + x:
			return 1
		else:
			return -1
	return sorted(lista, key=cmp_to_key(cmp))
MOD = 10 ** 9 + 7
maxN = 10 ** 5
FACT = [0] * maxN

def add(x, y):
	return (x + y) % MOD

def multiply(x, y):
	return x * y % MOD

def power(x, y):
	if y == 0:
		return 1
	elif y % 2:
		return multiply(x, power(x, y - 1))
	else:
		a = power(x, y // 2)
		return multiply(a, a)

def inverse(x):
	return power(x, MOD - 2)

def divide(x, y):
	return multiply(x, inverse(y))

def allFactorials():
	FACT[0] = 1
	for i in range(1, maxN):
		FACT[i] = multiply(i, FACT[i - 1])

def coeffBinom(n, k):
	if n < k:
		return 0
	return divide(FACT[n], multiply(FACT[k], FACT[n - k]))

def primes(N):
	smallest_prime = [1] * (N + 1)
	prime = []
	smallest_prime[0] = 0
	smallest_prime[1] = 0
	for i in range(2, N + 1):
		if smallest_prime[i] == 1:
			prime.append(i)
			smallest_prime[i] = i
		j = 0
		while j < len(prime) and i * prime[j] <= N:
			smallest_prime[i * prime[j]] = min(prime[j], smallest_prime[i])
			j += 1
	return (prime, smallest_prime)

def gcd(a, b):
	(s, t, r) = (0, 1, b)
	(old_s, old_t, old_r) = (1, 0, a)
	while r != 0:
		quotient = old_r // r
		(old_r, r) = (r, old_r - quotient * r)
		(old_s, s) = (s, old_s - quotient * s)
		(old_t, t) = (t, old_t - quotient * t)
	return (old_r, old_s, old_t)

def create_graph(n, m, undirected=1, unweighted=1):
	graph = [[] for i in range(n)]
	if unweighted:
		for i in range(m):
			[x, y] = li(lag=-1)
			graph[x].append(y)
			if undirected:
				graph[y].append(x)
	else:
		for i in range(m):
			[x, y, w] = li(lag=-1)
			graph[x].append([y, w])
			if undirected:
				graph[y].append([x, w])
	return graph

def create_tree(n, unweighted=1):
	children = [[] for i in range(n)]
	if unweighted:
		for i in range(n - 1):
			[x, y] = li(lag=-1)
			children[x].append(y)
			children[y].append(x)
	else:
		for i in range(n - 1):
			[x, y, w] = li(lag=-1)
			children[x].append([y, w])
			children[y].append([x, w])
	return children

def create_edges(m, unweighted=0):
	edges = list()
	if unweighted:
		for i in range(m):
			edges.append(li(lag=-1))
	else:
		for i in range(m):
			[x, y, w] = li(lag=-1)
			edges.append([w, x, y])
	return edges

def dist(tree, n, A, B=-1):
	s = [[A, 0]]
	(massimo, massimo_nodo) = (0, 0)
	distanza = -1
	v = [-1] * n
	while s:
		(el, dis) = s.pop()
		if dis > massimo:
			massimo = dis
			massimo_nodo = el
		if el == B:
			distanza = dis
		for child in tree[el]:
			if v[child] == -1:
				v[child] = 1
				s.append([child, dis + 1])
	return (massimo, massimo_nodo, distanza)

def diameter(tree):
	(_, foglia, _) = dist(tree, n, 0)
	(diam, _, _) = dist(tree, n, foglia)
	return diam

def dfs(graph, n, A):
	v = [-1] * n
	s = [[A, 0]]
	v[A] = 0
	while s:
		(el, dis) = s.pop()
		for child in graph[el]:
			if v[child] == -1:
				v[child] = dis + 1
				s.append([child, dis + 1])
	return v

def bfs(graph, n, A):
	v = [-1] * n
	s = deque()
	s.append([A, 0])
	v[A] = 0
	while s:
		(el, dis) = s.popleft()
		for child in graph[el]:
			if v[child] == -1:
				v[child] = dis + 1
				s.append([child, dis + 1])
	return v

def connected(graph, n):
	v = dfs(graph, n, 0)
	for el in v:
		if el == -1:
			return False
	return True

def topological(graph, n):
	indegree = [0] * n
	for el in range(n):
		for child in graph[el]:
			indegree[child] += 1
	s = deque()
	for el in range(n):
		if indegree[el] == 0:
			s.append(el)
	order = []
	while s:
		el = s.popleft()
		order.append(el)
		for child in graph[el]:
			indegree[child] -= 1
			if indegree[child] == 0:
				s.append(child)
	if n == len(order):
		return (False, order)
	else:
		return (True, [])

def bipartite(graph, n):
	color = [-1] * n
	color[0] = 0
	s = [0]
	while s:
		el = s.pop()
		for child in graph[el]:
			if color[child] == color[el]:
				return False
			if color[child] == -1:
				s.append(child)
			color[child] = 1 - color[el]
	return True

def dijkstra(graph, n, A):
	dist = [float('inf') for i in range(n)]
	prev = [-1 for i in range(n)]
	dist[A] = 0
	pq = []
	heappush(pq, [0, A])
	while pq:
		[d_v, v] = heappop(pq)
		if d_v != dist[v]:
			continue
		for (to, w) in graph[v]:
			if dist[v] + w < dist[to]:
				dist[to] = dist[v] + w
				prev[to] = v
				heappush(pq, [dist[to], to])
	return (dist, prev)

def dijkstra_0_1(graph, n, A):
	dist = [float('inf') for i in range(n)]
	dist[A] = 0
	p = deque()
	p.append(A)
	while p:
		v = p.popleft()
		for (to, w) in graph[v]:
			if dist[v] + w < dist[to]:
				dist[to] = dist[v] + w
			if w == 1:
				q.append(to)
			else:
				q.appendleft(to)
	return dist

def floyd_warshall(graph, n):
	dist = [[float('inf') for _ in range(n)] for _ in range(n)]
	for i in range(n):
		dist[i][i] = 0
		for (child, d) in graph[i]:
			dist[i][child] = d
			dist[child][i] = d
	for k in range(n):
		for i in range(n):
			for j in range(j):
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
	return dist

def minimum_spanning_tree(edges, n):
	edges = sorted(edges)
	union_find = UnionFind(n)
	used_edges = list()
	for (w, x, y) in edges:
		if union_find.find(x) != union_find.find(y):
			union_find.merge(x, y)
			used_edges.append([w, x, y])
	return used_edges

def parents_children_root_unrooted_tree(tree, n, root=0):
	q = deque()
	visited = [0] * n
	parent = [-1] * n
	children = [[] for i in range(n)]
	q.append(root)
	while q:
		all_done = 1
		visited[q[0]] = 1
		for child in tree[q[0]]:
			if not visited[child]:
				all_done = 0
				q.appendleft(child)
		if all_done:
			for child in tree[q[0]]:
				if parent[child] == -1:
					parent[q[0]] = child
					children[child].append(q[0])
			q.popleft()
	return (parent, children)

def all_longest_path_starting_from_node(parent, children, n):
	q = deque()
	visited = [len(children[i]) for i in range(n)]
	downwards = [[0, 0] for i in range(n)]
	upward = [1] * n
	longest_path = [1] * n
	for i in range(n):
		if not visited[i]:
			q.append(i)
			downwards[i] = [1, 0]
	while q:
		node = q.popleft()
		if parent[node] != -1:
			visited[parent[node]] -= 1
			if not visited[parent[node]]:
				q.append(parent[node])
		else:
			root = node
		for child in children[node]:
			downwards[node] = sorted([downwards[node][0], downwards[node][1], downwards[child][0] + 1], reverse=True)[0:2]
	s = [node]
	while s:
		node = s.pop()
		if parent[node] != -1:
			if downwards[parent[node]][0] == downwards[node][0] + 1:
				upward[node] = 1 + max(upward[parent[node]], downwards[parent[node]][1])
			else:
				upward[node] = 1 + max(upward[parent[node]], downwards[parent[node]][0])
		longest_path[node] = downwards[node][0] + downwards[node][1] + upward[node] - min([downwards[node][0], downwards[node][1], upward[node]]) - 1
		for child in children[node]:
			s.append(child)
	return longest_path

def finding_ancestors(parent, queries, n):
	steps = int(ceil(log(n, 2)))
	ancestors = [[-1 for i in range(n)] for j in range(steps)]
	ancestors[0] = parent
	for i in range(1, steps):
		for node in range(n):
			if ancestors[i - 1][node] != -1:
				ancestors[i][node] = ancestors[i - 1][ancestors[i - 1][node]]
	result = []
	for (node, k) in queries:
		ans = node
		if k >= n:
			ans = -1
		i = 0
		while k > 0 and ans != -1:
			if k % 2:
				ans = ancestors[i][ans]
			k = k // 2
			i += 1
		result.append(ans)
	return result

class SegmentTree:

	def __init__(self, arr):
		(self.low, self.high) = (0, len(arr) - 1)
		self.sz = pow(2, int(ceil(log(len(arr), 2))))
		self.dat = [float('inf')] * (2 * self.sz - 1)
		self.arr = arr
		self.build_help(self.low, self.high, 0)

	def build_help(self, low, high, pos):
		if low == high:
			self.dat[pos] = self.arr[low]
			return
		mid = (low + high) // 2
		self.build_help(low, mid, 2 * pos + 1)
		self.build_help(mid + 1, high, 2 * pos + 2)
		self.dat[pos] = self.dat[2 * pos + 1] + self.dat[2 * pos + 2]

	def update(self, idx, val):
		self.update_help(idx, self.low, self.high, 0, val)

	def update_help(self, idx, low, high, pos, val):
		if idx < low or idx > high:
			return
		if low == high:
			self.dat[pos] = val
			return
		mid = (low + high) // 2
		self.update_help(idx, low, mid, 2 * pos + 1, val)
		self.update_help(idx, mid + 1, high, 2 * pos + 2, val)
		self.dat[pos] = self.dat[2 * pos + 1] + self.dat[2 * pos + 2]

	def query(self, qlow, qhigh):
		return self.query_help(qlow, qhigh, self.low, self.high, 0)

	def query_help(self, qlow, qhigh, low, high, pos):
		if qlow <= low and qhigh >= high:
			return self.dat[pos]
		if qlow > high or qhigh < low:
			return 0
		mid = (low + high) // 2
		return self.query_help(qlow, qhigh, low, mid, 2 * pos + 1) + self.query_help(qlow, qhigh, mid + 1, high, 2 * pos + 2)

def prefix_sum(arr):
	r = [0] * (len(arr) + 1)
	for (i, el) in enumerate(arr):
		r[i + 1] = r[i] + el
	return r

def nearest_from_the_left_smaller_elements(arr):
	n = len(arr)
	res = [-1] * n
	s = []
	for (i, el) in enumerate(arr):
		while s and s[-1] >= el:
			s.pop()
		if s:
			res[i] = s[-1]
		s.append(el)
	return res

def sliding_window_minimum(arr, k):
	res = []
	q = deque()
	for (i, el) in enumerate(arr):
		while q and arr[q[-1]] >= el:
			q.pop()
		q.append(i)
		while q and q[0] <= i - k:
			q.popleft()
		if i >= k - 1:
			res.append(arr[q[0]])
	return res

class TrieNode:

	def __init__(self):
		self.children = [None] * 26
		self.isEndOfWord = False

class Trie:

	def __init__(self):
		self.root = self.getNode()

	def getNode(self):
		return TrieNode()

	def _charToIndex(self, ch):
		return ord(ch) - ord('a')

	def insert(self, key):
		pCrawl = self.root
		length = len(key)
		for level in range(length):
			index = self._charToIndex(key[level])
			if not pCrawl.children[index]:
				pCrawl.children[index] = self.getNode()
			pCrawl = pCrawl.children[index]
		pCrawl.isEndOfWord = True

	def search(self, key):
		pCrawl = self.root
		length = len(key)
		for level in range(length):
			index = self._charToIndex(key[level])
			if not pCrawl.children[index]:
				return False
			pCrawl = pCrawl.children[index]
		return pCrawl != None and pCrawl.isEndOfWord

def crea(x, y):
	return (min(x, y), max(x, y))

def nodiok(graph, partenza, destra, sinistra, edge):
	stack = [partenza]
	frecce = set()
	frecce.add(edge)
	frecce.add(crea(partenza, destra))
	frecce.add(crea(partenza, sinistra))
	count = 0
	while stack:
		el = stack.pop()
		for child in graph[el]:
			freccia = crea(el, child)
			if freccia not in frecce:
				stack.append(child)
				count += 1
			frecce.add(freccia)
	return count
t = ii()
for test in range(t):
	n = ii()
	graph = dict()
	for v in range(1, n + 1):
		graph[v] = set()
	for edges in range(n):
		[x, y] = li()
		graph[x].add(y)
		graph[y].add(x)
	visited = set()
	stack = [1]
	visited.add(1)
	frecce = set()
	while stack:
		el = stack.pop()
		for child in graph[el]:
			freccia = (min(el, child), max(el, child))
			if freccia not in frecce:
				if child not in visited:
					stack.append(child)
					visited.add(child)
				else:
					edge = (min(el, child), max(el, child))
					stack = list()
					break
			frecce.add(freccia)
	total_path = n * (n - 1) // 2
	stack = [edge[0]]
	frecce = set()
	frecce.add(edge)
	previous = dict()
	while stack:
		el = stack.pop()
		for child in graph[el]:
			freccia = (min(el, child), max(el, child))
			if freccia not in frecce:
				stack.append(child)
				previous[child] = el
				if child == edge[1]:
					parente = el
					stack = list()
					break
			frecce.add(freccia)
	ciclo = [edge[1]]
	while ciclo[-1] != edge[0]:
		ciclo.append(previous[ciclo[-1]])
	res = list()
	NC = len(ciclo)
	for i in range(len(ciclo)):
		res.append(nodiok(graph, ciclo[i], ciclo[(i + 1) % NC], ciclo[(i - 1) % NC], edge))
	x = 0
	x += sum(res) ** 2
	for el in res:
		x -= el ** 2
	total_path += x // 2
	total_path += NC * (NC - 1) // 2
	total_path += (NC - 1) * sum(res)
	print(total_path)


from collections import deque
from sys import stdin, gettrace
if gettrace():
	inputi = input
else:

	def input():
		return next(stdin)[:-1]

	def inputi():
		return stdin.buffer.readline()

def readGraph(n, m):
	adj = [[] for _ in range(n)]
	for _ in range(m):
		(u, v) = map(int, inputi().split())
		adj[u - 1].append(v - 1)
		adj[v - 1].append(u - 1)
	return adj

def solve():
	n = int(inputi())
	adj = readGraph(n, n)
	parent = [None] * n
	depth = [0] * n
	q = deque()
	q.append(0)
	loop = deque()
	while not loop:
		c = q.popleft()
		for a in adj[c]:
			if a != parent[c]:
				if parent[a] != None:
					loop.append(a)
					loop.append(c)
					break
				else:
					parent[a] = c
					depth[a] = depth[c] + 1
					q.append(a)
	while loop[0] != loop[-1]:
		if depth[loop[0]] > depth[loop[-1]]:
			loop.appendleft(parent[loop[0]])
		else:
			loop.append(parent[loop[-1]])
	loop = list(loop)[:-1]
	ls = len(loop)
	lc = []
	for i in range(ls):
		l = loop[i]
		q = deque()
		q.append(l)
		count = 0
		visited = {loop[(i - 1) % ls], l, loop[(i + 1) % ls]}
		while q:
			for a in adj[q.popleft()]:
				if a not in visited:
					count += 1
					visited.add(a)
					q.append(a)
		lc.append(count)
	treecount = n * (n - 1) // 2
	loopcount = ls * (ls - 1) // 2
	lt = (ls - 1) * (n - ls)
	tt = sum((c * (n - c - ls) for c in lc)) // 2
	res = treecount + loopcount + lt + tt
	print(res)

def main():
	t = int(inputi())
	for _ in range(t):
		solve()
main()


import sys
input = iter(sys.stdin.read().splitlines()).__next__

def find_cycle_dfs(graph):
	parents = {}
	stack = [(0, None)]
	while stack:
		(node, parent) = stack.pop()
		if node in parents:
			break
		parents[node] = parent
		for child in graph[node]:
			if child == parent:
				continue
			stack.append((child, node))
	cycle = {parent}
	current = parent
	while current != node:
		current = parents[current]
		cycle.add(current)
	return cycle

def branch_size(graph, cycle_entry, cycle):
	visited = {cycle_entry}
	stack = graph[cycle_entry].copy()
	while stack:
		node = stack.pop()
		if node in visited or node in cycle:
			continue
		visited.add(node)
		for child in graph[node]:
			stack.append(child)
	return len(visited)

def solve(graph, n):
	cycle = find_cycle_dfs(graph)
	cycle_entries = filter(lambda node: node in cycle and len(graph[node]) > 2, range(n))
	branch_sizes = map(lambda entry: branch_size(graph, entry, cycle), cycle_entries)
	return n * (n - 1) - sum(map(lambda x: x * (x - 1) // 2, branch_sizes))
t = int(input())
output = []
for _ in range(t):
	n = int(input())
	graph = [[] for _ in range(n)]
	for edge in range(n):
		(u, v) = map(int, input().split())
		graph[u - 1].append(v - 1)
		graph[v - 1].append(u - 1)
	output.append(solve(graph, n))
print(*output, sep='\n')


from collections import deque
import sys
import copy

def dfs(now):
	for j in G[now[-1]]:
		if not visit[j]:
			now.append(j)
			visit[j] = 1
			dfs(now)
			now.pop()
			visit[j] = 0
		else:
			global f
			if not now[-2] == j and (not f):
				now.append(j)
				f = 1
				global x
				x = now.copy()
				return

def bfs():
	q = deque()
	q.append([1, 0])
	parent = [0] * (n + 1)
	visit[1] = 1
	while q:
		(i, ii) = q.popleft()
		for j in G[i]:
			if not visit[j]:
				parent[j] = i
				visit[j] = 1
				q.append([j, i])
			elif not parent[i] == j:
				xx = set()
				x = set()
				k = i
				while not k == 0:
					xx.add(k)
					k = parent[k]
				k = j
				while not k == 0:
					if not k in xx:
						x.add(k)
						k = parent[k]
					else:
						k = parent[k]
						break
				l = i
				while not l == k:
					x.add(l)
					l = parent[l]
				return list(x)
t = int(input())
for _ in range(t):
	n = int(input())
	G = [[] for _ in range(n + 1)]
	for _ in range(n):
		(u, v) = map(int, input().split())
		G[u].append(v)
		G[v].append(u)
	visit = [0] * (n + 1)
	visit[1] = 1
	y = bfs()
	f = 0
	cy = [0] * (n + 1)
	for i in y:
		cy[i] = 1
	ans = n * (n - 1)
	q = deque()
	visit = [0] * (n + 1)
	for i in y:
		cnt = 1
		visit[i] = 1
		for j in G[i]:
			if not cy[j]:
				q.append(j)
				cnt += 1
				visit[j] = 1
				while q:
					k = q.popleft()
					for l in G[k]:
						if not visit[l]:
							q.append(l)
							cnt += 1
							visit[l] = 1
		ans -= cnt * (cnt - 1) // 2
	print(ans)


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

def dfs(start, graph):
	visited = {start}
	d = deque(graph[start])
	while d:
		v = d.pop()
		visited.add(v)
		d.extend(graph[v] - visited)
	return visited

def find_cycle(vx, graph):
	visited = [0] * len(graph)
	d = deque([vx])
	while d:
		visited[vx] = 1
		sons = graph[vx]
		vx_sons = [son for son in sons if visited[son] == 0]
		vx_parents = [son for son in sons if visited[son] == 1]
		if len(vx_parents) > 1:
			branch = {i for (i, v) in enumerate(visited) if v == 1}
			(start, end) = vx_parents
			if len(graph[start] & branch) != 2:
				(start, end) = (end, start)
			assert len(graph[start] & branch) == 2 and 2 <= len(graph[end] & branch) <= 3
			pvx = vx
			cycle = [pvx]
			vx = start
			graph[end].remove(pvx)
			graph[pvx].remove(end)
			while vx != end:
				graph[vx].remove(pvx)
				graph[pvx].remove(vx)
				cycle.append(vx)
				pvx = vx
				vx = (graph[vx] & branch).pop()
			graph[vx].remove(pvx)
			graph[pvx].remove(vx)
			cycle.append(end)
			return cycle
		d.append(vx)
		d.extend(vx_sons)
		vx = d.pop()
		while d and visited[vx] == 1:
			visited[vx] = 2
			vx = d.pop()
t = int(input())
for _ in range(t):
	n = int(input())
	graph = defaultdict(set)
	for _ in range(n):
		(ui, vi) = tuple(map(int, input().split(' ')))
		ui -= 1
		vi -= 1
		graph[ui].add(vi)
		graph[vi].add(ui)
	cycle = find_cycle(ui, graph)
	conn_components = []
	unvisited = set(graph.keys())
	while len(unvisited):
		vis = dfs(unvisited.pop(), graph)
		unvisited -= vis
		conn_components.append(len(vis) - 1)
	simple_paths = n * (n - 1) // 2
	k = len(cycle)
	simple_paths += (n - k) * (k - 1)
	simple_paths += k * (k - 1) // 2
	cc = conn_components
	scc = sum(conn_components)
	for cc in conn_components:
		scc -= cc
		simple_paths += cc * scc
	print(simple_paths)


import io
import os
from collections import Counter, defaultdict, deque

def findCycle(source, getNbr):
	q = deque([source])
	dist = {source: 0}
	parent = {source: None}
	while q:
		node = q.popleft()
		d = dist[node]
		for nbr in getNbr(node):
			if nbr not in dist:
				q.append(nbr)
				dist[nbr] = d + 1
				parent[nbr] = node
			else:
				if dist[nbr] == d - 1:
					assert nbr == parent[node]
					continue
				assert dist[nbr] in [d, d + 1]
				path1 = [nbr]
				path2 = [node]
				while path1[-1] != path2[-1]:
					if dist[path1[-1]] >= dist[path2[-1]]:
						path1.append(parent[path1[-1]])
					else:
						path2.append(parent[path2[-1]])
				assert path1[-1] == path2[-1]
				path2.pop()
				return path1 + path2[::-1]
	return None

def bfs(source, getNbr):
	q = deque([source])
	dist = {source: 0}
	while q:
		node = q.popleft()
		d = dist[node]
		for nbr in getNbr(node):
			if nbr not in dist:
				q.append(nbr)
				dist[nbr] = d + 1
	return dist

def solve(N, edges):
	graph = [[] for i in range(N)]
	for (u, v) in edges:
		graph[u].append(v)
		graph[v].append(u)

	def nC2(n):
		return n * (n - 1) // 2
	ans = 2 * nC2(N)

	def getNbr(u):
		return graph[u]
	cycle = findCycle(0, getNbr)
	C = len(cycle)
	for (i, x) in enumerate(cycle):
		exclude = [cycle[(i - 1) % C], cycle[(i + 1) % C]]

		def getNbr(u):
			return (v for v in graph[u] if v not in exclude)
		subtreeSize = len(bfs(x, getNbr))
		ans -= nC2(subtreeSize)
	return ans
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
TC = int(input())
for tc in range(1, TC + 1):
	(N,) = [int(x) for x in input().split()]
	edges = [[int(x) - 1 for x in input().split()] for i in range(N)]
	ans = solve(N, edges)
	print(ans)


import sys
from collections import defaultdict, deque
from io import BytesIO, IOBase

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None
		self.BUFSIZE = 8192

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def get_int():
	return int(input())

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

def get_int_grid(n):
	return [get_ints() for _ in range(n)]

def get_str():
	return input().split(' ')

def yes_no(b):
	if b:
		return 'YES'
	else:
		return 'NO'

def binary_search(good, left, right, delta=1, right_true=False):
	limits = [left, right]
	while limits[1] - limits[0] > delta:
		if delta == 1:
			mid = sum(limits) // 2
		else:
			mid = sum(limits) / 2
		if good(mid):
			limits[int(right_true)] = mid
		else:
			limits[int(~right_true)] = mid
	if good(limits[int(right_true)]):
		return limits[int(right_true)]
	else:
		return False

def prefix_sums(a):
	p = [0]
	for x in a:
		p.append(p[-1] + x)
	return p

def bfs_cycle(graph, root):
	Q = deque([(root, -1)])
	parents = {root: -1}
	while Q:
		(node, parent) = Q.popleft()
		for neighbour in graph[node]:
			if neighbour == parent:
				continue
			elif neighbour in parents:
				path1 = [node]
				visited1 = {node}
				while parents[path1[-1]] != -1:
					path1.append(parents[path1[-1]])
					visited1.add(path1[-1])
				path2 = [neighbour]
				while parents[path2[-1]] != -1:
					path2.append(parents[path2[-1]])
					if path2[-1] in visited1:
						path1 = path1[:path1.index(path2[-1])]
						return path1 + path2[::-1]
			else:
				parents[neighbour] = node
				Q.append((neighbour, node))
	return False

class DSU:

	def __init__(self, nodes):
		self.p = [i for i in range(nodes)]
		self.r = [0 for i in range(nodes)]
		self.s = [1 for i in range(nodes)]

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

	def union(self, u, v):
		u = self.get(u)
		v = self.get(v)
		if u != v:
			if self.r[u] > self.r[v]:
				(u, v) = (v, u)
			self.p[u] = v
			if self.r[u] == self.r[v]:
				self.r[v] += 1
			self.s[v] += self.s[u]
t = get_int()
for _ in range(t):
	n = get_int()
	G = defaultdict(set)
	for edge in range(n):
		(a, b) = [int(x) for x in input().split(' ')]
		G[a].add(b)
		G[b].add(a)
	cycle = set(bfs_cycle(G, 1))
	dsu = DSU(n)
	for x in G:
		for y in G[x]:
			if not (x in cycle and y in cycle):
				dsu.union(x - 1, y - 1)
	tree_sizes = []
	for i in range(n):
		if dsu.get(i) == i and i + 1:
			tree_sizes.append(dsu.s[i])
	S = 0
	for m in tree_sizes:
		S += m * (m - 1) // 2
		S += m * (n - m)
	print(S)


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left, bisect_right
import time
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict as dd, deque as dq, Counter as dc
import math, string
start_time = time.time()

def getInts():
	return [int(s) for s in input().split()]

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

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

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

def getMat(n):
	return [getInts() for _ in range(n)]
MOD = 998244353

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
import copy

def solve():
	N = getInt()
	graph = dd(set)
	for n in range(N):
		(u, v) = getInts()
		u -= 1
		v -= 1
		graph[u].add(v)
		graph[v].add(u)
	parents = [-1] * N
	global ans
	ans = None

	@bootstrap
	def dfs(node):
		global ans
		if ans:
			yield
		visited.add(node)
		for neigh in graph[node]:
			if neigh in visited and neigh != parents[node] and (ans is None):
				ans = (node, neigh)
			if neigh not in visited:
				parents[neigh] = node
				yield dfs(neigh)
		yield
	visited = set()
	dfs(0)
	(node, neigh) = ans
	cycle = set()
	graph[node].remove(neigh)
	graph[neigh].remove(node)
	cycle.add(node)
	cycle.add(neigh)
	(curr, par) = (node, parents[node])
	while par != neigh:
		graph[curr].remove(par)
		graph[par].remove(curr)
		cycle.add(curr)
		cycle.add(par)
		(curr, par) = (par, parents[par])
	graph[curr].remove(par)
	graph[par].remove(curr)

	def bfs(node):
		queue = dq([node])
		visited.add(node)
		while queue:
			node = queue.popleft()
			for neigh in graph[node]:
				if neigh not in visited:
					visited.add(neigh)
					queue.append(neigh)
		return len(visited)
	ans = N * (N - 1)
	for node in cycle:
		visited = set()
		c = bfs(node)
		ans -= c * (c - 1) // 2
	return ans
for _ in range(getInt()):
	print(solve())


import sys
input = sys.stdin.readline
from collections import deque
(T,) = map(int, input().split())
for _ in range(T):
	(N,) = map(int, input().split())
	G = [set() for _ in range(N + 1)]
	ds = [0] * (N + 1)
	for _ in range(N):
		(u, v) = map(int, input().split())
		G[u].add(v)
		G[v].add(u)
		ds[u] += 1
		ds[v] += 1
	queue = deque([])
	loop = [1] * (N + 1)
	for i in range(1, N + 1):
		if ds[i] == 1:
			queue.append(i)
			loop[i] = 0
	while queue:
		v = queue.popleft()
		for u in G[v]:
			if not loop[u]:
				continue
			ds[u] -= 1
			if ds[u] <= 1:
				loop[u] = 0
				queue.append(u)
	R = N * (N - 1)
	vs = [0] * (N + 1)
	for v in range(1, N + 1):
		if not loop[v]:
			continue
		stack = [v]
		c = 1
		while stack:
			v = stack.pop()
			for u in G[v]:
				if loop[u]:
					continue
				if vs[u]:
					continue
				vs[u] = 1
				stack.append(u)
				c += 1
		R -= c * (c - 1) // 2
	print(R)


import sys
input = sys.stdin.buffer.readline
t = int(input())
for _ in range(t):
	n = int(input())
	adj = [set() for _ in range(n + 1)]
	for _ in range(n):
		(u, v) = [int(x) for x in input().split()]
		adj[u].add(v)
		adj[v].add(u)
	leaves = []
	for node in range(1, n + 1):
		if len(adj[node]) == 1:
			leaves.append(node)
	subTreeSizes = [1 for _ in range(n + 1)]
	while leaves:
		leaf = leaves.pop()
		nex = next(iter(adj[leaf]))
		subTreeSizes[nex] += subTreeSizes[leaf]
		adj[nex].remove(leaf)
		if len(adj[nex]) == 1:
			leaves.append(nex)
	nodesAtCycle = []
	for node in range(1, n + 1):
		if len(adj[node]) == 2:
			nodesAtCycle.append(node)
	intraTreeWays = 0
	interTreeWays = 0
	for node in nodesAtCycle:
		size = subTreeSizes[node]
		intraTreeWays += size * (size - 1) // 2
		interTreeWays += 2 * (n - size) * size
	ans = intraTreeWays + interTreeWays // 2
	print(ans)


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

class Graph(object):

	def __init__(self, n, d):
		self.n = n
		self.graph = {}
		self.parent = [-1 for i in range(n)]
		self.directed = d

	def addEdge(self, x, y):
		if x not in self.graph:
			self.graph[x] = set()
		self.graph[x].add(y)
		if not self.directed:
			if y not in self.graph:
				self.graph[y] = set()
			self.graph[y].add(x)

	def bfs(self, root):
		queue = [root]
		queue = deque(queue)
		vis = [0] * self.n
		while len(queue) != 0:
			element = queue.popleft()
			vis[element] = 1
			for i in self.graph[element]:
				if vis[i] == 0:
					queue.append(i)
					self.parent[i] = element
					vis[i] = 1

	def dfs(self, root):
		ans = [0] * n
		stack = [root]
		vis = [0] * self.n
		stack2 = []
		while len(stack) != 0:
			element = stack.pop()
			if vis[element]:
				continue
			vis[element] = 1
			stack2.append(element)
			for i in self.graph[element]:
				if vis[i] == 0:
					self.parent[i] = element
					stack.append(i)
		while len(stack2) != 0:
			element = stack2.pop()
			m = 0
			for i in self.graph[element]:
				if i != self.parent[element]:
					m += ans[i]
			ans[element] = m
		return ans

	def shortestpath(self, source, dest):
		self.bfs(source)
		path = [dest]
		while self.parent[path[-1]] != -1:
			path.append(parent[path[-1]])
		return path[::-1]

	def detect_cycle(self):
		indeg = [0] * self.n
		for i in range(self.n):
			for j in self.graph[i]:
				indeg[j] += 1
		q = deque()
		vis = 0
		for i in range(self.n):
			if indeg[i] == 0:
				q.append(i)
		while len(q) != 0:
			e = q.popleft()
			vis += 1
			for i in self.graph[e]:
				indeg[i] -= 1
				if indeg[i] == 0:
					q.append(i)
		if vis != self.n:
			return True
		return False

	def reroot(self, root, ans):
		stack = [root]
		vis = [0] * n
		while len(stack) != 0:
			e = stack[-1]
			if vis[e]:
				stack.pop()
				continue
			vis[e] = 1
			for i in graph[e]:
				if not vis[e]:
					stack.append(i)
			if self.parent[e] == -1:
				continue

	def eulertour(self, root):
		stack = [root]
		t = []
		while len(stack) != 0:
			element = stack[-1]
			if vis[element]:
				t.append(stack.pop())
				continue
			t.append(element)
			vis[element] = 1
			for i in self.graph[element]:
				if not vis[i]:
					stack.append(i)
		return t

	def calc(self):
		q = deque()
		for i in range(self.n):
			if len(self.graph[i]) == 1:
				q.append(i)
		cnt = [1] * n
		while q:
			e = q.popleft()
			for i in self.graph[e]:
				p = i
			cnt[p] += cnt[e]
			self.graph[e].remove(p)
			self.graph[p].remove(e)
			if len(self.graph[p]) == 1:
				q.append(p)
		return (self.graph, cnt)
for nt in range(int(input())):
	n = int(input())
	g = Graph(n, False)
	for i in range(n):
		(a, b) = map(int, input().split())
		g.addEdge(a - 1, b - 1)
	(graph, arr) = g.calc()
	v = []
	for i in graph:
		if not graph[i]:
			continue
		v.append(i)
	ans = 0
	for i in v:
		c = arr[i]
		ans += c * (c - 1) // 2 + c * (n - c)
	print(ans)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
cdiv = lambda x, y: -(-x // y)
read = lambda : list(map(int, input().split()))
xrange = lambda *args: reversed(range(*args))
inf = float('inf')
enum = enumerate
mod = 10 ** 9 + 7

def find_cycle(gr):
	vis = [False for i in range(n)]
	par = [-1 for i in range(n)]
	foc = []

	@bootstrap
	def dfs(node, p):
		par[node] = p
		vis[node] = True
		for i in gr[node]:
			if not vis[i]:
				yield dfs(i, node)
			elif i != p:
				foc.append(i)
		yield
	dfs(0, -1)
	(foc, loc) = foc
	cycle = set([foc])
	while loc != foc:
		cycle.add(loc)
		loc = par[loc]
	vis = [False for i in range(n)]
	dp = [1 for i in range(n)]

	@bootstrap
	def dfs2(node):
		vis[node] = True
		dp[node] = 1
		for i in gr[node]:
			if not vis[i] and i not in cycle:
				yield dfs2(i)
				dp[node] += dp[i]
		yield
	arr = []
	for i in cycle:
		dfs2(i)
		arr.append(dp[i])
	return arr
Testcase = 1
(Testcase,) = read()
for Test in range(Testcase):
	(n,) = read()
	gr = [[] for i in range(n)]
	for i in range(n):
		(u, v) = read()
		u -= 1
		v -= 1
		gr[u].append(v)
		gr[v].append(u)
	c = find_cycle(gr)
	ans = 0
	for i in c:
		ans += i * (n - i)
		ans += i * (i - 1) // 2
	print(ans)


from collections import deque
import sys
import math

def II():
	return int(sys.stdin.readline())

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

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

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

def FACT(n, mod):
	s = 1
	facts = [1]
	for i in range(1, n + 1):
		s *= i
		s %= mod
		facts.append(s)
	return facts[n]
t = II()
for q in range(t):
	n = II()
	d = [[] for i in range(n)]
	for i in range(n):
		(x, y) = MI()
		d[x - 1].append(y - 1)
		d[y - 1].append(x - 1)
	q = []
	for i in range(n):
		if len(d[i]) == 1:
			q.append(i)
	a = [1] * n
	while q:
		temp = q.pop()
		to = d[temp].pop()
		a[to] += a[temp]
		a[temp] = 0
		d[to].remove(temp)
		if len(d[to]) == 1:
			q.append(to)
	ans = 0
	for i in a:
		ans += i * (i - 1) // 2
		ans += i * (n - i)
	print(ans)


import math, sys
from collections import defaultdict, deque
import bisect as bi

def yes():
	print('YES')

def no():
	print('NO')

def I():
	return int(sys.stdin.readline())

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

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

def dict(a):
	d = {}
	for x in a:
		if d.get(x, -1) != -1:
			d[x] += 1
		else:
			d[x] = 1
	return d

def find_gt(a, x):
	i = bi.bisect_left(a, x)
	if i != len(a):
		return i
	else:
		return -1

def dfs(d, n):
	visit = [False for x in range(n + 1)]
	parent = [0 for x in range(n + 1)]
	q = deque([1])
	parent[1] = 0
	ans = -1
	while q:
		temp = q.popleft()
		if visit[temp] == True:
			continue
		visit[temp] = True
		for x in d[temp]:
			if visit[x] == False:
				q.appendleft(x)
				parent[x] = temp
			elif x != parent[temp]:
				ans = [x, temp]
	temp = ans[1]
	path = []
	while temp != ans[0]:
		path.append(temp)
		temp = parent[temp]
	path.append(ans[0])
	visit = [False for x in range(n + 1)]
	for x in path:
		visit[x] = True
	subtree = []
	for x in path:
		q = deque([x])
		cnt = 0
		while q:
			temp = q.popleft()
			visit[temp] = True
			for x in d[temp]:
				if visit[x] == False:
					cnt += 1
					q.appendleft(x)
		subtree.append(cnt)
	c = len(path)
	ans = c * (c - 1)
	ans += ((c - 1) * 2 + 1) * (n - c)
	for x in subtree:
		ans += x * (x - 1) // 2 + x * (n - c - x)
	print(ans)

def main():
	try:
		n = I()
		d = defaultdict(list)
		for i in range(n):
			(a, b) = In()
			d[a].append(b)
			d[b].append(a)
		dfs(d, n)
	except:
		pass
M = 998244353
P = 1000000007
for _ in range(I()):
	main()


T = int(input())
for t in range(T):
	N = int(input())
	edges = [set() for i in range(N + 1)]
	count = [0 for i in range(N + 1)]
	for i in range(N):
		(u, v) = list(map(int, input().split()))
		edges[u].add(v)
		edges[v].add(u)
		count[u] = 1
		count[v] = 1
	leaves = []
	for i in range(N + 1):
		parents = edges[i]
		if len(parents) == 1:
			leaves.append(i)
	while leaves:
		leaf = leaves.pop()
		parent = next(iter(edges[leaf]))
		count[parent] += count[leaf]
		count[leaf] = 0
		edges[leaf] = set()
		edges[parent].remove(leaf)
		if len(edges[parent]) == 1:
			leaves.append(parent)
	res = 0
	for i in range(N + 1):
		c = count[i]
		if c > 0:
			res += c * (c - 1) // 2
			res += c * (N - c)
	print(res)


import sys
import math, bisect
sys.setrecursionlimit(10 ** 5)
from itertools import groupby, accumulate
from heapq import heapify, heappop, heappush
from collections import deque, Counter, defaultdict
I = lambda : int(sys.stdin.readline())
neo = lambda : map(int, sys.stdin.readline().split())
Neo = lambda : list(map(int, sys.stdin.readline().split()))
for _ in range(I()):
	n = I()
	lis = [[] for i in range(n)]
	link = [0] * n
	num = [1] * n
	for i in range(n):
		(u, v) = neo()
		u -= 1
		v -= 1
		lis[u].append(v)
		lis[v].append(u)
		link[u] += 1
		link[v] += 1
	q = deque([])
	ans = n * (n - 1)
	for i in range(n):
		if link[i] == 1:
			q.append(i)
	while q:
		v = q.popleft()
		link[v] = 0
		for nex in lis[v]:
			if link[nex] != 0:
				num[nex] += num[v]
				link[nex] -= 1
				if link[nex] == 1:
					q.append(nex)
	for i in range(n):
		if link[i] != 0:
			ans -= num[i] * (num[i] - 1) // 2
	print(ans)


import os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
import heapq
INF = 10 ** 9

def Dijkstra(graph, start):
	dist = [INF] * len(graph)
	parent = [INF] * len(graph)
	queue = [(0, start)]
	while queue:
		(path_len, v) = heapq.heappop(queue)
		if dist[v] == INF:
			dist[v] = path_len
			for w in graph[v]:
				if dist[w[0]] == INF:
					parent[w[0]] = v
					heapq.heappush(queue, (dist[v] + w[1], w[0]))
	return (dist, parent)

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = [-1] * n

	def find(self, x):
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.parents[x] > self.parents[y]:
			(x, y) = (y, x)
		self.parents[x] += self.parents[y]
		self.parents[y] = x

	def size(self, x):
		return -self.parents[self.find(x)]

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def members(self, x):
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i) == root]

	def roots(self):
		return [i for (i, x) in enumerate(self.parents) if x < 0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		return {r: self.members(r) for r in self.roots()}

	def __str__(self):
		return '\n'.join(('{}: {}'.format(r, self.members(r)) for r in self.roots()))
t = int(input())
for _ in range(t):
	n = int(input())
	graph = []
	for i in range(n):
		graph.append([])
	uf = UnionFind(n)
	edges = []
	for i in range(n):
		(a, b) = map(int, input().split())
		edges.append([a, b])
	for i in range(n):
		a = edges[i][0]
		b = edges[i][1]
		if uf.same(a - 1, b - 1):
			(dist, parents) = Dijkstra(graph, a - 1)
			cycle = set()
			curr = b - 1
			while curr != a - 1:
				cycle.add(curr)
				curr = parents[curr]
			cycle.add(a - 1)
			break
		else:
			uf.union(a - 1, b - 1)
			graph[a - 1].append([b - 1, 1])
			graph[b - 1].append([a - 1, 1])
	ans = n * (n - 1)
	uf = UnionFind(n)
	for i in range(n):
		a = edges[i][0]
		b = edges[i][1]
		if a - 1 in cycle and b - 1 in cycle:
			continue
		uf.union(a - 1, b - 1)
	for root in uf.roots():
		k = uf.size(root)
		ans -= k * (k - 1) // 2
	print(ans)