You are given a $n \times n$ chessboard. Rows and columns of the board are numbered from $1$ to $n$. Cell $(x, y)$ lies on the intersection of column number $x$ and row number $y$.

Rook is a chess piece, that can in one turn move any number of cells vertically or horizontally. There are $m$ rooks ($m < n$) placed on the chessboard in such a way that no pair of rooks attack each other. I.e. there are no pair of rooks that share a row or a column.

In one turn you can move one of the rooks any number of cells vertically or horizontally. Additionally, it shouldn't be attacked by any other rook after movement. What is the minimum number of moves required to place all the rooks on the main diagonal?

The main diagonal of the chessboard is all the cells $(i, i)$, where $1 \le i \le n$.


-----Input-----

The first line contains the number of test cases $t$ ($1 \leq t \leq 10^3$). Description of the $t$ test cases follows.

The first line of each test case contains two integers $n$ and $m$ — size of the chessboard and the number of rooks ($2 \leq n \leq 10^5$, $1 \leq m < n$). Each of the next $m$ lines contains two integers $x_i$ and $y_i$ — positions of rooks, $i$-th rook is placed in the cell $(x_i, y_i)$ ($1 \leq x_i, y_i \leq n$). It's guaranteed that no two rooks attack each other in the initial placement.

The sum of $n$ over all test cases does not exceed $10^5$.


-----Output-----

For each of $t$ test cases print a single integer — the minimum number of moves required to place all the rooks on the main diagonal.

It can be proved that this is always possible.


-----Examples-----

Input
4
3 1
2 3
3 2
2 1
1 2
5 3
2 3
3 1
1 2
5 4
4 5
5 1
2 2
3 3
Output
1
3
4
2


-----Note-----

Possible moves for the first three test cases:

$(2, 3) \to (2, 2)$

$(2, 1) \to (2, 3)$, $(1, 2) \to (1, 1)$, $(2, 3) \to (2, 2)$

$(2, 3) \to (2, 4)$, $(2, 4) \to (4, 4)$, $(3, 1) \to (3, 3)$, $(1, 2) \to (1, 1)$

Difficulty: MEDIUM_HARD
Tags: Spanning trees

Graph algorithms

Graph traversal

Starter code:

Solutions:
T = int(input())
for iw in range(T):
	(n, m) = map(int, input().split())
	ans = 0
	X = [-1] * (n + 1)
	for i in range(m):
		(x, y) = map(int, input().split())
		if x != y:
			ans += 1
			X[x] = y
	for i in range(1, n + 1):
		if X[i] > 0:
			t = i
			while X[i] > 0:
				x = X[i]
				X[i] = 0
				i = x
				if i == t:
					ans += 1
					break
	print(ans)


def main():
	arr = [0] * 100001
	for _ in range(int(input())):
		(size, count) = map(int, input().split())
		for i in range(count):
			(x, y) = map(int, input().split())
			arr[x] = y
		cycles = 0
		petly = 0
		for i in range(1, size + 1):
			if arr[i] == i:
				petly += 1
				arr[i] = 0
			k = i
			while arr[k] != 0:
				temp = arr[k]
				arr[k] = 0
				k = temp
				if arr[k] == i:
					cycles += 1
					break
		print(count - petly + cycles)
main()


def find(i):
	k = i
	if p[i] == -1:
		return 0
	while 1:
		if p[i] == -1:
			break
		if p[i] == k:
			break
		l = i
		t = p[i]
		i = t
		p[l] = -1
	if p[i] == -1:
		return 0
	return 1
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	c = 0
	p = [-1] * (n + 1)
	for i in range(n + 1):
		p[i] = -1
	for i in range(m):
		(x, y) = map(int, input().split())
		if x != y:
			c += 1
			p[y] = x
	an = 0
	v = 0
	for i in range(n + 1):
		if p[i] != -1 and find(i) == 1:
			p[i] = -1
			v += 1
	print(c + v)


def solve():
	(n, m) = map(int, input().split())
	graph = dict()
	result = int()
	for _ in range(m):
		(x, y) = map(int, input().split())
		graph[x] = [y, False]
	for (key, value) in graph.items():
		if value[1] == False:
			graph[key][1] = True
			follow = graph[key][0]
			if follow != key:
				while True:
					if follow in graph and graph[follow][1] == False:
						graph[follow][1] = True
						result += 1
						follow = graph[follow][0]
						if follow == key:
							result += 1
							break
					else:
						break
				result += 1
	print(result)

def main():
	for _ in range(int(input())):
		solve()
main()


t = int(input())
for j in range(t):
	(n, m) = [int(i) for i in input().split()]
	arr = [-1 for i in range(n + 1)]
	vis = [True for i in range(n + 1)]
	for i in range(m):
		(x, y) = [int(k) for k in input().split()]
		if x != y:
			vis[x] = False
			arr[x] = y
	vis[0] = True
	ans = 0
	for i in range(n + 1):
		if vis[i] == False:
			start = arr[i]
			vis[i] = True
			count = 1
			while vis[start] == False:
				vis[start] = True
				count += 1
				start = arr[start]
				if start == i:
					count += 1
			ans += count
	print(ans)


def getfather(x, father):
	tmp_father = x
	if father[x] != x:
		tmp_father = getfather(father[x], father)
	else:
		tmp_father = x
	father[x] = tmp_father
	return tmp_father
T = int(input().strip())
for _ in range(T):
	line = input().strip().split()
	(n, m) = (int(line[0]), int(line[1]))
	result = 0
	father = [idx for idx in range(n + 1)]
	for _x in range(m):
		line = input().strip().split()
		(x, y) = (int(line[0]), int(line[1]))
		if x == y:
			continue
		t1 = getfather(x, father)
		t2 = getfather(y, father)
		if t1 != t2:
			result += 1
			father[t1] = t2
		else:
			result += 2
	print(result)


def dsu(x):
	p = x
	while v[x] != x:
		x = v[x]
	v[p] = x
	return x
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	ans = 0
	v = [i for i in range(n + 1)]
	ans = 0
	for _ in range(m):
		(a, b) = map(int, input().split())
		if a == b:
			continue
		ans += 1
		p = dsu(a)
		q = dsu(b)
		if p != q:
			v[p] = v[q]
		else:
			ans += 1
	print(ans)


for _ in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	l = [None] * (n + 1)
	for _ in range(m):
		(x, y) = [int(x) for x in input().split()]
		l[x] = y
	ans = 0
	visited = [False] * (n + 1)
	for i in range(n + 1):
		if l[i] == None or l[i] == i or visited[i]:
			continue
		(tmp, cnt) = (l[i], 1)
		visited[i] = True
		while tmp != i and tmp != None and (visited[tmp] == False):
			visited[tmp] = True
			tmp = l[tmp]
			cnt += 1
		cnt += tmp == i
		cnt -= tmp == None
		ans += cnt
	print(ans)


class Solution:

	def __init__(self, n: int, m: int):
		self.parent = list(range(n + 1))
		self.count = m

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

	def union(self, x: int, y: int):
		if x == y:
			self.count -= 1
			return
		x_p = self.find(x)
		y_p = self.find(y)
		if x_p == y_p:
			self.count += 1
		else:
			self.parent[x_p] = y_p

	def get_count(self):
		return self.count
t = int(input())
while t > 0:
	t -= 1
	(n, m) = input().split(' ')
	(n, m) = (int(n), int(m))
	so = Solution(n, m)
	for _ in range(m):
		(x, y) = input().split(' ')
		(x, y) = (int(x), int(y))
		so.union(x, y)
	print(so.get_count())


import sys
import math, bisect, operator
(inf, m) = (float('inf'), 10 ** 9 + 7)
sys.setrecursionlimit(10 ** 6)
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 tt in range(int(input())):
	(x, y) = map(int, input().split())
	l = [0] * (x + 1)
	v = [0] * (x + 1)
	for i in range(y):
		(a, b) = map(int, input().split())
		l[a] = b
	c = 0
	for i in range(1, x + 1):
		if l[i] != i:
			temp = i
			while v[temp] != 1 and l[temp] != 0:
				c += 1
				v[temp] = 1
				temp = l[temp]
				if temp == i:
					c += 1
					break
	print(c)


def move_nu(allPoints, m):
	n = len(allPoints)
	xlab = [-1] * m
	ylab = [-1] * m
	xexi = [0] * m
	exnum = 0
	xynum = 0
	for point in allPoints:
		xlab[point[0] - 1] = point[1] - 1
		ylab[point[1] - 1] = point[0] - 1
	for point in allPoints:
		x0 = point[0] - 1
		y0 = point[1] - 1
		if xexi[x0]:
			continue
		if x0 == y0:
			xynum += 1
			continue
		y1 = y0
		x1 = x0
		while xexi[x1] == 0 and xlab[x1] != -1:
			xexi[x1] = 1
			x1 = y1
			y1 = xlab[x1]
		if xlab[x1] != -1:
			exnum += 1
		elif ylab[x0] != -1:
			x1 = ylab[x0]
			while x1 != -1 and xexi[x1] == 0:
				xexi[x1] = 1
				x1 = ylab[x1]
	return n - xynum + exnum
n = int(input())
ans = []
for i in range(n):
	ll = input().split()
	allpoints = []
	for j in range(int(ll[1])):
		allpoints.append(tuple(map(int, input().split())))
	ans.append(move_nu(allpoints, int(ll[0])))
for i in ans:
	print(i)


import sys
if not sys.warnoptions:
	import warnings
	warnings.simplefilter('ignore')

def ii():
	return int(input())

def li():
	return [int(i) for i in input().split()]

def ls():
	return [i for i in input().split()]
for t in range(ii()):
	(n, m) = li()
	store = [-1 for i in range(n)]
	for i in range(m):
		(x, y) = li()
		x -= 1
		y -= 1
		store[x] = y
	vis = [0 for i in range(n)]
	ans = 0
	for i in range(n):
		if store[i] != -1:
			if store[i] != i:
				ans += 1
				root = i
				cnt = 0
				while vis[root] == 0:
					vis[root] = 1
					if store[root] == -1:
						break
					else:
						cnt += 1
						root = store[root]
				if root == i and cnt > 0:
					ans += 1
			else:
				vis[i] = 1
		else:
			vis[i] = 1
	print(ans)


for l in range(int(input())):
	(n, m) = map(int, input().split())
	res = 0
	table = dict()
	for i in range(m):
		(a, b) = map(int, input().split())
		table[a] = [b, False]
	for key in table:
		if table[key][1] == False:
			table[key][1] = True
			temp_key = table[key][0]
			if key != temp_key:
				while True:
					if table.get(temp_key):
						if table[temp_key][1] == True:
							break
						res += 1
						table[temp_key][1] = True
						temp_key = table[temp_key][0]
						if temp_key == key:
							res += 1
							break
					else:
						break
				res += 1
	print(res)


for _ in range(int(input())):
	(n, m) = list(map(int, input().split(' ')))
	rook_poses = {}
	for _ in range(m):
		(x, y) = tuple(map(int, input().split(' ')))
		if x != y:
			rook_poses[x] = y
	num_moves = 0
	cycle = set()
	unvisited = set(rook_poses.keys())
	while unvisited:
		x = unvisited.pop()
		cycle.add(x)
		y = rook_poses[x]
		num_moves += 1
		while y in unvisited:
			x = y
			unvisited.remove(x)
			cycle.add(x)
			y = rook_poses[x]
			num_moves += 1
		if y in cycle:
			num_moves += 1
		cycle.clear()
	print(num_moves)


t = int(input())
for j in range(0, t):
	(n, m) = map(int, input().split())
	c = 0
	g = {}
	p = []
	d = {}
	for kk in range(0, m):
		(a, b) = map(int, input().split())
		if a != b:
			p.append(a)
			g[a] = b
			d[a] = 0
	cc = 0
	for tt in p:
		s = tt
		o = s
		fl = 0
		if d[o] == 0:
			while o in d and d[o] == 0:
				cc += 1
				d[o] = 1
				if o in g:
					if g[o] == s:
						fl = 1
						break
					o = g[o]
				else:
					fl = 0
					break
			if fl == 1:
				cc += 1
	print(cc + c)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().strip().split())
	xs = set()
	ys = set()
	xd = []
	yd = []
	x = [0] * (n + 1)
	y = [0] * (n + 1)
	for _ in range(m):
		(i, j) = map(int, input().strip().split())
		xd.append(i)
		yd.append(j)
		x[i] = j
		y[j] = i
		xs.add(i)
		ys.add(j)
	count = 0
	for i in range(m):

		def inner():
			if xd[i] == yd[i]:
				return 0
			if x[xd[i]] == 0:
				return 0
			if xd[i] not in ys:
				lc = 1
				num = x[xd[i]]
				x[xd[i]] = 0
				while num in xs:
					lc += 1
					t = x[num]
					x[num] = 0
					num = t
				return lc
			else:
				lc = 1
				num = x[xd[i]]
				x[xd[i]] = 0
				while num in xs:
					if x[num] == 0:
						return lc + 1
					lc += 1
					t = x[num]
					x[num] = 0
					num = t
				lc += 1
				num = y[xd[i]]
				x[y[xd[i]]] = 0
				while num in ys:
					lc += 1
					t = y[num]
					x[y[num]] = 0
					num = t
				return lc
			return 0
		count += inner()
	print(count)


import sys, threading
sys.setrecursionlimit(500000)
threading.stack_size(134217728)
from collections import defaultdict

def solve():

	def dfs(node, visited, parent, an):
		visited[node] = 1
		for v in g[node]:
			if visited[v] == 0:
				dfs(v, visited, node, an)
			elif v != parent:
				an[0] = 1
	f = 0
	t = int(input())
	for i in range(t):
		g = defaultdict(list)
		(n, m) = map(int, input().split())
		p = 0
		for j in range(m):
			(u, v) = map(int, sys.stdin.readline().split())
			if u != v:
				g[u].append(v)
				g[v].append(u)
				p = p + 1
		visited = [0] * (n + 1)
		for j in range(1, n + 1):
			if visited[j] == 0 and j in g:
				an = [0]
				dfs(j, visited, -1, an)
				p = p + an[0]
		print(p)
threading.Thread(target=solve).start()


class UnionFind:

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

	def findset(self, x: int) -> int:
		if self.parent[x] == x:
			return x
		self.parent[x] = self.findset(self.parent[x])
		return self.parent[x]

	def unite(self, x: int, y: int) -> bool:
		(x, y) = (self.findset(x), self.findset(y))
		if x == y:
			return False
		if self.size[x] < self.size[y]:
			(x, y) = (y, x)
		self.parent[y] = x
		self.size[x] += self.size[y]
		self.setCount -= 1
		return True

	def connected(self, x: int, y: int) -> bool:
		(x, y) = (self.findset(x), self.findset(y))
		return x == y
T = int(input())
while T:
	(n, m) = map(int, input().split(' '))
	uf = UnionFind(n)
	ok = 0
	huan = 0
	for _ in range(m):
		(x, y) = map(int, input().split(' '))
		if x == y:
			ok += 1
		elif not uf.unite(x - 1, y - 1):
			huan += 1
	print(m + huan - ok)
	T -= 1


sa = lambda : input()
sb = lambda : int(input())
sc = lambda : input().split()
sd = lambda : list(map(int, input().split()))
se = lambda : float(input())

class Disjoint_SU:

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

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

	def jod(self, a, b):
		x = self.lake_de(a)
		y = self.lake_de(b)
		if x == y:
			return True
		if self.size[x] > self.size[y]:
			self.size[x] += self.size[y]
			self.parent[y] = x
		else:
			self.size[y] += self.size[x]
			self.parent[x] = y
		return False

def hnbhai():
	(n, m) = sd()
	obj = Disjoint_SU(n)
	total = 0
	for i in range(m):
		(x, y) = sd()
		x -= 1
		y -= 1
		if x == y:
			continue
		total += 1
		if obj.jod(x, y):
			total += 1
	print(total)
for _ in range(sb()):
	hnbhai()


def untie(r, c, d, i, x, y, e):
	res = 0
	u = i
	t = set()
	(ux, uy) = d[u]
	if ux == uy:
		return (0, set([u]))
	while 1:
		if not ux in c or c[ux] in e:
			t.add(u)
			res += 1
			return (res, t)
		res += 1
		t.add(u)
		u = c[ux]
		(ux, uy) = d[u]
		if u == i:
			res += 1
			return (res, t)
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	r = {}
	c = {}
	d = []
	res = 0
	e = set()
	for i in range(m):
		(x, y) = map(int, input().split())
		r[x] = i
		c[y] = i
		d += [[x, y]]
	for i in range(m):
		(x, y) = d[i]
		if i in e:
			continue
		(a, b) = untie(r, c, d, i, x, y, e)
		e = e.union(b)
		res += a
	print(res)


lm = lambda : list(map(int, input().split()))
ii = lambda : int(input())

class sabar_karo:

	def __init__(self, n):
		self.baap = [i for i in range(n)]
		self.aukat = [1 for _ in range(n)]

	def pata_karo(self, a):
		if a == self.baap[a]:
			return a
		self.baap[a] = self.pata_karo(self.baap[a])
		return self.baap[a]

	def daya(self, a, b):
		x = self.pata_karo(a)
		y = self.pata_karo(b)
		a = x
		b = y
		if x == y:
			return True
		elif self.aukat[a] > self.aukat[b]:
			self.aukat[a] += self.aukat[b]
			self.baap[b] = a
		else:
			self.aukat[b] += self.aukat[a]
			self.baap[a] = b
		return False

def ruko_jara():
	(n, m) = lm()
	x = sabar_karo(n)
	ans = 0
	for _ in range(m):
		(u, v) = lm()
		if u == v:
			continue
		ans += 1
		if x.daya(u - 1, v - 1):
			ans += 1
	print(ans)
for _ in range(ii()):
	ruko_jara()


import sys, threading
sys.setrecursionlimit(500000)
threading.stack_size(134217728)
from collections import defaultdict

def solve():

	def dfs(node, visited, parent, loop):
		visited[node] = 1
		for v in graph[node]:
			if visited[v] == 0:
				dfs(v, visited, node, loop)
			elif v != parent:
				loop[0] = 1
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		ans = 0
		graph = defaultdict(list)
		for i in range(m):
			(x, y) = map(int, input().split())
			if x != y:
				graph[x].append(y)
				graph[y].append(x)
				ans += 1
		visited = [0] * (n + 1)
		for i in range(1, n + 1):
			if visited[i] == 0 and i in graph:
				loop = [0]
				dfs(i, visited, -1, loop)
				ans += loop[0]
		print(ans)
threading.Thread(target=solve).start()


from collections import defaultdict
import sys
t = int(input())
sys.setrecursionlimit(100000000)

def rek():
	while stack:
		k = stack.pop()
		(a, b) = k
		tmp[0] += 1
		w[k] = True
		if ver[a]:
			if not w[ver[a]]:
				w[ver[a]] = True
				stack.append(ver[a])
		else:
			check[0] = False
		if st[b]:
			if not w[st[b]]:
				w[st[b]] = True
				stack.append(st[b])
		else:
			check[0] = False
for _ in range(t):
	(n, m) = map(int, input().split())
	(st, ver) = (defaultdict(tuple), defaultdict(tuple))
	ar = []
	for _ in range(m):
		(a, b) = map(int, input().split())
		q = (a, b)
		ar.append(q)
		st[a] = q
		ver[b] = q
	res = 0
	w = defaultdict(bool)
	for (a, b) in ar:
		if a != b and (not w[a, b]):
			tmp = [0]
			check = [True]
			stack = [(a, b)]
			rek()
			if check[0]:
				tmp[0] += 1
			res += tmp[0]
	print(res)


T = int(input())
for _ in range(T):
	(n, k) = map(int, input().split())
	lim = 10 ** 5 + 10
	A = [-1] * lim
	ans = 0
	flag = 0
	for i in range(k):
		(x, y) = map(int, input().split())
		if flag == 0:
			flag = 1
			res = x
		if x != y:
			ans += 1
			A[x] = y
		flag = 0
		x = res
		while True:
			temp = A[x]
			if temp == -1:
				break
			if temp == res:
				ans += 1
				break
			x = temp
	print(ans)


import sys, threading
sys.setrecursionlimit(200000)
threading.stack_size(10 ** 8)
from collections import defaultdict as dd

def dfs(x, y):
	global v, adj, b, c, d
	v[x] = 1
	c += 1
	for i in adj[x]:
		if not v[i]:
			dfs(i, x)
		elif i != y and y != -1 or (i == y and d[i, x] == 2):
			b += 2
			d[i, x] = 1
			d[x, i] = 1

def main():
	global v, adj, b, c, d
	for t in range(int(input())):
		(n, m) = map(int, input().split())
		adj = [[] for i in range(n + 1)]
		a = 0
		b = 0
		c = 0
		v = [0] * (n + 1)
		d = dd(int)
		for i in range(m):
			(x, y) = map(int, input().split())
			if x != y:
				adj[x].append(y)
				adj[y].append(x)
				d[x, y] += 1
				d[y, x] += 1
			else:
				a += 1
		ans = 0
		for j in range(1, n + 1):
			if not v[j]:
				c = 0
				dfs(j, -1)
				ans += c - 1
		print(ans + b)
z = threading.Thread(target=main)
z.start()
z.join()


import sys

def main():
	(n, m) = map(int, input().split())
	dct = dict()
	dots_visited = set()
	o = 0
	dct_dots = dict()
	dots = []
	for i in range(m):
		(x, y) = map(int, input().split())
		if x != y:
			if x in dct_dots:
				dct_dots[x].append(o)
			else:
				dct_dots[x] = [o]
			if y in dct_dots:
				dct_dots[y].append(o)
			else:
				dct_dots[y] = [o]
			dct[o] = set()
			dots.append([x, y])
			o += 1
	for i in dct_dots:
		if len(dct_dots[i]) == 2:
			dct[dct_dots[i][0]].add(dct_dots[i][1])
			dct[dct_dots[i][1]].add(dct_dots[i][0])
	cnt = 0
	for dot in range(o):
		if not dot in dots_visited:
			to_go = set()
			to_go.add(dot)
			st = set()
			while len(to_go) != 0:
				dt = to_go.pop()
				st.add(dt)
				dots_visited.add(dt)
				for i in dct[dt]:
					if not i in dots_visited:
						to_go.add(i)
			ways = set()
			for i in st:
				ways.add(dots[i][0])
				ways.add(dots[i][1])
			cnt += len(st)
			if len(ways) <= len(st):
				cnt += 1
	print(cnt)
t = int(input())
for i in range(t):
	main()


class UFS:

	def __init__(self):
		self.parent = {}

	def add(self, x):
		if x not in self.parent:
			self.parent[x] = x

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

	def isConnected(self, x, y):
		rootx = self.find(x)
		rooty = self.find(y)
		return rootx == rooty

	def union(self, x, y):
		rootx = self.find(x)
		rooty = self.find(y)
		if rootx != rooty:
			self.parent[rootx] = rooty

def solution(indexs):
	ufs = UFS()
	ans = 0
	for (i, j) in indexs:
		if i == j:
			continue
		ans += 1
		ufs.add((i, i))
		ufs.add((j, j))
		ufs.add((i, j))
		if ufs.isConnected((i, i), (j, j)):
			ans += 1
		ufs.union((i, i), (i, j))
		ufs.union((j, j), (i, j))
	return ans
T = int(input())
while T:
	T -= 1
	(n, m) = list(map(int, input().split()))
	indexs = []
	while m:
		(i, j) = list(map(int, input().split()))
		indexs.append((i, j))
		m -= 1
	ans = solution(indexs)
	print(ans)