Chef has decided to start home delivery from his restaurant. He hopes that he will get a lot of orders for delivery, however there is a concern. He doesn't have enough work forces for all the deliveries.  For this he has came up with an idea - he will group together all those orders which have to be delivered in nearby areas. 

In particular, he has identified certain bidirectional roads which he calls as fast roads. They are short and usually traffic free, so the fast travel is possible along these roads. His plan is that he will send orders to locations A and B together if and only if it is possible to travel between A and B using only fast roads. Your task is, given the configuration of fast roads, identify which orders are to be sent together.

-----Input-----
First line of input contains an integer T, the number of test cases. Then T test cases follow. First line of each test case contains two space separated integers N and M, denoting number of locations and the number of fast roads. Then M lines follow each containing two space separated integers A and B, denoting that there is a fast road between locations A and B. Assume that locations are indexed by numbers from 0 to N-1. 

Next line contains an integer Q denoting the number of queries. Each of the next Q lines contain two integers X and Y. For each query you have to find out if orders meant for locations X and Y are to be sent together or not.

Note that there might be multiple fast roads between same pair of locations, also there might be a fast road that links a location to itself.

-----Output-----
For each test case print Q lines - one for each query. Output "YO" if the orders are to be 
delivered together and "NO" otherwise (quotes for clarity).

-----Constraints-----
1 ≤ T ≤ 100
1 ≤ N ≤ 100
1 ≤ M ≤ 1000
0 ≤ A, B, X, Y ≤ N-1
1 ≤ Q ≤ 3000

-----Example-----
Input:
1
4 2
0 1
1 2
3
0 2
0 3
2 1

Output:
YO
NO
YO

-----Warning!-----
There are large input and output files in this problem. Make sure you use fast enough I/O methods.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Graph traversal


Solutions:
def find(parent, i):
	if parent[i] == i:
		return i
	parent[i] = find(parent, parent[i])
	return parent[i]

def union(parent, rank, x, y):
	rootx = find(parent, x)
	rooty = find(parent, y)
	if rootx != rooty:
		if rank[rootx] < rank[rooty]:
			parent[rootx] = rooty
		elif rank[rootx] > rank[rooty]:
			parent[rooty] = rootx
		else:
			parent[rooty] = rootx
			rank[rootx] += 1
t = int(input())
for test_case in range(t):
	(n, m) = map(int, input().split())
	parent = [i for i in range(n)]
	rank = [0 for i in range(n)]
	for i in range(m):
		(x, y) = map(int, input().split())
		union(parent, rank, x, y)
	q = int(input())
	for i in range(q):
		(x, y) = map(int, input().split())
		if find(parent, x) == find(parent, y):
			print('YO')
		else:
			print('NO')


from collections import deque

def DFSutil(s, adj, visited):
	visited.add(s)
	for n in adj[s]:
		if n not in visited:
			DFSutil(n, adj, visited)

def DFS(s, adj):
	visited = set()
	DFSutil(s, adj, visited)
	return visited

def cons(s, adj):
	visited = set()
	queue = deque()
	visited.add(s)
	queue.append(s)
	while len(queue) > 0:
		s = queue.popleft()
		for i in adj[s]:
			if i not in visited:
				visited.add(i)
				queue.append(i)
	return visited
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	fast = [set() for i in range(n)]
	reach = [set() for i in range(n)]
	for _ in range(m):
		(a, b) = map(int, input().split())
		fast[a].add(b)
		fast[b].add(a)
	haspath = set()
	for ii in range(n):
		if ii not in haspath:
			visit = cons(ii, fast)
			for v in visit:
				reach[v] = visit
				haspath.add(v)
	q = int(input())
	for _ in range(q):
		(x, y) = map(int, input().split())
		if x == y:
			print('YO')
		elif x in reach[y]:
			print('YO')
		else:
			print('NO')


from collections import defaultdict
try:

	def find(node, arr):
		if arr[node] < 0:
			return node
		else:
			temp = find(arr[node], arr)
			arr[node] = temp
			return temp

	def merge(la, lb, arr):
		if arr[la] <= arr[lb]:
			arr[la] = arr[la] + arr[lb]
			arr[lb] = la
		else:
			arr[lb] = arr[lb] + arr[la]
			arr[la] = lb
	for _ in range(int(input())):
		(n, m) = list(map(int, input().split()))
		arr = [-1] * n
		for _ in range(m):
			(a, b) = map(int, input().split())
			la = find(a, arr)
			lb = find(b, arr)
			if la != lb:
				merge(la, lb, arr)
		q = int(input())
		for _ in range(q):
			(a, b) = map(int, input().split())
			la = find(a, arr)
			lb = find(b, arr)
			if la != lb:
				print('NO')
			else:
				print('YO')
except:
	pass


def find(parent, i):
	if parent[i] == i:
		return i
	parent[i] = find(parent, parent[i])
	return parent[i]

def union(parent, rank, x, y):
	xroot = find(parent, x)
	yroot = find(parent, y)
	if rank[xroot] < rank[yroot]:
		parent[xroot] = yroot
	elif rank[xroot] > rank[yroot]:
		parent[yroot] = xroot
	else:
		parent[yroot] = xroot
		rank[xroot] += 1
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	parent = list(range(n))
	rank = [0] * n
	for j in range(m):
		(a, b) = map(int, input().split())
		union(parent, rank, a, b)
	q = int(input())
	for k in range(q):
		(x, y) = map(int, input().split())
		if find(parent, x) == find(parent, y):
			print('YO')
		else:
			print('NO')


def find(node, arr):
	if arr[node] < 0:
		return node
	else:
		temp = find(arr[node], arr)
		arr[node] = temp
		return temp

def union(la, lb, arr):
	if arr[la] <= arr[lb]:
		arr[la] = arr[la] + arr[lb]
		arr[lb] = la
	else:
		arr[lb] = arr[la] + arr[lb]
		arr[la] = lb
t = int(input())
while t:
	(n, m) = map(int, input().split())
	arr = [-1] * n
	for _ in range(m):
		(a, b) = map(int, input().split())
		la = find(a, arr)
		lb = find(b, arr)
		if la != lb:
			union(la, lb, arr)
	q = int(input())
	for i in range(q):
		(a, b) = map(int, input().split())
		if find(a, arr) == find(b, arr):
			print('YO')
		else:
			print('NO')
	t -= 1


def dfs(a, b, visited):
	for ele in dct[b]:
		if ele not in visited:
			root[a][ele] = 1
			root[ele][a] = 1
			visited.add(ele)
			dfs(a, ele, visited)
t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	dct = {}
	for i in range(m):
		(a, b) = list(map(int, input().split()))
		if a not in dct:
			dct[a] = {b}
		else:
			dct[a].add(b)
		if b not in dct:
			dct[b] = {a}
		else:
			dct[b].add(a)
	Q = int(input())
	root = [[0 for j in range(n)] for i in range(n)]
	for i in range(n):
		root[i][i] = 1
		if i not in dct:
			continue
		dfs(i, i, {i})
	for i in range(Q):
		(a, b) = list(map(int, input().split()))
		if root[a][b] or root[b][a]:
			print('YO')
		else:
			print('NO')


from sys import stdin, stdout
from math import ceil

def solve():
	for _ in range(int(input())):
		(n, m) = map(int, stdin.readline().split())
		par = [i for i in range(n)]
		for i in range(m):
			(ta, tb) = map(int, stdin.readline().strip().split())
			(a, b) = (min(ta, tb), max(ta, tb))
			for j in range(n):
				if par[j] == par[b] and j != b:
					par[j] = par[a]
			par[b] = par[a]
		q = int(input())
		while q:
			q -= 1
			(x, y) = map(int, stdin.readline().split())
			if par[x] == par[y]:
				print('YO')
			else:
				print('NO')

def __starting_point():
	solve()
__starting_point()


def find(u, graph):
	if graph[u] < 0:
		return u
	else:
		temp = find(graph[u], graph)
		graph[u] = temp
		return temp

def union(u, v, graph):
	u = find(u, graph)
	v = find(v, graph)
	if graph[u] <= graph[v]:
		graph[u] += graph[v]
		graph[v] = u
	else:
		graph[v] += graph[u]
		graph[u] = v
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	graph = [-1] * n
	for _ in range(m):
		(u, v) = map(int, input().split())
		if find(u, graph) != find(v, graph):
			union(u, v, graph)
	k = int(input())
	for _ in range(k):
		(u, v) = map(int, input().split())
		if find(u, graph) == find(v, graph):
			print('YO')
		else:
			print('NO')


def dfs(s, vis, d, m):
	vis[s] = mark
	for i in d[s]:
		if vis[i] == False:
			dfs(i, vis, d, m)
for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	d = dict()
	for i in range(n):
		d[i] = set()
	for i in range(m):
		(x, y) = list(map(int, input().split()))
		if x != y:
			d[x].add(y)
			d[y].add(x)
	vis = [False for i in range(n)]
	mark = 1
	for i in range(n):
		if vis[i] == False:
			dfs(i, vis, d, mark)
			mark += 1
	q = int(input())
	for _ in range(q):
		(a, b) = list(map(int, input().split()))
		if vis[a] == vis[b]:
			print('YO')
		else:
			print('NO')


t = int(input())
for i in range(0, t):
	(n, m) = map(int, input().split())
	l = [0] * n
	for j in range(0, n):
		l[j] = j
	for j in range(0, m):
		(a, b) = map(int, input().split())
		if l[a] < l[b]:
			temp = l[b]
			for p in range(0, n):
				if l[p] == temp:
					l[p] = l[a]
		elif l[b] < l[a]:
			temp = l[a]
			for p in range(0, n):
				if l[p] == temp:
					l[p] = l[b]
	q = int(input())
	for p in range(0, q):
		(x, y) = map(int, input().split())
		if l[x] == l[y]:
			print('YO')
		else:
			print('NO')


from collections import defaultdict
from queue import deque
t = int(input())
while t:
	(n, m) = map(int, input().split())
	parent = [i for i in range(n)]
	rank = [1] * n

	def find(node, parent):
		if node == parent[node]:
			return parent[node]
		return find(parent[node], parent)

	def union(u, v):
		lx = find(u, parent)
		ly = find(v, parent)
		if lx != ly:
			if rank[lx] < rank[ly]:
				parent[lx] = ly
			elif rank[lx] > rank[ly]:
				parent[ly] = lx
			else:
				parent[ly] = lx
				rank[lx] += 1
	for _ in range(m):
		(u, v) = map(int, input().split())
		union(u, v)
	x = int(input())
	for _ in range(x):
		(u, v) = map(int, input().split())
		lx = find(u, parent)
		ly = find(v, parent)
		if lx != ly:
			print('NO')
		else:
			print('YO')
	t -= 1


from collections import defaultdict

class Graph:

	def __init__(self, vertices):
		self.graph = defaultdict(list)
		self.DFSList = defaultdict(list)
		for i in range(0, vertices):
			self.graph[i] = []
			self.DFSList[i] = []

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

	def DFSUtil(self, v, visited, n):
		visited[v] = True
		self.DFSList[n].append(v)
		for i in self.graph[v]:
			if visited[i] == False:
				self.DFSUtil(i, visited, n)

	def DFS(self, v):
		visited = [False] * len(self.graph)
		self.DFSUtil(v, visited, v)
t = int(input())
for z in range(0, t):
	(n, m) = map(int, input().split())
	g = Graph(n)
	for M in range(0, m):
		(u, v) = map(int, input().split())
		g.addEdge(u, v)
	for i in range(0, n):
		g.DFS(i)
	q = int(input())
	for Q in range(0, q):
		(u, v) = map(int, input().split())
		if v in g.DFSList[u]:
			print('YO')
		else:
			print('NO')


def find(node):
	res = node
	while res != par[res]:
		par[res] = par[par[res]]
		res = par[res]
	return res

def union(n1, n2):
	(p1, p2) = (find(n1), find(n2))
	if p1 == p2:
		return 0
	if rank[p2] > rank[p1]:
		par[p1] = p2
		rank[p2] += rank[p1]
	else:
		par[p2] = p1
		rank[p1] += rank[p2]
	return 1
t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	par = [i for i in range(n)]
	rank = [1 for _ in range(n)]
	for _ in range(m):
		(a, b) = list(map(int, input().split()))
		union(a, b)
	q = int(input())
	for _ in range(q):
		(x, y) = list(map(int, input().split()))
		if find(x) == find(y):
			print('YO')
		else:
			print('NO')


def find(node, par):
	res = node
	while res != par[res]:
		par[res] = par[par[res]]
		res = par[res]
	return res

def union(a, b, par, rank):
	(p1, p2) = (find(a, par), find(b, par))
	if p1 == p2:
		return 0
	if rank[p2] > rank[p1]:
		par[p1] = p2
		rank[p2] += rank[p1]
	else:
		par[p2] = p1
		rank[p1] += rank[p2]
	return 1
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	par = [i for i in range(n)]
	rank = [1 for i in range(n)]
	for j in range(m):
		(a, b) = map(int, input().split())
		union(a, b, par, rank)
	for i in range(int(input())):
		(x, y) = map(int, input().split())
		if find(x, par) == find(y, par):
			print('YO')
		else:
			print('NO')


def find(x, arr):
	if arr[x] < 0:
		return x
	else:
		y = find(arr[x], arr)
		arr[x] = y
		return y

def merge(la, lb, arr):
	if la <= lb:
		arr[la] = arr[la] + arr[lb]
		arr[lb] = la
	else:
		arr[lb] = arr[la] + arr[lb]
		arr[la] = lb
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	arr = [-1] * a
	for i in range(b):
		(n, m) = map(int, input().split())
		la = find(n, arr)
		lb = find(m, arr)
		if la != lb:
			merge(la, lb, arr)
	for i in range(int(input())):
		(s, d) = map(int, input().split())
		la = find(s, arr)
		lb = find(d, arr)
		if la == lb:
			print('YO')
		else:
			print('NO')


def visit(u, visited, L, adj):
	if not visited[u]:
		visited[u] = True
		for v in adj[u]:
			visit(v, visited, L, adj)
		L.append(u)

def assign(u, root, who, adj):
	if who[u] is None:
		who[u] = root
		for v in adj[u]:
			assign(v, root, who, adj)
t = int(input())
for _ in range(t):
	(V, E) = [int(e) for e in input().split()]
	adj = {v: [] for v in range(V)}
	for _ in range(E):
		(u, v) = [int(e) for e in input().split()]
		adj[u].append(v)
		adj[v].append(u)
	L = []
	visited = [False for _ in range(V)]
	who = [None for _ in range(V)]
	for u in range(V):
		visit(u, visited, L, adj)
	while len(L):
		u = L.pop()
		assign(u, u, who, adj)
	q = int(input())
	for _ in range(q):
		(i, j) = [int(e) for e in input().split()]
		print('YO' if who[i] == who[j] else 'NO')


import sys
sys.setrecursionlimit(10000)

def dfs(n):
	ans = set()
	queue = [n]
	bool[n] = True
	ans.add(n)
	while queue != []:
		z = queue.pop(0)
		ans.add(z)
		for j in hash[z]:
			if bool[j] == False:
				bool[j] = True
				queue.append(j)
	return ans
from collections import defaultdict
t = int(input())
for _ in range(t):
	ans = []
	hash = defaultdict(list)
	(n, m) = map(int, sys.stdin.readline().strip().split())
	for i in range(m):
		(a, b) = map(int, sys.stdin.readline().strip().split())
		hash[a].append(b)
		hash[b].append(a)
	for i in range(n):
		bool = [False] * n
		z = dfs(i)
		hash[i] = z
	q = int(input())
	for i in range(q):
		(a, b) = map(int, sys.stdin.readline().strip().split())
		dfs(a)
		if b in hash[a]:
			z = 'YO'
			sys.stdout.write(z)
			print()
		else:
			z = 'NO'
			sys.stdout.write(z)
			print()


def find_parent(x, lst):
	if lst[x] == x:
		return x
	lst[x] = find_parent(lst[x], lst)
	return lst[x]

def merge(a, b, lst):
	x = find_parent(b, lst)
	y = find_parent(a, lst)
	lst[x] = y
t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	lst = [i for i in range(n + 1)]
	visited = set()
	for i in range(m):
		(a, b) = list(map(int, input().split()))
		if a == b:
			visited.add(a)
		merge(a, b, lst)
	q = int(input())
	for i in range(q):
		(x, y) = list(map(int, input().split()))
		(px, py) = (find_parent(x, lst), find_parent(y, lst))
		print('YO' if px == py else 'NO')


from collections import deque

def recur(ind, visited, graph):
	visited[ind] = True
	res = set()
	queue = deque([ind])
	while queue:
		cur = queue.popleft()
		visited[cur] = True
		for i in graph[cur]:
			if not visited[i]:
				queue.append(i)
		res.add(cur)
	return res
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	graph = {i: set() for i in range(n)}
	mem = {i: set() for i in range(n)}
	visited = [False] * n
	for i in range(m):
		(x, y) = map(int, input().split())
		graph[x].add(y)
		graph[y].add(x)
	for i in range(n):
		if not visited[i]:
			cur = recur(i, visited, graph)
			for j in cur:
				mem[j] = cur
	for q in range(int(input())):
		(a, b) = map(int, input().split())
		if a in mem[b] or b in mem[a]:
			print('YO')
		else:
			print('NO')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	par = [i for i in range(n)]
	size = [1] * n
	for __ in range(m):
		(x, y) = map(int, input().split())
		while x != par[x]:
			x = par[x]
		while y != par[y]:
			y = par[y]
		if size[x] > size[y]:
			par[y] = x
			size[x] += size[y]
		else:
			par[x] = y
			size[y] += size[x]
	q = int(input())
	for ___ in range(q):
		(x, y) = map(int, input().split())
		while x != par[x]:
			x = par[x]
		while y != par[y]:
			y = par[y]
		if x == y:
			print('YO')
		else:
			print('NO')