In Chefland, there are N cities numbered from 1 to N. The cities are connected using N-1 roads such that there exists a path between all pairs of cities. In other words, the cities and roads forma a tree-structure

The roads of Chefland are not in good condition. Therefore, all the roads need to be destroyed. The cost of destroying a road between cities x and y is d_{x} \cdot d_{y}, where d_{x} and d_{y} are the [degrees] of the cities x and y respectively.  
Note that, the degree of a city is the number of roads connected to it before each destroy operation.

Chef wants to find the minimum cost to destroy all the roads. On calculating this cost once, he finds the process very interesting. Therefore, he does this for Q more independent queries.  
In each query, a road is removed and another road is added. Find the minimum cost to destroy all roads initially, and after each query. It is guaranteed that after each query, all the cities are still connected and form a tree-structure.

Note: Since the queries are independent, the initial tree is retained after each query.

------ Input Format ------ 

- The first line contains a single integer T , the number of test cases. Then the test cases follow.
- The first line of each test case contains two integers N and Q.
- The next N-1 lines contain two integers each, u_{i} and v_{i} , denoting a road between cities u_{i} and v_{i} .
- The next Q lines contain four space separated integers, a_{i}, b_{i}, c_{i}, and d_{i} denoting that the road between the cities a_{i} and b_{i} is removed and the road between the cities c_{i} and d_{i} is added.

------ Output Format ------ 

For each test case, output Q+1 lines. Each line should contain a single integer.  
The first line contains the answer to the initial tree. The next Q lines contain the answer for the updated tree in each query.

------ Constraints ------ 

$1 ≤ T ≤ 10^{4}$
$1 ≤ N,Q ≤ 10^{5}$
$1 ≤ u_{i},v_{i} ≤ N, u_{i} \neq v_{i}$
$1 ≤ a_{i},b_{i},c_{i},d_{i} ≤ N, a_{i} \neq b_{i}, c_{i} \neq d_{i}$
- It is guaranteed that there exists a road between cities $a_{i}$ and $b_{i}$.
- It is guaranteed that the given edges form a tree initially as well as after every query.

------ subtasks ------ 

Subtask 1 (30 points):
Sum of $N \cdot Q$ over all test cases does not exceed $2 \cdot 10^{5}$.
Subtask 2 (70 points):
Sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$.
Sum of $Q$ over all test cases does not exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
1
4 4
1 2
1 3
1 4
1 2 2 3
1 3 2 3
4 1 1 4
2 1 4 2
----- Sample Output 1 ------ 
6
5
5
6
5
----- explanation 1 ------ 
Test Case $1$: Initially, the tree looks like:

The roads can be destroyed as: 
- Remove edge between nodes $1$ and $2$. The degree of these nodes are $3$ and $1$ respectively. Hence, the cost is $3 \cdot 1 = 3$. Now, the degree of node $1$ becomes $2$.
- Remove edge between nodes $1$ and $3$. The degree of these nodes are $2$ and $1$ respectively. Hence, the cost is $2 \cdot 1 = 2$. Now, the degree of node $1$ becomes $1$.
- Remove edge between nodes $1$ and $4$. The degree of these nodes are $1$ and $1$ respectively. Hence, the cost is $1 \cdot 1 = 1$.

Thus, the total cost is $3+2+1=6$. It can be proven that this is the minimum cost required to remove all the edges.

- Query $1$: The edge between $1$ and $2$ is removed and the edge between $2$ and $3$ is added. The tree looks like:

The minimum total cost to remove all the edges of this tree is $5$.

- Query $2$: The edge between $1$ and $3$ is removed and the edge between $2$ and $3$ is added. The tree looks like:

The minimum total cost to remove all the edges of this tree is $5$.

- Query $3$: The edge between $4$ and $1$ is removed and the edge between $1$ and $4$ is added. Thus, the tree remains the same as the initial tree.
The total cost of removing all the edges is $6$, as explained earlier.

- Query $4$: The edge between $2$ and $1$ is removed and the edge between $4$ and $2$ is added. The tree looks like:

The minimum total cost to remove all the edges of this tree is $5$.

Source: codechef | Difficulty: VERY_HARD
Tags: Tree algorithms

Graph algorithms

Data structures

Mathematics


Solutions:
for _ in range(int(input())):
	(nn, qqqq) = map(int, input().split())
	dddd = {i: 0 for i in range(1, nn + 1)}
	aaaa = {i: [] for i in range(1, nn + 1)}
	for _ in range(nn - 1):
		(xxxx, yyyy) = map(int, input().split())
		dddd[xxxx] += 1
		dddd[yyyy] += 1
	answer = 0
	for i in dddd:
		answer += dddd[i] * (dddd[i] + 1) // 2
	answer -= nn - 1
	print(answer)
	for _ in range(qqqq):
		(wwww, xxxx, yyyy, zzzz) = map(int, input().split())
		cccc = answer
		cccc -= dddd[wwww]
		cccc -= dddd[xxxx]
		cccc += dddd[yyyy]
		cccc += dddd[zzzz]
		if wwww == yyyy and xxxx == zzzz or (wwww == zzzz and xxxx == yyyy):
			cccc += 0
		elif wwww == yyyy or wwww == zzzz or xxxx == yyyy or (xxxx == zzzz):
			cccc += 1
		else:
			cccc += 2
		print(cccc)


for _ in range(int(input())):
	(na, qu) = map(int, input().split())
	daa = {i: 0 for i in range(1, na + 1)}
	avv = {i: [] for i in range(1, na + 1)}
	for _ in range(na - 1):
		(x, y) = map(int, input().split())
		daa[x] += 1
		daa[y] += 1
	sol = 0
	for i in daa:
		sol = sol + daa[i] * (daa[i] + 1) // 2
	sol -= na - 1
	print(sol)
	for _ in range(qu):
		(w, x, y, z) = map(int, input().split())
		c = sol
		c -= daa[w]
		c -= daa[x]
		c += daa[y]
		c += daa[z]
		if w == y and x == z or (w == z and x == y):
			c += 0
		elif w == y or w == z or x == y or (x == z):
			c += 1
		else:
			c += 2
		print(c)


for _ in range(int(input())):
	(o, p) = map(int, input().split())
	y = {i: 0 for i in range(1, o + 1)}
	e = {i: [] for i in range(1, o + 1)}
	for _ in range(o - 1):
		(s, k) = map(int, input().split())
		y[s] += 1
		y[k] += 1
	sol = 0
	for iii in y:
		sol = sol + y[iii] * (y[iii] + 1) // 2
	sol -= o - 1
	print(sol)
	for _ in range(p):
		(z, s, k, t) = map(int, input().split())
		a = sol
		a -= y[z]
		a -= y[s]
		a += y[k]
		a += y[t]
		if z == k and s == t or (z == t and s == k):
			a += 0
		elif z == k or z == t or s == k or (s == t):
			a += 1
		else:
			a += 2
		print(a)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	d = {i: 0 for i in range(1, n + 1)}
	a = {i: [] for i in range(1, n + 1)}
	for _ in range(n - 1):
		(x, y) = map(int, input().split())
		d[x] += 1
		d[y] += 1
	s = 0
	for i in d:
		s = s + d[i] * (d[i] + 1) // 2
	s -= n - 1
	print(s)
	for _ in range(q):
		(w, x, y, z) = map(int, input().split())
		c = s
		c -= d[w]
		c -= d[x]
		c += d[y]
		c += d[z]
		if w == y and x == z or (w == z and x == y):
			c += 0
		elif w == y or w == z or x == y or (x == z):
			c += 1
		else:
			c += 2
		print(c)


for _ in range(int(input())):
	(c, p) = map(int, input().split())
	m = {i: 0 for i in range(1, c + 1)}
	n = {i: [] for i in range(1, c + 1)}
	for _ in range(c - 1):
		(s, k) = map(int, input().split())
		m[s] += 1
		m[k] += 1
	sol = 0
	for i in m:
		sol = sol + m[i] * (m[i] + 1) // 2
	sol -= c - 1
	print(sol)
	for _ in range(p):
		(z, s, k, t) = map(int, input().split())
		a = sol
		a -= m[z]
		a -= m[s]
		a += m[k]
		a += m[t]
		if z == k and s == t or (z == t and s == k):
			a += 0
		elif z == k or z == t or s == k or (s == t):
			a += 1
		else:
			a += 2
		print(a)


for _ in range(int(input())):
	(o, p) = map(int, input().split())
	y = {i: 0 for i in range(1, o + 1)}
	ep = {i: [] for i in range(1, o + 1)}
	for _ in range(o - 1):
		(sr, kh) = map(int, input().split())
		y[sr] += 1
		y[kh] += 1
	sol = 0
	for i in y:
		sol = sol + y[i] * (y[i] + 1) // 2
	sol -= o - 1
	print(sol)
	for _ in range(p):
		(z, sr, kh, t) = map(int, input().split())
		a = sol
		a -= y[z]
		a -= y[sr]
		a += y[kh]
		a += y[t]
		if z == kh and sr == t or (z == t and sr == kh):
			a += 0
		elif z == kh or z == t or sr == kh or (sr == t):
			a += 1
		else:
			a += 2
		print(a)


for _ in range(int(input())):
	(mn, pq) = map(int, input().split())
	jaa = {i: 0 for i in range(1, mn + 1)}
	dvv = {i: [] for i in range(1, mn + 1)}
	for _ in range(mn - 1):
		(s, h) = map(int, input().split())
		jaa[s] += 1
		jaa[h] += 1
	sol = 0
	for i in jaa:
		sol = sol + jaa[i] * (jaa[i] + 1) // 2
	sol -= mn - 1
	print(sol)
	for _ in range(pq):
		(r, s, h, e) = map(int, input().split())
		y = sol
		y -= jaa[r]
		y -= jaa[s]
		y += jaa[h]
		y += jaa[e]
		if r == h and s == e or (r == e and s == h):
			y += 0
		elif r == h or r == e or s == h or (s == e):
			y += 1
		else:
			y += 2
		print(y)


from copy import deepcopy
T = int(input())
for _ in range(T):
	(N, P) = map(int, input().split())
	degree = [0] * (N + 1)
	degree[0] = N + 1
	for i in range(N - 1):
		ed = list(map(int, input().split()))
		for j in range(2):
			degree[ed[j]] += 1
	cost = 1
	for i in range(1, N + 1):
		K = degree[i]
		cost += K * (K + 1) // 2 - 1
	ini_cost = cost
	print(cost)
	for i in range(P):
		(A, B, C, D) = map(int, input().split())
		net_add = 0
		degree[A] -= 1
		degree[B] -= 1
		if degree[A] >= 1:
			net_add -= degree[A] + 1
		if degree[B] >= 1:
			net_add -= degree[B] + 1
		degree[C] += 1
		degree[D] += 1
		if degree[C] > 1:
			net_add += degree[C]
		if degree[D] > 1:
			net_add += degree[D]
		cost += net_add
		print(cost)
		cost = ini_cost
		degree[A] += 1
		degree[B] += 1
		degree[C] -= 1
		degree[D] -= 1


for _ in range(int(input())):
	(v, u) = map(int, input().split())
	x = {i: 0 for i in range(1, v + 1)}
	y = {i: [] for i in range(1, v + 1)}
	for _ in range(v - 1):
		(s, k) = map(int, input().split())
		x[s] += 1
		x[k] += 1
	sol = 0
	for i in x:
		sol = sol + x[i] * (x[i] + 1) // 2
	sol -= v - 1
	print(sol)
	for _ in range(u):
		(z, s, k, t) = map(int, input().split())
		a = sol
		a -= x[z]
		a -= x[s]
		a += x[k]
		a += x[t]
		if z == k and s == t or (z == t and s == k):
			a += 0
		elif z == k or z == t or s == k or (s == t):
			a += 1
		else:
			a += 2
		print(a)


from copy import deepcopy
at = int(input())
for _ in range(at):
	(n, q) = map(int, input().split())
	degree = [0] * (n + 1)
	degree[0] = n + 1
	for i in range(n - 1):
		edge = list(map(int, input().split()))
		for j in range(2):
			degree[edge[j]] += 1
	cost = 1
	for i in range(1, n + 1):
		k = degree[i]
		cost += k * (k + 1) // 2 - 1
	ini_cost = cost
	print(cost)
	for i in range(q):
		(a, b, c, d) = map(int, input().split())
		net_add = 0
		degree[a] -= 1
		degree[b] -= 1
		if degree[a] >= 1:
			net_add -= degree[a] + 1
		if degree[b] >= 1:
			net_add -= degree[b] + 1
		degree[c] += 1
		degree[d] += 1
		if degree[c] > 1:
			net_add += degree[c]
		if degree[d] > 1:
			net_add += degree[d]
		cost += net_add
		print(cost)
		cost = ini_cost
		degree[a] += 1
		degree[b] += 1
		degree[c] -= 1
		degree[d] -= 1


from copy import deepcopy
for i in range(int(input())):
	(a, b) = map(int, input().split())
	degree = [0] * (a + 1)
	degree[0] = a + 1
	for i in range(a - 1):
		edge = list(map(int, input().split()))
		for j in range(2):
			degree[edge[j]] += 1
	cost = 1
	for i in range(1, a + 1):
		k = degree[i]
		cost += k * (k + 1) // 2 - 1
	ini_cost = cost
	print(cost)
	for i in range(b):
		(w, x, y, z) = map(int, input().split())
		net_add = 0
		degree[w] -= 1
		degree[x] -= 1
		if degree[w] >= 1:
			net_add -= degree[w] + 1
		if degree[x] >= 1:
			net_add -= degree[x] + 1
		degree[y] += 1
		degree[z] += 1
		if degree[y] > 1:
			net_add += degree[y]
		if degree[z] > 1:
			net_add += degree[z]
		cost += net_add
		print(cost)
		cost = ini_cost
		degree[w] += 1
		degree[x] += 1
		degree[y] -= 1
		degree[z] -= 1


from copy import deepcopy
from collections import deque

def f(n, Sol):
	q = deque()
	for i in range(n):
		if ind2[i] == 1:
			q.append(i)
	while q:
		t = q.popleft()
		exp[t] = 1
		for j in adj[t]:
			if not exp[j - 1]:
				Sol += ind2[j - 1]
		for i in adj[t]:
			ind2[i - 1] -= 1
			if ind2[i - 1] == 1:
				q.append(i - 1)
	return Sol
T = int(input())
for t in range(T):
	(n, q) = map(int, input().split())
	adj = [[] for i in range(n)]
	ind = [0] * n
	exp = [0] * n
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		adj[u - 1].append(v)
		adj[v - 1].append(u)
		ind[u - 1] += 1
		ind[v - 1] += 1
	Sol = 0
	ind2 = ind.copy()
	Sol = f(n, Sol)
	print(Sol)
	for i in range(q):
		(a, b, c, d) = map(int, input().split())
		res2 = deepcopy(Sol)
		res2 -= ind[a - 1] + ind[b - 1]
		if a == c or b == c:
			res2 += ind[c - 1]
		else:
			res2 += ind[c - 1] + 1
		if a == d or b == d:
			res2 += ind[d - 1]
		else:
			res2 += ind[d - 1] + 1
		print(res2)


for _ in range(int(input())):
	(u, p) = map(int, input().split())
	Q = {i: 0 for i in range(1, u + 1)}
	e = {i: [] for i in range(1, u + 1)}
	for _ in range(u - 1):
		(s, l) = map(int, input().split())
		Q[s] += 1
		Q[l] += 1
	sol = 0
	for i in Q:
		sol = sol + Q[i] * (Q[i] + 1) // 2
	sol -= u - 1
	print(sol)
	for _ in range(p):
		(z, s, l, t) = map(int, input().split())
		a = sol
		a -= Q[z]
		a -= Q[s]
		a += Q[l]
		a += Q[t]
		if z == l and s == t or (z == t and s == l):
			a += 0
		elif z == l or z == t or s == l or (s == t):
			a += 1
		else:
			a += 2
		print(a)


from sys import stdin, setrecursionlimit
input = stdin.readline
setrecursionlimit(2 * 10 ** 5)

def dfs(p, prev, lvl):
	parent[p] = prev
	level[lvl].append(p)
	for i in child[p]:
		if i == prev:
			continue
		dfs(i, p, lvl + 1)

def answer():
	original_deg = deg[:]
	ans = 0
	for p in range(n - 1, 0, -1):
		for i in level[p]:
			ans += deg[i] * deg[parent[i]]
			deg[parent[i]] -= 1
	print(ans)
	for query in range(q):
		(u1, v1, u2, v2) = map(int, input().split())
		query_ans = ans
		query_ans -= original_deg[u1] - 1 + original_deg[v1] - 1
		original_deg[u1] -= 1
		original_deg[v1] -= 1
		query_ans += original_deg[u2] + original_deg[v2]
		original_deg[u1] += 1
		original_deg[v1] += 1
		print(query_ans)
for T in range(int(input())):
	(n, q) = map(int, input().split())
	deg = [0 for i in range(n + 1)]
	child = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		child[u].append(v)
		child[v].append(u)
		deg[u] += 1
		deg[v] += 1
	level = [[] for i in range(n)]
	parent = [-1 for i in range(n + 1)]
	dfs(1, -1, 0)
	answer()


for _ in range(int(input())):
	(m, q) = map(int, input().split())
	jvv = {i: 0 for i in range(1, m + 1)}
	ahh = {i: [] for i in range(1, m + 1)}
	for _ in range(m - 1):
		(s, h) = map(int, input().split())
		jvv[s] += 1
		jvv[h] += 1
	sol = 0
	for i in jvv:
		sol = sol + jvv[i] * (jvv[i] + 1) // 2
	sol -= m - 1
	print(sol)
	for _ in range(q):
		(r, s, h, e) = map(int, input().split())
		v = sol
		v -= jvv[r]
		v -= jvv[s]
		v += jvv[h]
		v += jvv[e]
		if r == h and s == e or (r == e and s == h):
			v += 0
		elif r == h or r == e or s == h or (s == e):
			v += 1
		else:
			v += 2
		print(v)


for _ in range(int(input())):
	(nady, qudy) = map(int, input().split())
	daa = {i: 0 for i in range(1, nady + 1)}
	avv = {i: [] for i in range(1, nady + 1)}
	for _ in range(nady - 1):
		(x, y) = map(int, input().split())
		daa[x] += 1
		daa[y] += 1
	sol = 0
	for i in daa:
		sol = sol + daa[i] * (daa[i] + 1) // 2
	sol -= nady - 1
	print(sol)
	for _ in range(qudy):
		(w, x, y, z) = map(int, input().split())
		con = sol
		con -= daa[w]
		con -= daa[x]
		con += daa[y]
		con += daa[z]
		if w == y and x == z or (w == z and x == y):
			con += 0
		elif w == y or w == z or x == y or (x == z):
			con += 1
		else:
			con += 2
		print(con)


for _ in range(int(input())):
	(na, qu) = map(int, input().split())
	daa = {i: 0 for i in range(1, na + 1)}
	avv = {i: [] for i in range(1, na + 1)}
	for _ in range(na - 1):
		(a, b) = map(int, input().split())
		daa[a] += 1
		daa[b] += 1
	sol = 0
	for i in daa:
		sol = sol + daa[i] * (daa[i] + 1) // 2
	sol -= na - 1
	print(sol)
	for _ in range(qu):
		(u, a, b, z) = map(int, input().split())
		c = sol
		c -= daa[u]
		c -= daa[a]
		c += daa[b]
		c += daa[z]
		if u == b and a == z or (u == z and a == b):
			c += 0
		elif u == b or u == z or a == b or (a == z):
			c += 1
		else:
			c += 2
		print(c)


for smart in range(int(input())):
	(nani, qit) = map(int, input().split())
	po = {ma: 0 for ma in range(1, nani + 1)}
	avv = {ma: [] for ma in range(1, nani + 1)}
	for smart in range(nani - 1):
		(xak, yak) = map(int, input().split())
		po[xak] += 1
		po[yak] += 1
	loc = 0
	for ma in po:
		loc = loc + po[ma] * (po[ma] + 1) // 2
	loc -= nani - 1
	print(loc)
	for smart in range(qit):
		(wak, xak, yak, zak) = map(int, input().split())
		cot = loc
		cot -= po[wak]
		cot -= po[xak]
		cot += po[yak]
		cot += po[zak]
		if wak == yak and xak == zak or (wak == zak and xak == yak):
			cot += 0
		elif wak == yak or wak == zak or xak == yak or (xak == zak):
			cot += 1
		else:
			cot += 2
		print(cot)


for x in range(int(input())):
	(o, p) = map(int, input().split())
	r = {i: 0 for i in range(1, o + 1)}
	e = {i: [] for i in range(1, o + 1)}
	for y in range(o - 1):
		(s, k) = map(int, input().split())
		r[s] += 1
		r[k] += 1
	ans = 0
	for i in r:
		ans = ans + r[i] * (r[i] + 1) // 2
	ans -= o - 1
	print(ans)
	for _ in range(p):
		(z, s, k, t) = map(int, input().split())
		a = ans
		a -= r[z]
		a -= r[s]
		a += r[k]
		a += r[t]
		if z == k and s == t or (z == t and s == k):
			a += 0
		elif z == k or z == t or s == k or (s == t):
			a += 1
		else:
			a += 2
		print(a)


for _ in range(int(input())):
	(ha, ku) = map(int, input().split())
	paa = {j: 0 for j in range(1, ha + 1)}
	lvv = {j: [] for j in range(1, ha + 1)}
	for _ in range(ha - 1):
		(s, f) = map(int, input().split())
		paa[s] += 1
		paa[f] += 1
	sol = 0
	for j in paa:
		sol = sol + paa[j] * (paa[j] + 1) // 2
	sol -= ha - 1
	print(sol)
	for _ in range(ku):
		(a, s, f, b) = map(int, input().split())
		d = sol
		d -= paa[a]
		d -= paa[s]
		d += paa[f]
		d += paa[b]
		if a == f and s == b or (a == b and s == f):
			d += 0
		elif a == f or a == b or s == f or (s == b):
			d += 1
		else:
			d += 2
		print(d)


for j in range(int(input())):
	(num, qum) = map(int, input().split())
	daa = {i: 0 for i in range(1, num + 1)}
	avv = {i: [] for i in range(1, num + 1)}
	for _ in range(num - 1):
		(x, y) = map(int, input().split())
		daa[x] += 1
		daa[y] += 1
	sol = 0
	for i in daa:
		sol = sol + daa[i] * (daa[i] + 1) // 2
	sol -= num - 1
	print(sol)
	for _ in range(qum):
		(w, x, y, z) = map(int, input().split())
		c = sol
		c -= daa[w]
		c -= daa[x]
		c += daa[y]
		c += daa[z]
		if w == y and x == z or (w == z and x == y):
			c += 0
		elif w == y or w == z or x == y or (x == z):
			c += 1
		else:
			c += 2
		print(c)


for _ in range(int(input())):
	(nas, qus) = map(int, input().split())
	daat = {i: 0 for i in range(1, nas + 1)}
	avv = {i: [] for i in range(1, nas + 1)}
	for _ in range(nas - 1):
		(x, y) = map(int, input().split())
		daat[x] += 1
		daat[y] += 1
	sol = 0
	for i in daat:
		sol = sol + daat[i] * (daat[i] + 1) // 2
	sol -= nas - 1
	print(sol)
	for _ in range(qus):
		(w, x, y, z) = map(int, input().split())
		c = sol
		c -= daat[w]
		c -= daat[x]
		c += daat[y]
		c += daat[z]
		if w == y and x == z or (w == z and x == y):
			c += 0
		elif w == y or w == z or x == y or (x == z):
			c += 1
		else:
			c += 2
		print(c)


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

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

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

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

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def solve():
	(n, q) = mp()
	d = defaultdict(list)
	deg = defaultdict(int)
	for i in range(n - 1):
		(a, b) = mp()
		d[a].append(b)
		d[b].append(a)
		deg[a] += 1
		deg[b] += 1
	ans = 0
	for i in range(1, n + 1):
		ans += deg[i] * (deg[i] + 1) // 2
	ans -= n - 1
	pr(ans)
	for i in range(q):
		(a, b, c, d) = mp()
		cur = ans - (deg[a] + deg[b]) + deg[c] + deg[d]
		for x in [a, b]:
			for y in [c, d]:
				cur -= x == y
		pr(cur + 2)
for _ in range(inp()):
	solve()


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	graph = dict()
	degree = [0 for i in range(n + 1)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		if u not in graph.keys():
			graph[u] = [v]
		else:
			graph[u].append(v)
		degree[u] += 1
		if v not in graph.keys():
			graph[v] = [u]
		else:
			graph[v].append(u)
		degree[v] += 1
	ansa = 0
	for x in graph.keys():
		d = degree[x]
		if x != 1:
			ansa -= 1
		ansa += d * (d + 1) // 2
	print(ansa)
	for i in range(q):
		ansaa = ansa
		(a, b, c, d) = map(int, input().split())
		st = set([a, b, c, d])
		for x in st:
			temp = degree[x]
			ansaa -= temp * (temp + 1) // 2
			if x != 1:
				ansaa += 1
		degree[a] -= 1
		degree[b] -= 1
		degree[c] += 1
		degree[d] += 1
		for x in st:
			t = degree[x]
			ansaa += t * (t + 1) // 2
			if x != 1:
				ansaa -= 1
		degree[a] += 1
		degree[b] += 1
		degree[c] -= 1
		degree[d] -= 1
		print(ansaa)