There is a city with $N$ numbered $0 - N-1$ shops. A market is a place where we can reach from one shop to another using some road. There are $M$ roads in this city connecting each connecting any two shops. 
Find the number of markets in the city.
NOTE:  A market having only one shop is also a valid market.

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- First line of Each Test Case is $N, M$, denoting the number of shops and the number of roads respectively.
- Next M lines consist of two integers $A$ and $B$ denoting that there exists a road between Shop A and Shop B

-----Output:-----
For each testcase, output the number of markets.

-----Constraints-----
- $1 \leq T \leq 100$
- $1 \leq N,M \leq 10^3$
- $0 \leq A,B < N$

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

-----Sample Output:-----
2

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
from sys import stdin
from math import ceil, gcd

def dfs(src, visit):
	visit[src] = 1
	for nbr in d[src]:
		if visit[nbr] == 0:
			dfs(nbr, visit)
for _ in range(int(stdin.readline())):
	(n, m) = list(map(int, stdin.readline().split()))
	d = {}
	for i in range(m):
		(u, v) = list(map(int, stdin.readline().split()))
		if u in d:
			d[u].append(v)
		else:
			d[u] = [v]
		if v in d:
			d[v].append(u)
		else:
			d[v] = [u]
	visited = {}
	for i in range(n):
		visited[i] = 0
	ans = 0
	for i in range(n):
		if visited[i] == 0:
			ans += 1
			if i in d:
				dfs(i, visited)
	print(ans)


class Graph:

	def __init__(self, V):
		self.V = V
		self.adj = [[] for i in range(V)]

	def DFSUtil(self, temp, v, visited):
		visited[v] = True
		temp.append(v)
		for i in self.adj[v]:
			if visited[i] == False:
				temp = self.DFSUtil(temp, i, visited)
		return temp

	def addEdge(self, v, w):
		self.adj[v].append(w)
		self.adj[w].append(v)

	def connectedComponents(self):
		visited = []
		cc = []
		for i in range(self.V):
			visited.append(False)
		for v in range(self.V):
			if visited[v] == False:
				temp = []
				cc.append(self.DFSUtil(temp, v, visited))
		return cc
for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	g = Graph(n)
	for i in range(m):
		(u, v) = list(map(int, input().split()))
		g.addEdge(u, v)
	print(len(g.connectedComponents()))


from sys import stdin, stdout

class Graph:

	def __init__(self, V):
		self.V = V
		self.adj = [[] for i in range(V)]

	def DFSUtil(self, temp, v, visited):
		visited[v] = True
		temp.append(v)
		for i in self.adj[v]:
			if visited[i] == False:
				temp = self.DFSUtil(temp, i, visited)
		return temp

	def addEdge(self, v, w):
		self.adj[v].append(w)
		self.adj[w].append(v)

	def connectedComponents(self):
		visited = []
		cc = []
		for i in range(self.V):
			visited.append(False)
		for v in range(self.V):
			if visited[v] == False:
				temp = []
				cc.append(self.DFSUtil(temp, v, visited))
		return cc
for ii in range(int(input())):
	x = 1293781029873019827309128730918273
	(n, m) = map(int, input().split())
	g = Graph(n)
	for i in range(m):
		(nn, mm) = map(int, input().split())
		g.addEdge(nn, mm)
	c = g.connectedComponents()
	print(len(c))


for t in range(int(input())):
	total = 0

	def check(n, store):
		nonlocal edges, q, points
		if n in store:
			return
		for i in range(q):
			if n == edges[i][0]:
				edges[i][0] = -1
				x = edges[i][1]
				edges[i][1] = -1
				if x in points:
					check(x, store + [n])
			elif n == edges[i][1]:
				edges[i][1] = -1
				x = edges[i][0]
				edges[i][0] = -1
				if x in points:
					check(x, store + [n])
		points.remove(n)
	(n, q) = list(map(int, input().split()))
	edges = []
	points = [i for i in range(n)]
	for i in range(q):
		x = input().split()
		edges.append([int(x[0]), int(x[1])])
	for i in range(n):
		if i in points:
			total += 1
			check(i, [])
	print(total)


from collections import deque, defaultdict

def addEdge(graph, u, v):
	graph[u].append(v)

def bfs(graph, start):
	explored = []
	queue = deque([start])
	while queue:
		node = queue.popleft()
		if node not in explored:
			explored.append(node)
			neighbours = graph[node]
			for neighbour in neighbours:
				queue.append(neighbour)
	return explored

def delete(graph, n):
	try:
		del graph[n]
	except KeyError:
		pass
	for i in graph:
		try:
			graph[i].remove(n)
		except ValueError:
			continue
for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	graph = defaultdict(list)
	for i in range(m):
		(u, v) = list(map(str, input().split()))
		addEdge(graph, u, v)
		addEdge(graph, v, u)
	cnt = 0
	dele = []
	for i in range(n):
		if str(i) in dele:
			continue
		else:
			path = bfs(graph, str(i))
			for j in path:
				delete(graph, j)
				dele.append(j)
		cnt += 1
	print(cnt)


import sys
sys.setrecursionlimit(10 ** 5)
from collections import defaultdict
g = defaultdict(list)

def dfs(u, visited):
	visited[u] = True
	for v in g[u]:
		if not visited[v]:
			dfs(v, visited)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	g.clear()
	for _ in range(m):
		(u, v) = map(int, input().split())
		g[u].append(v)
		g[v].append(u)
	visited = [False] * n
	ans = 0
	for i in range(n):
		if not visited[i]:
			ans += 1
			dfs(i, visited)
	print(ans)


class DSU(object):

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

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

	def union(self, x, y):
		(rootA, rootB) = (self.find(x), self.find(y))
		if rootA != rootB:
			self.parents[rootA] = rootB

def solve():
	(n, m) = map(int, input().split())
	dsu = DSU(n)
	for i in range(m):
		(x, y) = map(int, input().split())
		dsu.union(x, y)
	cnt = 0
	for (i, x) in enumerate(dsu.parents):
		cnt += i == x
	print(cnt)
t = int(input())
while t:
	solve()
	t -= 1


from collections import *
for _ in range(int(input())):
	graph = defaultdict(list)

	def edge(x, y):
		graph[x].append(y)

	def deltafun(s, visited):
		visited[s] = 1
		for i in graph[s]:
			if visited[i] == 0:
				deltafun(i, visited)

	def delta(s):
		visited = [0] * n
		ans = 0
		for i in range(n):
			if visited[i] == 0:
				deltafun(i, visited)
				ans += 1
		return ans
	(n, m) = list(map(int, input().split()))
	for i in range(m):
		(a, b) = list(map(int, input().split()))
		edge(a, b)
		edge(b, a)
	print(delta(0))


from collections import defaultdict

def dfs(node):
	visit[node] = True
	nonlocal flag
	flag = 1
	for i in g[node]:
		if visit[i] == False:
			dfs(i)
for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	g = defaultdict(list)
	for i in range(m):
		(u, v) = list(map(int, input().split()))
		g[u].append(v)
		g[v].append(u)
	flag = 0
	c = 0
	visit = [False] * (n + 1)
	for i in range(0, n):
		if visit[i] == False:
			flag = 0
			dfs(i)
			if flag == 1:
				c += 1
	print(c)


from collections import defaultdict
l = []

def DFSUtil(d, temp, v, visited):
	visited[v] = True
	temp.append(v)
	for i in d[v]:
		if visited[i] == False:
			temp = DFSUtil(d, temp, i, visited)
	return temp

def connectedComponents(n):
	visited = []
	cc = []
	for i in range(n):
		visited.append(False)
	for v in range(n):
		if visited[v] == False:
			temp = []
			cc.append(DFSUtil(d, temp, v, visited))
	return cc
for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	d = defaultdict(list)
	for i in range(m):
		(x, y) = list(map(int, input().split()))
		d[x].append(y)
		d[y].append(x)
	l.append(len(connectedComponents(n)))
for i in l:
	print(i)


import sys
from sys import stdin, stdout
import math
import time
import random
from functools import lru_cache
from collections import Counter
import heapq

def Update(X, AX, BX, CX, DX, k, n):
	for i in range(k, n):
		tem = (AX * X[i - 2] + BX * X[i - 1] + CX) % DX + 1
		X.append(tem)

def my_function():
	print('Hello from a function')

def a(adj, s, visited):
	visited[s] = True
	for s in adj[s]:
		if not visited[s]:
			a(adj, s, visited)

def b(adj, src, n):
	visited = [False] * n
	ans = 0
	for i in range(n):
		if not visited[i]:
			ans += 1
			a(adj, i, visited)
	print(ans)

def e(adj, s, v):
	adj[s].append(v)
	adj[v].append(s)
try:
	for _ in range(int(input())):
		(n, m) = list(map(int, input().split()))
		adj = [[] for i in range(n + 1)]
		for i in range(m):
			(s, v) = list(map(int, input().split()))
			e(adj, s, v)
		b(adj, 0, n)
except EOFError as e:
	print(e)


class Graph:

	def __init__(self, V):
		self.V = V
		self.adj = [[] for i in range(V)]

	def dfs(self, temp, v, visited):
		visited[v] = True
		temp.append(v)
		for i in self.adj[v]:
			if visited[i] == False:
				temp = self.dfs(temp, i, visited)
		return temp

	def addEdge(self, v, w):
		self.adj[v].append(w)
		self.adj[w].append(v)

	def connectedComponents(self):
		visited = []
		cc = []
		for i in range(self.V):
			visited.append(False)
		for v in range(self.V):
			if visited[v] == False:
				temp = []
				cc.append(self.dfs(temp, v, visited))
		return cc
for _ in range(int(input())):
	(N, M) = map(int, input().split())
	g = Graph(N)
	for i in range(M):
		(a, b) = map(int, input().split())
		g.addEdge(a, b)
	print(len(g.connectedComponents()))


from collections import defaultdict

def solve(L, n):
	vis = [False] * n

	def dfs(s):
		vis[s] = True
		for i in L[s]:
			if not vis[i]:
				dfs(i)
	ans = 0
	for i in range(n):
		if not vis[i]:
			ans += 1
			dfs(i)
	return ans
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	adjList = defaultdict(list)
	for k in range(m):
		(a, b) = map(int, input().split())
		adjList[a].append(b)
		adjList[b].append(a)
	print(solve(adjList, n))


from collections import defaultdict

class graph:

	def __init__(self, n):
		self.v = n
		self.adj = defaultdict(list)

	def addedge(self, u, v):
		self.adj[u].append(v)
		self.adj[v].append(u)

	def connected(self):
		vis = [False] * self.v
		c = []
		for v in range(self.v):
			if vis[v] == False:
				temp = []
				c.append(self.util(temp, v, vis))
		return c

	def util(self, temp, v, vis):
		vis[v] = True
		temp.append(v)
		for i in self.adj[v]:
			if vis[i] == False:
				temp = self.util(temp, i, vis)
		return temp
t = int(input())
while t > 0:
	t = t - 1
	(n, m) = list(map(int, input().split()))
	gr = graph(n)
	for i in range(m):
		(u, v) = list(map(int, input().split()))
		gr.addedge(u, v)
	c = gr.connected()
	print(len(c))


def dfs(s):
	if v[s] == 1:
		return
	v[s] = 1
	for k in adj[s]:
		dfs(k)
test = int(input())
for t in range(test):
	(n, m) = map(int, input().split())
	v = [0 for i in range(n)]
	adj = [[] for i in range(n)]
	for i in range(m):
		(a, b) = map(int, input().split())
		adj[a].append(b)
		adj[b].append(a)
	count = 0
	while 0 in v:
		node = v.index(0)
		dfs(node)
		count += 1
	print(count)


from collections import defaultdict

class Graph:

	def __init__(self, n):
		self.n = n
		self.edge = defaultdict(list)

	def addegde(self, u, v):
		self.edge[u].append(v)
		self.edge[v].append(u)

	def dfsUtil(self, i, visited):
		visited[i] = True
		for j in self.edge[i]:
			if visited[j] == False:
				self.dfsUtil(j, visited)

	def dfs(self):
		visited = [False] * self.n
		s = 0
		for i in range(self.n):
			if visited[i] == False:
				s += 1
				self.dfsUtil(i, visited)
		return s
for _ in range(int(input())):
	(m, n) = map(int, input().split())
	g = Graph(m)
	for i in range(n):
		(a, b) = map(int, input().split())
		g.addegde(a, b)
	print(g.dfs())


from collections import defaultdict
viz = [0] * 1005

class Graph:

	def __init__(self):
		self.graph = defaultdict(list)

	def addEdge(self, u, v):
		self.graph[u].append(v)

	def DFSUtil(self, v, visited):
		nonlocal viz
		visited[v] = True
		viz[v] = 1
		for i in self.graph[v]:
			if visited[i] == False:
				self.DFSUtil(i, visited)

	def DFS(self, v, visited):
		self.DFSUtil(v, visited)
		return visited
for _ in range(int(input())):
	g = Graph()
	(n, m) = list(map(int, input().split()))
	vizi = [False] * (n + 1)
	for i in range(m):
		(a, b) = list(map(int, input().split()))
		g.addEdge(a, b)
		g.addEdge(b, a)
	cnt = 0
	for i in range(n):
		if vizi[i] == False:
			cnt += 1
			vizi = g.DFS(i, vizi)
	print(cnt)


def dfs(u):
	visited[u] = 1
	for i in graph[u]:
		if visited[i] == 0:
			dfs(i)
for _ in range(int(input())):
	(N, M) = map(int, input().split())
	graph = [[] for i in range(N)]
	for i in range(M):
		(u, v) = map(int, input().split())
		graph[u].append(v)
		graph[v].append(u)
	ccnum = 0
	visited = [0] * N
	for pp in range(N):
		if visited[pp] == 0:
			dfs(pp)
			ccnum += 1
	print(ccnum)