Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

Chef invited N of his friends in his birthday party. All the friends are numbered from 1 to N. Some of the friends might know each other. You are given this information by M pairs each of form (a_{i}, b_{i}), denoting that the persons a_{i} and b_{i} know each other.

Chef wants all of his guests to seat at the two tables set up for dinner. He wants that all the people  sitting at a table must know each other, otherwise they will feel awkward with mutual eating habits. Chef is okay if a table is not occupied by any person. Chef is worried whether all the guests can seat at the dinner tables in the desired way.

Please help Chef fast to identify whether his worry is real or not!! The delicacies at the table are getting cold.

------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two space-separated integers N and M, denoting the number of Chef's friends and the number of pairs representing information whether two person know each other or not.
The next M lines contain two space-separated integers a_{i} and b_{i}, denoting that persons a_{i} and b_{i} know each other.

------ Output ------ 

For each test case, output a single line containing word "YES" (without quotes) if Chef can divide all of his friends into two groups that in each group all the people know each other and "NO" (without quotes) otherwise.

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

$1 ≤ T ≤ 10^{3}$
$1 ≤ N ≤ 10^{3}$
$0 ≤ M ≤ 10^{6}$
$1 ≤ a_{i}, b_{i} ≤ N$
$The sum of N over all test cases in a single test file does not exceed 10^{4}$
$The sum of M over all test cases in a single test file does not exceed 10^{6}$

------ Subtasks ------ 

Subtask #1 (30 pts)
$1 ≤ N ≤ 10$
Subtask #2 (70 pts)
$Original constraints$

----- Sample Input 1 ------ 
3
3 2
1 2
2 3
4 3
1 2
2 3
2 4
6 7
1 2
1 3
2 3
2 4
4 5
4 6
5 6
----- Sample Output 1 ------ 
YES
NO
YES
----- explanation 1 ------ 
Example case 1.
Table 1: Person 1. Table 2: Persons 2 and 3.
Example case 2.
All guests can't have a seat according to the rule.
Example case 3.
Table 1: Persons 1, 2, 3. Table 2: Persons 4, 5, 6.

Difficulty: MEDIUM_HARD
Tags: Data structures

Graph algorithms

Graph traversal
Skill types: Data structures

Starter code:

Solutions:
import collections
import sys

def BFSS(graph, sv, n, col):
	q = collections.deque([sv])
	col[sv] = 1
	while q:
		v = q.popleft()
		for u in range(n):
			if col[u] == -1 and graph[u][v]:
				q.append(u)
				col[u] = 1 - col[v]
			elif graph[u][v] and col[v] == col[u]:
				return False
	return True

def BFS(graph, n):
	col = [-1] * n
	for i in range(n):
		if col[i] == -1:
			ans = BFSS(graph, i, n, col)
			if ans == False:
				print('NO')
				return
	print('YES')
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	graph = [[0 for i in range(n)] for i in range(n)]
	for i in range(m):
		(x, y) = map(int, sys.stdin.readline().split())
		graph[x - 1][y - 1] = 1
		graph[y - 1][x - 1] = 1
	for i in range(n):
		graph[i][i] = 0
		for j in range(i + 1, n):
			graph[i][j] = 1 - graph[i][j]
			graph[j][i] = 1 - graph[j][i]
	BFS(graph, n)


from collections import defaultdict
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	d = defaultdict(list)
	mat = [[0 for i in range(n)] for i in range(n)]
	for i in range(m):
		(x, y) = map(int, input().split())
		x = x - 1
		y = y - 1
		mat[x][y] = 1
		mat[y][x] = 1
	for i in range(n):
		for j in range(i + 1, n):
			mat[i][j] = 1 - mat[i][j]
			mat[j][i] = 1 - mat[j][i]
	for i in range(n):
		mat[i][i] = 0

	def isok():
		col = [-1] * n
		for i in range(n):
			if col[i] == -1:
				src = i
				q = [src]
				col[src] = 1
				while q:
					t = q.pop(0)
					for i in range(n):
						if mat[t][i] and col[i] == -1:
							q.append(i)
							col[i] = 1 - col[t]
						elif mat[t][i] and col[t] == col[i]:
							return False
		return True
	print('YES' if isok() else 'NO')


def is2colorable(n, graph):
	col = [-1 for i in range(n)]
	for v in range(n):
		if col[v] == -1:
			tmp = []
			tmp.append(v)
			col[v] = 1
			while len(tmp) > 0:
				ind = tmp.pop()
				for i in range(n):
					if graph[ind][i] == 1 and col[i] == -1:
						col[i] = 1 - col[ind]
						tmp.append(i)
					elif graph[ind][i] == 1 and col[ind] == col[i]:
						return False
	return True
for t in range(int(input())):
	(n, m) = list(map(int, input().split()))
	graph = [[1 for i in range(n)] for j in range(n)]
	for i in range(n):
		graph[i][i] = 0
	while m > 0:
		(a, b) = list(map(int, input().split()))
		graph[a - 1][b - 1] = 0
		graph[b - 1][a - 1] = 0
		m -= 1
	if is2colorable(n, graph):
		print('YES')
	else:
		print('NO')


from collections import deque

def find(graph):
	n = len(graph)
	A = [0] * n
	Col = [0 for i in range(n)]
	parent = [-1] * n
	Q = [0] * n
	for i in range(len(graph)):
		if A[i] == 0:
			Col[i] = 0
			q = deque([i])
			while q:
				v = q.popleft()
				Q[v] = 0
				A[v] = 1
				for adj in graph[v]:
					if adj != parent[v]:
						if A[adj] == 0:
							if Q[adj] == 0:
								q += [adj]
								Q[adj] = 1
								parent[adj] = v
								if Col[v] == 0:
									Col[adj] = 1
								else:
									Col[adj] = 0
							elif Col[adj] == Col[v]:
								return 0
	return 1

def build(graph):
	n = len(graph)
	GG = [[] for i in range(n)]
	for i in range(n):
		A = [0 for jjj in range(n)]
		for k in graph[i]:
			A[k] = 1
		for j in range(len(A)):
			if A[j] == 0:
				GG[i] += [j]
	return GG
for _ in range(int(input())):
	(n, m) = list(map(int, input().strip().split(' ')))
	g = [[] for i in range(n)]
	for _ in range(m):
		(a, b) = list(map(int, input().strip().split(' ')))
		a -= 1
		b -= 1
		g[a] += [b]
		g[b] += [a]
	if find(build(g)) == 1:
		print('YES')
	else:
		print('NO')


from collections import defaultdict
T = int(input())

def func(p, graph, visited, color):
	visited[p] = True
	ans = True
	for i in graph[p]:
		if visited[i] and color[i] == color[p]:
			return False
		color[i] = not color[p]
		if visited[i] is not True:
			ans = ans and func(i, graph, visited, color)
	return ans
for i in range(T):
	graph = defaultdict(list)
	(n, m) = map(int, input().split())
	for j in range(m):
		(x, y) = map(int, input().split())
		graph[x].append(y)
		graph[y].append(x)
	inv_graph = {}
	uni_set = set(range(1, n + 1))
	for j in range(1, n + 1):
		inv_graph[j] = list(uni_set - set(graph[j] + [j]))
	visited = [False for i in range(n + 1)]
	color = [False for i in range(n + 1)]
	ans = True
	for j in range(1, n + 1):
		ans = ans and func(j, inv_graph, visited, color)
	if ans:
		print('YES')
	else:
		print('NO')


def dfs():
	q = list()
	col = [-1 for x1 in range(n)]
	col[0] = 0
	q.append(0)
	visited = [False for x in range(n)]
	while True:
		while len(q) != 0:
			pr_node = q.pop(0)
			visited[pr_node] = True
			for i in range(n):
				if a[pr_node][i] == 1:
					if col[i] == -1:
						q.append(i)
						col[i] = 1 - col[pr_node]
					elif col[i] == col[pr_node]:
						return False
		k = all_visited(visited)
		if k == -1:
			return True
		q.append(k)

def all_visited(v):
	for i in range(n):
		if not v[i]:
			return i
	return -1
for i in range(int(input())):
	(n, m) = map(int, input().split())
	a = [[1 for x in range(n)] for y in range(n)]
	for j in range(n):
		a[j][j] = 0
	for j in range(m):
		(m1, m2) = map(int, input().split())
		a[m1 - 1][m2 - 1] = 0
		a[m2 - 1][m1 - 1] = 0
	if dfs():
		print('YES')
	else:
		print('NO')


def check(A, B, confused, isconn):
	if len(confused) == 0:
		return 1
	q = [i for i in confused]
	posed = {}
	while len(q) != 0:
		curr = q[0]
		if posed.get(curr, -1) == len(q):
			break
		chkA = 1
		chkB = 1
		for i in A:
			if isconn.get((curr, i), -1) == -1 and isconn.get((i, curr), -1) == -1:
				chkA = -1
				break
		for i in B:
			if isconn.get((curr, i), -1) == -1 and isconn.get((i, curr), -1) == -1:
				chkB = -1
				break
		if chkA == 1 and chkB == 1:
			q.append(q.pop(0))
			posed[curr] = len(q)
		elif chkA == -1 and chkB != -1:
			B.append(curr)
			q.pop(0)
		elif chkA != -1 and chkB == -1:
			A.append(curr)
			q.pop(0)
		elif chkA == -1 and chkB == -1:
			return -1
	if len(q) == 0:
		return 1
	elif len(q) == 1:
		A.append(q[0])
		return 1
	while len(q) != 0:
		xA = []
		xB = []
		init_confused(q, xA, xB)
		if len(xA) == 0 and len(xB) == 0:
			for i in q:
				A.append(i)
			return 1
		captainA = xA[0]
		captainB = xB[0]
		dick = {}
		for i in q:
			dick[i] = 1
		adjA = []
		adjB = []
		for i in d[captainA]:
			if dick.get(i, -1) != -1:
				adjA.append(i)
		for i in d[captainB]:
			if dick.get(i, -1) != -1:
				adjB.append(i)
		for i in adjA:
			if isconn.get((i, captainB), -1) == -1 and isconn.get((captainB, i), -1) == -1:
				xA.append(i)
				q.remove(i)
		for i in adjB:
			if isconn.get((i, captainA), -1) == -1 and isconn.get((captainA, i), -1) == -1:
				xB.append(i)
				q.remove(i)
		if finalcheck(xA) == -1 or finalcheck(xB) == -1:
			return -1
		posed = {}
		while len(q) != 0:
			curr = q[0]
			if posed.get(curr, -1) == len(q):
				break
			chkA = 1
			chkB = 1
			for i in xA:
				if isconn.get((curr, i), -1) == -1 and isconn.get((i, curr), -1) == -1:
					chkA = -1
					break
			for i in xB:
				if isconn.get((curr, i), -1) == -1 and isconn.get((i, curr), -1) == -1:
					chkB = -1
					break
			if chkA == 1 and chkB == 1:
				q.append(q.pop(0))
				posed[curr] = len(q)
			elif chkA == -1 and chkB != -1:
				xB.append(curr)
				q.pop(0)
			elif chkA != -1 and chkB == -1:
				xA.append(curr)
				q.pop(0)
			elif chkA == -1 and chkB == -1:
				return -1
		if len(q) == 1:
			xA.append(q[0])
			q.pop(0)
		if len(q) == 2:
			xA.append(q[0])
			xB.append(q[1])
			q.pop(0)
			q.pop(1)
		for i in xA:
			A.append(i)
		for i in xB:
			B.append(i)
	return 1

def init_confused(q, xA, xB):
	for i in q:
		for j in q:
			if i != j and isconn.get((i, j), -1) == -1 and (isconn.get((j, i), -1) == -1):
				xA.append(i)
				xB.append(j)
				q.remove(i)
				q.remove(j)
				return

def init(d, dkeys, A, B, n):
	for i in range(1, n + 1):
		for j in range(len(dkeys)):
			if i != dkeys[j] and isconn.get((dkeys[j], i), -1) == -1 and (isconn.get((i, dkeys[j]), -1) == -1):
				A.append(dkeys[j])
				B.append(i)
				return

def finalcheck(A):
	for i in A:
		for j in A:
			if i != j:
				if isconn.get((j, i), -1) == -1 and isconn.get((i, j), -1) == -1:
					return -1
	return 1
for _ in range(int(input())):
	(n, m) = [int(i) for i in input().split()]
	d = {}
	degree = {}
	isconn = {}
	if n > 2 and m == 0:
		print('NO')
		continue
	elif m == 0:
		print('YES')
		continue
	for __ in range(m):
		(a, b) = [int(i) for i in input().split()]
		if a == b:
			continue
		if d.get(a, -1) == -1:
			d[a] = [b]
			isconn[a, b] = 1
		elif isconn.get((a, b), -1) == -1 and isconn.get((b, a), -1) == -1:
			d[a].append(b)
			isconn[a, b] = 1
		if d.get(b, -1) == -1:
			d[b] = [a]
		elif isconn.get((a, b), -1) == -1 and isconn.get((b, a), -1) == -1:
			d[b].append(a)
	if n == 1 or n == 2:
		print('YES')
		continue
	for u in range(1, n + 1):
		if d.get(u, -1) == -1:
			d[u] = []
	dkeys = [i for i in d.keys()]
	for i in range(1, n + 1):
		degree[i] = len(set(d[i]))
	A = []
	B = []
	init(d, dkeys, A, B, n)
	if len(A) == 0 and len(B) == 0:
		print('YES')
		continue
	captA = A[0]
	captB = B[0]
	tempA = d[captA]
	tempB = d[captB]
	placed = {}
	placed[captB] = 1
	placed[captA] = 1
	for i in d[captA]:
		if isconn.get((i, captB), -1) == -1 and isconn.get((captB, i), -1) == -1:
			A.append(i)
			placed[i] = 1
	for i in d[captB]:
		if isconn.get((i, captA), -1) == -1 and isconn.get((captA, i), -1) == -1:
			B.append(i)
			placed[i] = 1
	confused = []
	for i in range(1, n + 1):
		if placed.get(i, -1) == -1:
			confused.append(i)
	xxx = check(A, B, confused, isconn)
	if xxx == -1:
		print('NO')
		continue
	ans = 1
	ans = finalcheck(A)
	if ans == -1:
		print('NO')
		continue
	ans = finalcheck(B)
	if ans == -1:
		print('NO')
	else:
		print('YES')


from collections import deque

def check(A, _N):
	flag = [-1] * _N
	flag[0] = 1
	dq = deque([])
	dq.appendleft(0)
	prev = 0
	while len(dq) != 0:
		u = dq.pop()
		for v in range(_N):
			if A[u][v] == 1 and flag[v] == -1:
				flag[v] = 1 - flag[u]
				dq.appendleft(v)
			elif A[u][v] == 1 and flag[v] == flag[u]:
				return False
		if len(dq) == 0:
			for v in range(1 + prev, _N):
				if flag[v] == -1:
					prev = v
					flag[v] = 1
					dq.appendleft(v)
					break
	return True
_T = int(input())
for _t in range(_T):
	(_N, _M) = list(map(int, input().strip().split()))
	A = [[1 if i != j else 0 for i in range(_N)] for j in range(_N)]
	for _m in range(_M):
		(a, b) = list(map(int, input().strip().split()))
		a -= 1
		b -= 1
		(A[a][b], A[b][a]) = (0, 0)
	flag = check(A, _N)
	if flag:
		print('YES')
	else:
		print('NO')


from time import time

class Queue(object):

	def __init__(self, capacity):
		(self.front, self.rear, self.size) = (0, -1, 0)
		self.capacity = capacity
		self.array = [0] * capacity

	def isEmptyQueue(self):
		return self.size == 0

	def isFullQueue(self):
		return self.size == self.capacity

	def enqueue(self, value):
		if self.isFullQueue():
			return
		self.rear = (self.rear + 1) % self.capacity
		self.array[self.rear] = value
		self.size += 1

	def dequeue(self):
		if self.isEmptyQueue():
			return None
		item = self.array[self.front]
		self.front = (self.front + 1) % self.capacity
		self.size -= 1
		return item

	def getFront(self):
		return self.front

	def getRear(self):
		return self.rear

class graph(object):

	def __init__(self, V):
		self.adj = {}
		if V != []:
			for vertex in V:
				self.adj[vertex] = []
		self.V = V

	def addEdge(self, u, v):
		if self.adj.get(u, False):
			self.adj[u].append(v)
		else:
			self.adj[u] = [v]

def isBipartite(G, s, n):
	color[s] = 0
	Q = Queue(n)
	Q.enqueue(s)
	while not Q.isEmptyQueue():
		u = Q.dequeue()
		if G.adj.get(u, 0) == 0:
			continue
		for v in G.adj[u]:
			if color[v] == -1:
				color[v] = 1 - color[u]
				Q.enqueue(v)
			elif color[u] == color[v]:
				return False
	return True

def addEdges(G, ed, n):
	for i in range(1, n + 1):
		for j in range(i, n + 1):
			if i != j and ed.get((i, j), 0) == 0:
				G.addEdge(i, j)
				G.addEdge(j, i)

def BFS(G, s, n):
	visited[s] = True
	Q = Queue(n)
	Q.enqueue(s)
	while not Q.isEmptyQueue():
		u = Q.dequeue()
		if G.adj.get(u, 0) == 0:
			continue
		for v in G.adj[u]:
			if not visited[v]:
				visited[v] = True
				Q.enqueue(v)
from sys import stdin
t = int(stdin.readline())
start = time()
while t > 0:
	(n, m) = list(map(int, stdin.readline().split()))
	if time() - start > 3.65:
		for i in range(m):
			s = stdin.readline()
		print('NO')
		t -= 1
		continue
	ed = {}
	G = graph([])
	for i in range(m):
		(a, b) = list(map(int, stdin.readline().split()))
		G.addEdge(a, b)
		G.addEdge(b, a)
		ed[a, b] = 1
		ed[b, a] = 1
	visited = [False] * (n + 1)
	components = 0
	for i in range(1, n + 1):
		if not visited[i]:
			BFS(G, i, n)
			components += 1
	if components > 2:
		print('NO')
		t -= 1
		continue
	G = graph([])
	addEdges(G, ed, n)
	res = True
	color = [-1] * (n + 1)
	for i in range(1, n + 1):
		if color[i] == -1:
			res = res and isBipartite(G, i, n)
	if res:
		print('YES')
	else:
		print('NO')
	t -= 1


import queue
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	adj = []
	for i in range(n):
		adj.append(set(range(n)))
		adj[i].discard(i)
	for i in range(m):
		(u, v) = map(int, input().split())
		u = u - 1
		v = v - 1
		adj[u].discard(v)
		adj[v].discard(u)
	color = [0] * n
	flag = 1
	for v in range(n):
		if color[v] == 0:
			q = queue.Queue()
			color[v] = 1
			q.put(v)
			while q.empty() != True:
				u = q.get()
				for w in adj[u]:
					if color[w] == 0:
						if color[u] == 1:
							color[w] = 2
						else:
							color[w] = 1
						q.put(w)
					elif color[u] == color[w]:
						flag = 0
						break
				if flag == 0:
					break
		if flag == 0:
			break
	if flag == 1:
		print('YES')
	else:
		print('NO')


from collections import deque
t = int(input())
for idx in range(t):
	[n, m] = [int(a) for a in input().split(' ')]
	nodes = range(n)
	edge = [[False for u in range(n)] for v in range(n)]
	for edg in range(m):
		[u, v] = [int(a) for a in input().split(' ')]
		edge[u - 1][v - 1] = True
	color = [0 for u in range(n)]
	result = True
	for start in range(n):
		if result == False:
			break
		if color[start] != 0:
			continue
		queue = deque([start])
		color[start] = 1
		while len(queue) != 0:
			u = queue.popleft()
			c = color[u]
			next_color = 1 if c == 2 else 2
			for v in range(n):
				if u == v or edge[u][v] or edge[v][u]:
					continue
				if color[v] == 0:
					color[v] = next_color
					queue.append(v)
				elif color[v] == color[u]:
					result = False
					break
	if result:
		print('YES')
	else:
		print('NO')


from queue import *
N = 10 ** 3
Adj = [[1] * (N + 1) for i in range(0, N + 1)]
t = int(input())
ColArr = [-1] * (N + 1)

def Biparatite(s):
	ColArr[s] = 1
	q = Queue()
	q.put(s)
	while q.empty() is not True:
		u = q.get()
		for v in range(1, n + 1):
			if Adj[u][v] == 1 and ColArr[v] == -1:
				q.put(v)
				ColArr[v] = 1 - ColArr[u]
			elif Adj[u][v] == 1 and ColArr[v] == ColArr[u]:
				return False
	return True
while t:
	t = t - 1
	(n, m) = map(int, input().split())
	li = []
	for i in range(m):
		li.append(tuple(map(int, input().split())))
	for i in range(0, len(li)):
		Adj[li[i][0]][li[i][1]] = 0
		Adj[li[i][1]][li[i][0]] = 0
	for i in range(1, n + 1):
		Adj[i][i] = 0
	ok = True
	for i in range(1, n + 1):
		if ColArr[i] == -1:
			ok = ok and Biparatite(i)
	if ok == True:
		print('YES')
	else:
		print('NO')
	for i in range(0, len(li)):
		Adj[li[i][0]][li[i][1]] = 1
		Adj[li[i][1]][li[i][0]] = 1
	for i in range(1, n + 1):
		ColArr[i] = -1


from collections import deque

def fun(x, col):
	if len(graph[x]) == 0:
		return True
	Q = deque([(x, col)])
	color[x] = col
	while Q:
		(x, col) = Q.popleft()
		for i in graph[x]:
			if color[i] == -1:
				color[i] = col ^ 1
				Q.append((i, col ^ 1))
			elif color[i] == col:
				return False
	return True
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	graph = {i: set(range(1, n + 1)) for i in range(1, n + 1)}
	for i in range(1, n + 1):
		graph[i].remove(i)
	for _ in range(m):
		(a, b) = map(int, input().split())
		if b in graph[a]:
			graph[a].remove(b)
		if a in graph[b]:
			graph[b].remove(a)
	color = [-1] * (n + 1)
	for i in range(1, n + 1):
		if color[i] == -1:
			if fun(i, 1):
				continue
			else:
				print('NO')
				break
	else:
		print('YES')


import random
for t in range(int(input())):
	(n, m) = list(map(int, input().split()))
	adj = {i: set() for i in range(1, n + 1)}
	for i in range(m):
		(a, b) = list(map(int, input().split()))
		adj[a].add(b)
		adj[b].add(a)
	mv = 0
	ind = -1
	for i in range(1, n + 1):
		if len(adj[i]) > mv:
			mv = len(adj[i])
			ind = i
	possible = True
	s1 = set()
	s2 = set()
	doubt = set()
	s1.add(ind)
	if ind == -1:
		possible = n < 3
	else:
		for i in range(1, n + 1):
			if i != ind:
				if i in adj[ind]:
					doubt.add(i)
				else:
					s2.add(i)
		try:
			l = list(s2)
			for i in range(len(l)):
				for j in range(i + 1, len(l)):
					if l[j] not in adj[l[i]]:
						possible = False
						break
				if not possible:
					break
			if possible:
				while doubt and len(s1) + len(s2) < n:
					doubt2 = set()
					changed = False
					for d in doubt:
						if len(adj[d]) > 0.99 * n:
							ind = random.randint(1, n - 1)
							if ind in s1:
								s1.add(d)
							elif ind in s2:
								s2.add(d)
							else:
								s1.add(d)
							continue
						for b in s1:
							if b not in adj[d]:
								for c in s2:
									if c not in adj[d]:
										possible = False
										break
								else:
									s2.add(d)
								break
						else:
							for c in s2:
								if c not in adj[d]:
									s1.add(d)
									break
							else:
								doubt2.add(d)
						if not possible:
							break
					if len(doubt2) and len(doubt) == len(doubt2):
						l = list(doubt2)
						random.shuffle(l)
						v = l[len(l) // 2]
						doubt2.remove(v)
						if len(s1) < len(s2):
							s1.add(v)
						else:
							s2.add(v)
					doubt = doubt2
		except Exception as e:
			possible = False
	if possible:
		print('YES')
	else:
		print('NO')


import sys
import numpy as np

def solve(n, ee):
	g = np.ones((n, n), dtype=np.int64)
	for i in range(n):
		g[i, i] = 0
	for (a, b) in ee:
		g[a, b] = 0
		g[b, a] = 0
	ret = np.zeros(n, dtype=np.int64)
	v = set(range(n))
	q = []
	while v:
		x = next(iter(v))
		v.remove(x)
		q = [x]
		ret[x] = 1
		while q:
			x = q[0]
			q = q[1:]
			cc = ret[x]
			for y in np.where(g[x, :] == 1)[0]:
				if ret[y] == cc:
					return 'NO'
				elif ret[y] == 0:
					ret[y] = 3 - cc
					q += [y]
					v.remove(y)
	return 'YES'
f = sys.stdin
t = int(f.readline())
for j in range(t):
	(n, m) = map(int, f.readline().split())
	ee = []
	for i in range(m):
		(x, y) = map(int, f.readline().split())
		ee += [(x - 1, y - 1)]
	print(solve(n, ee))