A matrix B (consisting of integers) of dimension N × N is said to be good if there exists an array A (consisting of integers) such that B[i][j]  = |A[i] - A[j]|, where |x| denotes absolute value of integer x.
You are given a partially filled matrix B of dimension N × N. Q of the entries of this matrix are filled by either 0 or 1. You have to identify whether it is possible to fill the remaining entries of matrix B (the entries can be filled by any integer, not necessarily by 0 or 1) such that the resulting fully filled matrix B is good.

-----Input-----
The first line of the input contains an integer T denoting the number of test cases. 
The first line of each test case contains two space separated integers N, Q.
Each of the next Q lines contain three space separated integers i, j, val, which means that B[i][j] is filled with value val.

-----Output-----
For each test case, output "yes" or "no" (without quotes) in a single line corresponding to the answer of the problem.

-----Constraints-----
- 1 ≤ T ≤ 106
- 2 ≤ N ≤ 105
- 1 ≤ Q ≤ 106
- 1 ≤ i, j ≤ N
- 0 ≤ val ≤ 1
- Sum of each of N, Q over all test cases doesn't exceed 106

-----Subtasks-----
- Subtask #1 (40 points) 2 ≤ N ≤ 103, 1 ≤ Q ≤ 103, Sum of each of N, Q over all test cases doesn't exceed 104
- Subtask #2 (60 points) Original Constraints

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

Output
yes
no
yes
no

-----Explanation-----
Example 1. You can fill the entries of matrix B as follows. 

0 1
1 0
This matrix corresponds to the array A = [1, 2].

Example 2. It is impossible to fill the remaining entries of matrix B such that the resulting matrix is good, as B[1][2] = 1 and B[2][1] = 0, which is impossible.

Source: codechef | Difficulty: HARD
Tags: Graph algorithms

Data structures


Solutions:
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	arr = []
	a = [-1] * (n + 1)
	b = []
	a[1] = 0
	ans = 0
	for _ in range(q):
		(x, y, z) = map(int, input().split())
		if x == y:
			if z != 0:
				ans += 1
		else:
			arr.append([min(x, y), max(x, y), z])
	arr.sort()
	for i in arr:
		if a[i[0]] != -1 and a[i[1]] != -1:
			if abs(a[i[0]] - a[i[1]]) == i[2]:
				continue
			else:
				ans += 1
				break
		elif a[i[0]] != -1 and a[i[1]] == -1:
			if i[2] == 0:
				a[i[1]] = a[i[0]]
			elif i[2] == 1:
				if a[i[0]] == 0:
					a[i[1]] = 1
				elif a[i[0]] == 1:
					a[i[1]] = 0
		elif a[i[0]] == -1 and a[i[1]] != -1:
			if i[2] == 0:
				a[i[0]] = a[i[1]]
			elif i[2] == 1:
				if a[i[1]] == 0:
					a[i[1]] = 0
				elif a[i[1]] == 1:
					a[i[1]] = 1
		else:
			b.append(i)
	if ans == 0:
		for i in b:
			if a[i[0]] != -1 and a[i[1]] != -1:
				if abs(a[i[0]] - a[i[1]]) == i[2]:
					continue
				else:
					ans += 1
					break
			elif a[i[0]] != -1 and a[i[1]] == -1:
				if i[2] == 0:
					a[i[1]] = a[i[0]]
				elif i[2] == 1:
					if a[i[0]] == 0:
						a[i[1]] = 1
					elif a[i[0]] == 1:
						a[i[1]] = 0
			elif a[i[0]] == -1 and a[i[1]] != -1:
				if i[2] == 0:
					a[i[0]] = a[i[1]]
				elif i[2] == 1:
					if a[i[1]] == 0:
						a[i[1]] = 0
					elif a[i[1]] == 1:
						a[i[1]] = 1
			elif i[2] == 0:
				a[i[0]] = 0
				a[i[1]] = 0
			elif i[2] == 1:
				a[i[1]] = 0
				a[i[1]] = 1
	if ans == 0:
		print('yes')
	else:
		print('no')


import sys
sys.setrecursionlimit(1000000)
t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	par = [i for i in range(2 * n)]

	def get(u):
		if u != par[u]:
			par[u] = get(par[u])
		return par[u]

	def union(u, v):
		par[get(u)] = get(v)
	for i in range(q):
		(i, j, val) = map(int, input().split())
		i -= 1
		j -= 1
		if val == 0:
			union(i, j)
			union(i + n, j + n)
		else:
			union(i, j + n)
			union(i + n, j)
	if any((get(i) == get(i + n) for i in range(n))):
		print('no')
	else:
		print('yes')


from collections import defaultdict
for _ in range(int(input())):
	(N, Q) = map(int, input().split(' '))
	colorArr = [-1 for x in range(N + 1)]
	Queries = []
	ans = 1
	for i in range(Q):
		(x, y, val) = map(int, input().split(' '))
		Queries.append(tuple([x, y, val]))
		Queries.append(tuple([y, x, val]))
	Queries.sort()
	for (x, y, val) in Queries:
		if x == y and val == 1:
			ans = 0
			break
		elif x != y:
			if colorArr[x] != -1 and colorArr[y] != -1:
				if int(abs(colorArr[x] - colorArr[y])) != val:
					ans = 0
					break
			elif colorArr[x] != -1:
				if val == 1:
					colorArr[y] = 1 - colorArr[x]
				else:
					colorArr[y] = colorArr[x]
			elif colorArr[y] != -1:
				if val == 1:
					colorArr[x] = 1 - colorArr[y]
				else:
					colorArr[x] = colorArr[y]
			elif val == 0:
				colorArr[x] = 0
				colorArr[y] = 0
			else:
				colorArr[x] = 0
				colorArr[y] = 1
	if ans == 0:
		print('no')
	else:
		print('yes')


def make_aid_map(N, zeroes):
	aid_map = dict()
	aid_size = 0
	adj_list = [list() for _ in range(N)]
	for (i, j) in zeroes:
		adj_list[i].append(j)
		adj_list[j].append(i)
	visited = set()
	for i in range(N):
		if i in visited:
			continue
		visited.add(i)
		aid_map[i] = aid_size
		S = [i]
		while S:
			cur = S.pop()
			for adj in adj_list[cur]:
				if adj in visited:
					continue
				visited.add(adj)
				aid_map[adj] = aid_size
				S.append(adj)
		aid_size += 1
	return (aid_size, aid_map)

def available(N, zeroes, ones):
	(aid_size, aid_map) = make_aid_map(N, zeroes)
	adj_aid_list = [list() for _ in range(aid_size)]
	for (i, j) in ones:
		(ai, aj) = (aid_map[i], aid_map[j])
		if ai == aj:
			return False
		adj_aid_list[ai].append(aj)
		adj_aid_list[aj].append(ai)
	color = dict()
	for i in range(aid_size):
		if i in color:
			continue
		color[i] = 0
		S = [i]
		while S:
			cur = S.pop()
			for adj in adj_aid_list[cur]:
				if adj in color:
					if color[adj] == color[cur]:
						return False
				else:
					color[adj] = 1 - color[cur]
					S.append(adj)
	return True
T = int(input())
for _ in range(T):
	(N, Q) = map(int, input().split())
	QO = list()
	QI = list()
	for _ in range(Q):
		(i, j, val) = map(int, input().split())
		i -= 1
		j -= 1
		if val == 0:
			QO.append((i, j))
		else:
			QI.append((i, j))
	print('yes' if available(N, QO, QI) else 'no')


class Graph:

	def __init__(self):
		self.edge_zero = {}
		self.edge_one = {}
		self.equiv_rep = {}
		self.invalid = False

	def add_edge(self, i, j, val):
		if i == j:
			if val == 1:
				self.invalid = True
			return
		if val == 1 and i in self.edge_zero and (j in self.edge_zero[i]):
			self.invalid = True
			return
		if val == 0 and i in self.edge_one and (j in self.edge_one[i]):
			self.invalid = True
			return
		table = self.edge_zero if val == 0 else self.edge_one
		if i not in table:
			table[i] = set()
		if j not in table:
			table[j] = set()
		table[i].add(j)
		table[j].add(i)

	def is_equal(self, i, j):
		if i in self.edge_zero and j in self.edge_zero:
			return self.equiv_rep[i] == self.equiv_rep[j]
		return False

	def check_valid(self):
		if self.invalid:
			return False
		colour = {}
		for i in set(self.edge_one.keys()).union(self.edge_zero.keys()):
			if i in colour:
				continue
			colour[i] = 0
			q = [i]
			closed = set()
			while q:
				current = q.pop()
				if current in closed:
					continue
				closed.add(current)
				if current in self.edge_one:
					for nbr in self.edge_one[current]:
						if nbr not in colour:
							colour[nbr] = 1 - colour[current]
						elif colour[nbr] == colour[current]:
							return False
						q.append(nbr)
				if current in self.edge_zero:
					for nbr in self.edge_zero[current]:
						if nbr not in colour:
							colour[nbr] = colour[current]
						elif colour[nbr] != colour[current]:
							return False
						q.append(nbr)
		return True
T = int(input())
for _ in range(T):
	(N, Q) = (int(x) for x in input().split())
	graph = Graph()
	for q in range(Q):
		(i, j, val) = (int(x) for x in input().split())
		graph.add_edge(i, j, val)
	if graph.check_valid():
		print('yes')
	else:
		print('no')


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	arr = [None for i in range(n)]
	brr = []
	for i in range(q):
		(x, y, val) = map(int, input().split())
		x -= 1
		y -= 1
		brr.append((x, y, val))
	brr.sort()
	f = 0
	for i in range(len(brr)):
		(x, y, val) = brr[i]
		if arr[x] == None and arr[y] == None:
			arr[x] = 0
			arr[y] = val
		elif arr[x] == None and arr[y] != None:
			if arr[y] == 1:
				arr[x] = (1 + val) % 2
			else:
				arr[y] = (0 + val) % 2
		elif arr[x] != None and arr[y] == None:
			if arr[x] == 0:
				arr[y] = val
			else:
				arr[y] = (1 + val) % 2
		if abs(arr[x] - arr[y]) != val:
			f = 1
			break
	if f == 0:
		print('yes')
	else:
		print('no')


g = int(input())
while g > 0:
	(n, q) = map(int, input().split())
	a = [-1]
	b = [((-1, -1), -1)]
	flag = 0
	for i in range(n):
		a.append(-1)
	for i in range(q):
		(x, y, z) = map(int, input().split())
		b.append(((x, y), z))

	def invert(x):
		if x == 1:
			return 0
		else:
			return 1
	b = sorted(b, key=lambda x: x[0])
	for i in range(1, q + 1):
		if b[i][0][0] == b[i][0][1] and b[i][1] != 0:
			flag = 1
			break
		elif b[i][0][0] == b[i][0][1]:
			pass
		elif a[b[i][0][0]] == -1 and a[b[i][0][1]] == -1:
			if b[i][1] != 0:
				a[b[i][0][0]] = 0
				a[b[i][0][1]] = 1
			else:
				a[b[i][0][0]] = 0
				a[b[i][0][1]] = 0
		elif a[b[i][0][0]] == -1 and a[b[i][0][1]] != -1:
			if b[i][1] != 0:
				a[b[i][0][0]] = invert(a[b[i][0][1]])
			else:
				a[b[i][0][0]] = a[b[i][0][1]]
		elif a[b[i][0][0]] != -1 and a[b[i][0][1]] == -1:
			if b[i][1] != 0:
				a[b[i][0][1]] = invert(a[b[i][0][0]])
			else:
				a[b[i][0][1]] = a[b[i][0][0]]
		elif a[b[i][0][0]] != -1 and a[b[i][0][1]] != -1:
			if abs(a[b[i][0][0]] - a[b[i][0][1]]) != b[i][1]:
				flag = 1
				break
	if flag:
		print('no')
	else:
		print('yes')
	g -= 1


t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	array = [-1 for i in range(n)]
	commands = []
	yes = True
	for i in range(q):
		(row, col, val) = map(int, input().split())
		commands.append((row, col, val))
	commands.sort()
	for i in commands:
		row = i[0]
		col = i[1]
		val = i[2]
		if row == col and val == 1:
			yes = False
		if array[row - 1] == -1 and array[col - 1] == -1:
			array[row - 1] = 0
			array[col - 1] = val
		elif array[row - 1] == -1:
			array[row - 1] = abs(array[col - 1] - val)
		elif array[col - 1] == -1:
			array[col - 1] = abs(array[row - 1] - val)
		elif abs(array[row - 1] - array[col - 1]) != val:
			yes = False
	if yes:
		print('yes')
	else:
		print('no')


def find(parent, i, distance):
	root = i
	while parent[root] != root:
		root = parent[root]
		distance[i] += distance[root]
	return root

def find2(parent, i, distance):
	root = i
	while parent[root] != root:
		root = parent[root]
	return root

def update(parent, des, distance, dis, new_parent):
	root = des
	while parent[root] != new_parent:
		root = parent[root]
		temp = distance[root]
		distance[root] = dis + distance[des]
		dis = temp
		des = root

def union(parent, size, x, y, cycle, distance, parent1, parent2):
	parent_x = parent1
	parent_y = parent2
	if parent_x != parent_y:
		if cycle[parent_x] == 1:
			size[parent_x] += size[parent_y]
			parent[parent_y] = parent_x
		elif cycle[parent_y] == 1:
			size[parent_y] += size[parent_x]
			parent[parent_x] = parent_y
		elif size[parent_x] < size[parent_y]:
			size[parent_y] += size[parent_x]
			parent[parent_x] = parent_y
		else:
			size[parent_x] += size[parent_y]
			parent[parent_y] = parent_x
test = int(input())
i = 1
while i <= test:
	c = 0
	s1 = list(map(int, input().split()))
	n = s1[0]
	q = s1[1]
	distance = []
	cycle = []
	edges = []
	parent = []
	size = []
	for j in range(n + 1):
		distance.append(0)
		cycle.append(0)
		edges.append([])
		parent.append(j)
		size.append(1)
	j = 1
	while j <= q:
		s2 = list(map(int, input().split()))
		src = s2[0]
		des = s2[1]
		weight = s2[2]
		parent[src] = find(parent, src, distance)
		parent[des] = find(parent, des, distance)
		if src == des:
			if weight != 0:
				c = 1
		elif src != des:
			if parent[src] == parent[des]:
				d1 = distance[des] - distance[src]
				if d1 % 2 == 0 and weight % 2 != 0:
					c = 1
				elif d1 % 2 != 0 and weight % 2 == 0:
					c = 1
			else:
				prev1 = parent[src]
				prev2 = parent[des]
				dis = distance[src]
				dis1 = distance[des]
				union(parent, size, src, des, cycle, distance, parent[src], parent[des])
				new1 = find2(parent, src, distance)
				new2 = find2(parent, des, distance)
				if new1 == prev1:
					distance[des] = distance[src] + weight
					if prev2 != des:
						update(parent, des, distance, dis1, new1)
					parent[des] = find2(parent, des, distance)
				else:
					distance[src] = distance[des] + weight
					if prev1 != src:
						update(parent, src, distance, dis, new1)
					parent[src] = find2(parent, src, distance)
		j += 1
	i += 1
	if c == 1:
		print('no')
	else:
		print('yes')


t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	brr = [None for i in range(n)]
	qu = []
	for j in range(q):
		(a, b, c) = map(int, input().split())
		a = a - 1
		b = b - 1
		qu.append((a, b, c))
	qu.sort()
	flag = 0
	for j in range(len(qu)):
		(a, b, c) = qu[j]
		if brr[a] == None and brr[b] == None:
			brr[a] = 0
			brr[b] = c
		elif brr[a] == None and brr[b] != None:
			if brr[b] == 1:
				brr[a] = (1 + c) % 2
			else:
				brr[a] = (0 + c) % 2
		elif brr[a] != None and brr[b] == None:
			if brr[a] == 1:
				brr[b] = (1 + c) % 2
			else:
				brr[b] = (0 + c) % 2
		if abs(brr[b] - brr[a]) != c:
			flag = 1
			break
	if flag == 0:
		print('yes')
	else:
		print('no')


import sys
sys.setrecursionlimit(1000000)
cases = int(input())

def dfs(index, values, flags, neighbors):
	flags[index - 1] = True
	for neighbor in neighbors[index]:
		if values[neighbor[0] - 1] is None:
			values[neighbor[0] - 1] = values[index - 1] + neighbor[1]
			if not flags[neighbor[0] - 1]:
				if dfs(neighbor[0], values, flags, neighbors) is False:
					return False
		elif (values[neighbor[0] - 1] - (values[index - 1] + neighbor[1])) % 2 != 0:
			return False
	return True
for _ in range(cases):
	(side, queries) = input().split()
	(side, queries) = (int(side), int(queries))
	possible = True
	neighbors = {num: set() for num in range(1, side + 1)}
	flags = [False for k in range(side)]
	values = [None for k in range(side)]
	for q in range(queries):
		(i, j, val) = input().split()
		(i, j, val) = (int(i), int(j), int(val))
		neighbors[i].add((j, val))
		neighbors[j].add((i, val))
	poss = True
	for index in range(1, side + 1):
		if not flags[index - 1]:
			values[index - 1] = 0
			poss &= dfs(index, values, flags, neighbors)
	if poss:
		print('yes')
	else:
		print('no')


def func():
	a = input().split()
	(n, q) = (int(a[0]), int(a[1]))
	arr = [-1 for i in range(n + 1)]
	z = {}
	dic2 = {}
	g_data = []
	for i in range(q):
		a = input().split()
		g_data.append([int(a[0]), int(a[1]), int(a[2])])
	j = 0
	for i in g_data:
		if i[0] == i[1] and i[2] == 1:
			print('no')
			return
		if i[0] not in z:
			printeve(arr, z, dic2, 0)
			if i[1] not in z:
				printeve(arr, z, dic2, 1)
				z[i[0]] = j
				z[i[1]] = j
				if i[0] != i[1]:
					dic2[j] = [i[0], i[1]]
				else:
					dic2[j] = [i[0]]
				if i[2] == 0:
					arr[i[0]] = 0
					arr[i[1]] = 0
				else:
					arr[i[0]] = 0
					arr[i[1]] = 1
				printeve(arr, z, dic2, 1)
				j += 1
			else:
				printeve(arr, z, dic2, 2)
				z[i[0]] = z[i[1]]
				dic2[z[i[1]]].append(i[0])
				arr[i[0]] = abs(arr[i[1]] - i[2])
				printeve(arr, z, dic2, 2)
			printeve(arr, z, dic2, 0)
		elif i[0] in z:
			printeve(arr, z, dic2, 3)
			if i[1] not in z:
				printeve(arr, z, dic2, 4)
				z[i[1]] = z[i[0]]
				dic2[z[i[0]]].append(i[1])
				arr[i[1]] = abs(arr[i[0]] - i[2])
				printeve(arr, z, dic2, 4)
			else:
				printeve(arr, z, dic2, 5)
				if z[i[0]] == z[i[1]]:
					if i[2] == 0:
						if arr[i[0]] != arr[i[1]]:
							print('no')
							return
					elif i[2] == 1:
						if arr[i[0]] == arr[i[1]]:
							print('no')
							return
				elif i[2] == 0:
					if arr[i[0]] == arr[i[1]]:
						if z[i[0]] > z[i[1]]:
							l = z[i[1]]
							h = z[i[0]]
						elif z[i[1]] > z[i[0]]:
							l = z[i[0]]
							h = z[i[1]]
						tempd = dic2[h]
						dic2[h] = []
						dic2[l] += tempd
						for ad in tempd:
							z[ad] = l
					elif arr[i[0]] != arr[i[1]]:
						if z[i[0]] > z[i[1]]:
							l = z[i[1]]
							h = z[i[0]]
						elif z[i[1]] > z[i[0]]:
							l = z[i[0]]
							h = z[i[1]]
						tempd = dic2[h]
						dic2[h] = []
						dic2[l] += tempd
						for ad in tempd:
							z[ad] = l
							arr[ad] = abs(arr[ad] - 1)
				elif i[2] == 1:
					if arr[i[0]] != arr[i[1]]:
						if z[i[0]] > z[i[1]]:
							l = z[i[1]]
							h = z[i[0]]
						elif z[i[1]] > z[i[0]]:
							l = z[i[0]]
							h = z[i[1]]
						tempd = dic2[h]
						dic2[h] = []
						dic2[l] += tempd
						for ad in tempd:
							z[ad] = l
					elif arr[i[0]] == arr[i[1]]:
						if z[i[0]] > z[i[1]]:
							l = z[i[1]]
							h = z[i[0]]
						elif z[i[1]] > z[i[0]]:
							l = z[i[0]]
							h = z[i[1]]
						tempd = dic2[h]
						dic2[h] = []
						dic2[l] += tempd
						for ad in tempd:
							z[ad] = l
							arr[ad] = abs(arr[ad] - 1)
				printeve(arr, z, dic2, 5)
	print('yes')

def printeve(a, b, c, s):
	pass
t = int(input())
for i in range(t):
	func()


t = int(input())
while t:
	t -= 1
	(n, q) = list(map(int, input().split()))
	a = dict()
	f = 1
	store = []
	for i in range(q):
		store.append(list(map(int, input().split())))
	store = sorted(store)
	for query in store:
		if query[0] == query[1] and query[2] == 1:
			f = 0
		elif query[0] in a and query[1] in a:
			x = set()
			y = set()
			for i in a[query[0]]:
				for j in a[query[1]]:
					if abs(i - j) == query[2]:
						x.add(i)
						y.add(j)
			if x == set():
				f = 0
			else:
				a[query[0]] = x
				a[query[1]] = y
		elif query[0] in a:
			y = set()
			for i in a[query[0]]:
				y.add(i - query[2])
				y.add(i + query[2])
			a[query[1]] = y
		elif query[1] in a:
			x = set()
			for i in a[query[1]]:
				x.add(i - query[2])
				x.add(i + query[2])
			a[query[0]] = x
		else:
			a[query[0]] = {0}
			a[query[1]] = {query[2], -query[2]}
	if f:
		print('yes')
	else:
		print('no')


t = int(input())
while t:
	t -= 1
	(n, q) = map(int, input().split())
	m = set()
	flag = 0
	l = []
	r = []
	a = [float('inf')] * n
	er = set()
	while q:
		q -= 1
		(i, j, val) = map(int, input().split())
		l.append([i, j, val])
		m.add((i, j))
		r.append((i, j))
		if i == j and val != 0:
			flag = 1
	l.sort()
	for k in range(len(l)):
		if (l[k][1], l[k][0]) in m and l[k][1] != l[k][0]:
			if l[r.index((l[k][1], l[k][0]))][2] != l[k][2]:
				flag = 1
		if l[k][0] in er and l[k][1] in er:
			if abs(a[l[k][0] - 1] - a[l[k][1] - 1]) != l[k][2]:
				flag = 1
		elif a[l[k][0] - 1] == float('inf') and a[l[k][1] - 1] == float('inf'):
			a[l[k][0] - 1] = 0
			a[l[k][1] - 1] = l[k][2]
		elif a[l[k][1] - 1] == float('inf') and a[l[k][0] - 1] == 1:
			if l[k][2] == 1:
				a[l[k][1] - 1] = 0
			else:
				a[l[k][1] - 1] = 1
		elif a[l[k][1] - 1] == float('inf') and a[l[k][0] - 1] == 0:
			if l[k][2] == 1:
				a[l[k][1] - 1] = 1
			else:
				a[l[k][1] - 1] = 0
		elif a[l[k][0] - 1] == float('inf') and a[l[k][1] - 1] == 1:
			if l[k][2] == 1:
				a[l[k][0] - 1] = 0
			else:
				a[l[k][0] - 1] = 1
		elif a[l[k][0] - 1] == float('inf') and a[l[k][1] - 1] == 0:
			if l[k][2] == 1:
				a[l[k][0] - 1] = 1
			else:
				a[l[k][0] - 1] = 0
		er.add(l[k][0])
		er.add(l[k][1])
	if flag == 1:
		print('no')
	else:
		print('yes')


for i in range(int(input())):
	state = 0
	(n, q) = map(int, input().split())
	d = []
	k = 0
	while k <= n:
		d.append(-1)
		k += 1
	gg = []
	k = 1
	while k <= q:
		(a, b, c) = map(int, input().split())
		gg.append([a, b, c])
		k += 1
	gg.sort()
	k = 0
	while k < q:
		if gg[k][0] == gg[k][1]:
			if gg[k][2] == 1:
				state = 1
				break
		elif d[gg[k][0]] == -1 and d[gg[k][1]] == -1:
			d[gg[k][0]] = 0
			if gg[k][2] == 0:
				d[gg[k][1]] = 0
			else:
				d[gg[k][1]] = 1
		elif d[gg[k][0]] != -1 and d[gg[k][1]] == -1:
			d[gg[k][1]] = abs(gg[k][2] - d[gg[k][0]])
		elif d[gg[k][0]] == -1 and d[gg[k][1]] != -1:
			d[gg[k][0]] = abs(gg[k][2] - d[gg[k][1]])
		elif d[gg[k][0]] != -1 and d[gg[k][1]] != -1:
			if gg[k][2] == 0 and d[gg[k][0]] != d[gg[k][1]]:
				state = 1
				break
			if gg[k][2] == 1 and d[gg[k][0]] == d[gg[k][1]]:
				state = 1
				break
		k += 1
	if state == 0:
		print('yes')
	else:
		print('no')


for _ in range(int(input())):
	(N, Q) = map(int, input().split())
	c = [-1] * N
	b = []
	flag = 0
	for j in range(Q):
		(p, q, r) = map(int, input().split())
		b.append([p, q, r])
	b.sort()
	for i in range(Q):
		(p, q, r) = b[i]
		p -= 1
		q -= 1
		if p == q:
			if r != 0:
				flag = 1
				break
		elif c[p] != -1 and c[q] != -1:
			if abs(c[p] - c[q]) != r:
				flag = 1
				break
		elif c[p] == -1 and c[q] == -1:
			c[q] = 0
			c[p] = c[q] + r
		elif c[p] == -1:
			if c[q] == 1:
				c[p] = c[q] - r
			else:
				c[p] = c[q] + r
		elif c[p] == 1:
			c[q] = c[p] - r
		else:
			c[q] = c[p] + r
	if flag == 1:
		print('no')
	else:
		print('yes')


import sys
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7
ts = int(input())
while ts > 0:
	(n, q) = list(map(int, input().split()))
	ncc = n - 1
	par = [i for i in range(n)]
	rank = [1] * n
	xor = [0] * n
	flag = 1

	def find(a):
		if par[a] == a:
			return a
		else:
			temp = find(par[a])
			xor[a] ^= xor[par[a]]
			par[a] = temp
			return temp

	def union(a, b):
		(a, b) = (find(a), find(b))
		if a == b:
			return
		if rank[a] > rank[b]:
			par[b] = a
			rank[a] += rank[b]
		elif rank[a] < rank[b]:
			par[a] = b
			rank[b] += rank[a]
		else:
			par[b] = a
			rank[a] += rank[b]
		par[b] = a
	for _ in range(q):
		(a, b, x) = list(map(int, input().split()))
		a -= 1
		b -= 1
		if flag == -1:
			continue
		para = find(a)
		parb = find(b)
		if para == parb and xor[a] ^ xor[b] != x:
			flag = -1
			continue
		if para != parb:
			if rank[para] < rank[parb]:
				xor[para] = xor[a] ^ xor[b] ^ x
				par[para] = parb
				rank[parb] += rank[para]
			else:
				xor[parb] = xor[a] ^ xor[b] ^ x
				par[parb] = para
				rank[para] += rank[parb]
			ncc -= 1
	if flag != -1:
		print('yes')
	else:
		print('no')
	ts -= 1


class DisjointNode:
	el: any
	parent = None
	opposite = None
	rank: int = 0

	def __init__(self, el) -> None:
		self.el = el
		self.parent = self

	def add_element(self, el):
		new_el = DisjointNode(el)
		new_el.parent = self
		return new_el

def find_parent(node: DisjointNode) -> DisjointNode:
	if node.parent != node:
		node.parent = find_parent(node=node.parent)
	return node.parent

def merge_sets(node1: DisjointNode, node2: DisjointNode) -> DisjointNode:
	(node1, node2) = (find_parent(node1), find_parent(node2))
	if node1.rank > node2.rank:
		node2.parent = node1
	else:
		node1.parent = node2
		if node1.rank == node2.rank:
			node2.rank += 1
	return node1.parent

def answer_of_task(n: int, qs: list) -> str:
	sets: list[DisjointNode] = [DisjointNode(el=i) for i in range(n + 1)]
	for q in qs:
		(i, j) = (q[0], q[1])
		val = q[2]
		if i == j:
			if val != 0:
				return 'no'
			continue
		sets[i] = find_parent(sets[i])
		sets[j] = find_parent(sets[j])
		sets[i].opposite = None if sets[i].opposite is None else find_parent(sets[i].opposite)
		sets[j].opposite = None if sets[j].opposite is None else find_parent(sets[j].opposite)
		if val == 0:
			if sets[i].opposite == sets[j]:
				return 'no'
			merge_sets(sets[i], sets[j])
		else:
			if sets[i] == sets[j]:
				return 'no'
			sets[i].opposite = sets[j] if sets[i].opposite is None else merge_sets(sets[i].opposite, sets[j])
			sets[j].opposite = sets[i] if sets[j].opposite is None else merge_sets(sets[j].opposite, sets[i])
	return 'yes'
T = int(input())
for k in range(T):
	(N, Q) = [int(x) for x in input().split()]
	qs = [[int(x) for x in input().split()] for i in range(Q)]
	print(answer_of_task(n=N, qs=qs))


test = int(input())
for bing in range(test):
	(n, q) = list(map(int, input().split()))
	b = [list(map(int, input().split())) for i in range(q)]
	m = 0
	x = 5.5
	b.sort()
	A = [x for i in range(n)]
	for i in range(q):
		if b[i][2] == 1:
			if A[b[i][0] - 1] == x and A[b[i][1] - 1] == x:
				A[b[i][0] - 1] = 1
				A[b[i][1] - 1] = 0
			elif A[b[i][0] - 1] == x:
				if A[b[i][1] - 1] == 0:
					A[b[i][0] - 1] = 1
				elif A[b[i][1] - 1] == 1:
					A[b[i][0] - 1] = 0
			elif A[b[i][1] - 1] == x:
				if A[b[i][0] - 1] == 0:
					A[b[i][1] - 1] = 1
				elif A[b[i][0] - 1] == 1:
					A[b[i][1] - 1] = 0
			elif A[b[i][0] - 1] == 0 and A[b[i][1] - 1] == 1:
				continue
			elif A[b[i][1] - 1] == 0 and A[b[i][0] - 1] == 1:
				continue
		elif b[i][2] == 0:
			if A[b[i][0] - 1] == x and A[b[i][1] - 1] == x:
				A[b[i][0] - 1] = 0
				A[b[i][1] - 1] = 0
			elif A[b[i][0] - 1] == x:
				A[b[i][0] - 1] = A[b[i][1] - 1]
			elif A[b[i][1] - 1] == x:
				A[b[i][1] - 1] = A[b[i][0] - 1]
			elif A[b[i][1] - 1] == 1 and A[b[i][0] - 1] == 1:
				continue
			elif A[b[i][1] - 1] == 0 and A[b[i][0] - 1] == 0:
				continue
	for i in range(q):
		if abs(A[b[i][1] - 1] - A[b[i][0] - 1]) != b[i][2]:
			m += 1
	if m != 0:
		print('no')
	else:
		print('yes')


T = int(input())
for i in range(T):
	(N, Q) = map(lambda s: int(s), input().split())
	valid = True
	r = [set() for i in range(N + 1)]
	visit = [False for i in range(N + 1)]
	delta = dict()
	a = [set() for i in range(N + 1)]
	for j in range(Q):
		(x, y, v) = map(lambda s: int(s), input().split())
		if x == y:
			valid = True if v == 0 else False
		else:
			r[x].add(y)
			r[y].add(x)
			if (x, y) not in delta:
				delta.setdefault((x, y), v)
				delta.setdefault((y, x), v)
			elif delta[x, y] != v:
				valid = False
	if valid:
		for (node, neighbor) in enumerate(r):
			if not valid:
				break
			if neighbor:
				if not a[node]:
					a[node].add(0)
				for n in neighbor:
					if not visit[n]:
						possible = set()
						for e in a[node]:
							(p1, p2) = (e + delta[node, n], e - delta[node, n])
							possible.add(p1)
							possible.add(p2)
						if a[n]:
							a[n] = a[n].intersection(possible)
							if not a[n]:
								valid = False
						else:
							a[n] = possible
			visit[node] = True
	if valid:
		print('yes')
	else:
		print('no')


t = int(input())
while t > 0:
	t -= 1
	(n, q) = map(int, input().split())
	Dic = {}
	ans = True
	A = [-1] * (n + 1)
	query = []
	for i in range(q):
		(x, y, z) = map(int, input().split())
		query.append([int(x), int(y), int(z)])
		if x == y and z != 0:
			ans = False
	query.sort()
	if ans == True:
		for i in range(q):
			x = query[i][0]
			y = query[i][1]
			z = query[i][2]
			st = str(query[i][0]) + ' ' + str(query[i][1])
			if A[x] == -1 and A[y] == -1:
				if z == 1:
					A[x] = 0
					A[y] = z
				else:
					A[x] = 0
					A[y] = 0
			elif A[x] != -1 and A[y] == -1:
				st1 = str(y) + ' ' + str(x)
				if Dic.get(st1, None) != None:
					if z != Dic.get(st1, None):
						ans = False
						break
				if z == 0:
					A[y] = A[x]
				else:
					A[y] = 1 - A[x]
			elif A[x] == -1 and A[y] != -1:
				st1 = str(y) + ' ' + str(x)
				if Dic.get(st1, None) != None:
					if z != Dic.get(st1, None):
						ans = False
						break
				if z == 0:
					A[x] = A[y]
				else:
					A[x] = 1 - A[y]
			elif A[x] != -1 and A[y] != -1:
				key = str(y) + ' ' + str(x)
				if Dic.get(st1, None) != None:
					if z != Dic.get(st1, None):
						ans = False
						break
				if abs(A[x] - A[y]) != z:
					ans = False
					break
			Dic[st] = z
	if ans == True:
		print('yes')
	else:
		print('no')


store = dict()

class node:

	def __init__(self, data):
		self.data = data
		self.parent = None
		self.rank = 0
		self.color = None

def makeset(data):
	new_node = node(data)
	new_node.parent = new_node
	store[data] = new_node

def union(data1, data2):
	node1 = store[data1]
	node2 = store[data2]
	parent1 = findset(node1)
	parent2 = findset(node2)
	if parent1.data == parent2.data:
		return
	if parent1.rank >= parent2.rank:
		parent1.rank += int(parent1.rank == parent2.rank)
		parent2.parent = parent1
	else:
		parent1.parent = parent2

def findset(new_node):
	parent = new_node.parent
	if new_node == parent:
		return new_node
	new_node.parent = findset(new_node.parent)
	return new_node.parent

def repre(data):
	return findset(store[data])
from sys import stdin, stdout
for _ in range(int(stdin.readline())):
	(n, q) = list(map(int, stdin.readline().split()))
	store = dict()
	different = []
	for i in range(1, n + 1):
		makeset(i)
	for i in range(q):
		(a, b, c) = list(map(int, stdin.readline().split()))
		if c == 0:
			union(a, b)
		else:
			different.append([a, b])
	ans = True
	for i in range(len(different)):
		ob1 = repre(different[i][0])
		ob2 = repre(different[i][1])
		if ob1.data == ob2.data:
			ans = 0
			break
		elif ob1.color == ob2.color and ob1.color != None:
			ans = 0
			break
		elif ob1.color == None and ob2.color == None:
			ob1.color = True
			ob2.color = not ob1.color
		elif ob1.color == None:
			ob1.color = not ob2.color
		elif ob2.color == None:
			ob2.color = not ob1.color
	if ans:
		stdout.write('yes\n')
	else:
		stdout.write('no\n')


def bfs(vertex):
	q = []
	arr[vertex] = 0
	q.append(vertex)
	while len(q) != 0:
		u = q.pop(0)
		visited[u] = True
		for (v, edge) in con[u]:
			if arr[v] == -1:
				arr[v] = edge ^ arr[u]
				q.append(v)
			elif arr[v] != edge ^ arr[u]:
				return False
	return True
for _ in range(int(input().strip())):
	(n, q) = map(int, input().strip().split())
	arr = [-1 for i in range(n + 1)]
	con = [[] for i in range(n + 1)]
	visited = [False for i in range(n + 1)]
	ans = True
	for y in range(q):
		(i, j, v) = map(int, input().strip().split())
		con[i].append((j, v))
	for i in range(1, n + 1):
		if visited[i] is False and ans is True:
			q = []
			arr[i] = 0
			q.append(i)
			while len(q) != 0:
				u = q.pop(0)
				visited[u] = True
				for (v, edge) in con[u]:
					if arr[v] == -1:
						arr[v] = edge ^ arr[u]
						q.append(v)
					elif arr[v] != edge ^ arr[u]:
						ans = False
						break
	if ans:
		print('yes')
	else:
		print('no')


from collections import defaultdict
for _ in range(int(input())):
	(n, q) = list(map(int, input().split()))
	graph = defaultdict(list)
	pair = {}
	ok = True
	for x in range(q):
		(i, j, val) = list(map(int, input().split()))
		if not ok:
			continue
		if i == j and val:
			ok = False
		else:
			if (i, j) in pair:
				if val != pair[i, j]:
					ok = False
				continue
			graph[i].append(j)
			graph[j].append(i)
			(pair[i, j], pair[j, i]) = (val, val)
	if not ok:
		print('no')
	else:
		visited = [False] * (n + 1)
		color = [0] * (n + 1)
		for i in range(1, n + 1):
			if not visited[i]:
				visited[i] = True
				color[i] = 1
				st = [i]
				while st:
					v = st.pop()
					for nb in graph[v]:
						if not visited[nb]:
							visited[nb] = True
							st.append(nb)
							if pair[v, nb] == 0:
								color[nb] = color[v]
							else:
								color[nb] = -1 * color[v]
						else:
							if pair[v, nb] == 0 and color[v] != color[nb]:
								ok = False
								break
							if pair[v, nb] == 1 and color[nb] != -1 * color[v]:
								ok = False
								break
		if ok:
			print('yes')
		else:
			print('no')


def union(a, b):
	fa = find(a)
	fb = find(b)
	if rank[fa] > rank[fb]:
		dsu[fb] = fa
	elif rank[fb] > rank[fa]:
		dsu[fa] = fb
	else:
		rank[fa] += 1
		dsu[fb] = fa

def find(x):
	while x != dsu[x]:
		dsu[x] = dsu[dsu[x]]
		x = dsu[x]
	return x
for _ in range(int(input())):
	(n, q) = list(map(int, input().split()))
	dsu = [i for i in range(n)]
	rank = [0] * n
	ones = []
	zeros = []
	for i in range(q):
		(a, b, c) = list(map(int, input().split()))
		if c == 1:
			ones.append([a - 1, b - 1])
		else:
			zeros.append([a - 1, b - 1])
	flag = 0
	for i in zeros:
		f1 = find(i[0])
		f2 = find(i[1])
		union(i[0], i[1])
	color = [0] * n
	for i in ones:
		f1 = find(i[0])
		f2 = find(i[1])
		if f1 == f2:
			flag = 1
		elif color[f1] == 0 and color[f2] == 0:
			color[f1] = -1
			color[f2] = 1
		elif color[f1] != 0 and color[f2] == 0:
			color[f2] = -color[f1]
		elif color[f2] != 0 and color[f1] == 0:
			color[f1] = -color[f2]
		elif color[f2] == color[f1]:
			flag = 1
	print('yes' if flag == 0 else 'no')


def func(qlist, N, Q):
	keys = {}
	values = {}
	count = 1
	A = []
	for i in range(N):
		A.append(0)
	for y in range(Q):
		[i, j, val] = qlist[y]
		if i == j and val != 0:
			print('no')
			return
		if i not in keys:
			if j not in keys:
				A[i - 1] = 0
				A[j - 1] = (1 - val) * A[i - 1] + val * (1 - A[i - 1])
				if i != j:
					values[count] = [i, j]
				else:
					values[count] = [i]
				keys[i] = count
				keys[j] = count
				count += 1
			else:
				keys[i] = keys[j]
				values[keys[j]].append(i)
				A[i - 1] = (1 - val) * A[j - 1] + val * (1 - A[j - 1])
		elif j not in keys:
			keys[j] = keys[i]
			values[keys[i]].append(j)
			A[j - 1] = (1 - val) * A[i - 1] + val * (1 - A[i - 1])
		elif keys[i] == keys[j]:
			if not (A[i - 1] - A[j - 1] == val or A[j - 1] - A[i - 1] == val):
				print('no')
				return
		else:
			if len(values[keys[i]]) >= len(values[keys[j]]):
				new_ind = keys[i]
				old_ind = keys[j]
			else:
				new_ind = keys[j]
				old_ind = keys[i]
			temp = values[old_ind]
			values[old_ind] = []
			values[new_ind] += temp
			if A[i - 1] - A[j - 1] == val or A[j - 1] - A[i - 1] == val:
				for t in temp:
					keys[t] = new_ind
			else:
				for t in temp:
					A[t - 1] = 1 - A[t - 1]
					keys[t] = new_ind
	print('yes')
T = int(input())
for x in range(T):
	inp = input().split()
	N = int(inp[0])
	Q = int(inp[1])
	qlist = []
	for y in range(Q):
		qlist.append([int(k) for k in input().split()])
	func(qlist, N, Q)


def main():
	for t in range(int(input())):
		(n, q) = [int(x) for x in input().strip().split()]
		a = [None] * n
		failure = False

		def make_key(i, j):
			return tuple(sorted([i, j]))
		relations = dict()
		mapping = dict()

		def read_queries():
			nonlocal failure
			for query in range(q):
				(i, j, v) = [int(x) for x in input().strip().split()]
				if i == j or failure:
					if v != 0:
						failure = True
				else:
					i -= 1
					j -= 1
					k = make_key(i, j)
					if k in relations:
						if relations[k] != v:
							failure = True
					else:
						relations[k] = v
					if i in mapping:
						mapping[i].append(j)
					else:
						mapping[i] = [j]
					if j in mapping:
						mapping[j].append(i)
					else:
						mapping[j] = [i]
		read_queries()
		if failure:
			print('no')
			continue

		def make_possibilities(i, v):
			nonlocal a
			ans = set()
			for p in a[i]:
				ans.add(p + v)
				ans.add(p - v)
				ans.add(v - p)
			return ans

		def combine_possibilities(i, j, v):
			nonlocal a
			newi = set()
			newj = set()
			for pi in a[i]:
				for pj in a[j]:
					if pi + pj == v or pi - pj == v or pj - pi == v:
						newi.add(pi)
						newj.add(pj)
			a[i] = newi
			a[j] = newj
			return len(newi) != 0 and len(newj) != 0

		def solve():
			nonlocal failure
			while len(mapping) > 0 and (not failure):
				done = set()
				todo = []
				for i in mapping:
					a[i] = {0}
					done.add(i)
					todo.append(i)
					break
				while len(todo) > 0 and (not failure):
					i = todo.pop()
					for j in mapping[i]:
						k = make_key(i, j)
						if k not in relations:
							continue
						v = relations[k]
						del relations[k]
						if a[j] is None:
							a[j] = make_possibilities(i, v)
						else:
							success = combine_possibilities(i, j, v)
							if not success:
								failure = True
						if j not in done:
							todo.append(j)
							done.add(j)
				for i in done:
					del mapping[i]
				done.clear()
		solve()
		print('no' if failure else 'yes')
main()


def make_graph(inp):
	g = {}
	for x in inp:
		if not x[0] in g:
			g[x[0]] = {}
		if x[1] in g[x[0]]:
			if g[x[0]][x[1]] != inp[x]:
				return None
		g[x[0]][x[1]] = inp[x]
		g[x[1]][x[0]] = inp[x]
	return g

def bfs(g, a, s, visited, flag):
	a[s] = 0
	q = [s]
	visited[s] = True
	while len(q) != 0:
		u = q.pop(0)
		for (v, val) in g[u]:
			if not visited[v]:
				q.append(v)
				visited[v] = True
				if val == 1:
					if a[u] == 0:
						a[v] = 1
					else:
						a[v] = 0
				else:
					a[v] = a[u]
			elif val != abs(a[u] - a[v]):
				flag[0] = False
				return

def solve(inp, n):
	a = [None for i in range(n + 1)]
	visited = [False for i in range(n + 1)]
	obj = [True, 0]
	for i in list(range(1, n + 1)):
		if not visited[i]:
			bfs(inp, a, i, visited, obj)
	if obj[0]:
		print('yes')
	else:
		print('no')
for _ in range(int(input())):
	(n, q) = tuple(map(int, input().split()))
	adj = [[] for i in range(n + 1)]
	while q:
		(i, j, val) = tuple(map(int, input().split()))
		adj[i].append((j, val))
		adj[j].append((i, val))
		q -= 1
	solve(adj, n)


class node:

	def __init__(self, key):
		self.data = key
		self.parent = None
		self.rank = 0
		self.color = None

class disjoint:

	def __init__(self, n):
		self.mapp = [None] * n
		for i in range(n):
			self.mapp[i] = node(i)
			self.mapp[i].parent = self.mapp[i]

	def find(self, a):
		node1 = self.mapp[a]
		while 1:
			if node1.parent == node1:
				break
			else:
				node1 = node1.parent
		if node1.rank >= 2:
			self.mapp[a].parent = node1
		return node1

	def union(self, a, b):
		rep1 = self.find(a)
		rep2 = self.find(b)
		if rep1.color == 0 and rep2.color == 1 or (rep2.color == 0 and rep1.color == 1):
			return False
		elif rep1.rank == rep2.rank:
			rep1.rank += 1
			rep2.rank = 0
			rep2.parent = rep1
		elif rep1.rank > rep2.rank:
			rep1.rank += 1
			rep2.rank = 0
			rep2.parent = rep1
		else:
			rep2.rank += 1
			rep1.rank = 0
			rep1.parent = rep2
		return True

	def colored(self, a, b):
		rep1 = self.find(a)
		rep2 = self.find(b)
		if rep1 == rep2:
			return False
		elif rep1.color == None and rep2.color == None:
			rep1.color = 0
			rep2.color = 1
		elif rep2.color == None:
			rep2.color = (rep1.color + 1) % 2
		elif rep1.color == None:
			rep1.color = (rep2.color + 1) % 2
		elif rep1.color == rep2.color:
			return False
		return True
t = int(input())
for i in range(t):
	(n, q) = map(int, input().strip().split())
	d = disjoint(n)
	flag = 0
	for j in range(q):
		(s0, s1, s2) = map(int, input().strip().split())
		if flag == 0:
			if s0 == s1:
				if s2 == 1:
					flag = 1
			elif s2 == 1:
				if d.colored(s0 - 1, s1 - 1) == False:
					flag = 1
			elif s2 == 0:
				if d.union(s0 - 1, s1 - 1) == False:
					flag = 1
	if flag == 0:
		print('yes')
	else:
		print('no')


from collections import defaultdict
for _ in range(int(input())):
	sames = defaultdict(list)
	differents = defaultdict(list)
	(n, q) = map(int, input().split())
	ans = True
	for query in range(q):
		(i, j, diff) = map(int, input().split())
		if diff:
			if i == j:
				ans = False
			differents[i - 1].append(j - 1)
			differents[j - 1].append(i - 1)
		else:
			sames[i - 1].append(j - 1)
			sames[j - 1].append(i - 1)
	a = [-1] * n
	if ans:
		for i in range(n):
			if a[i] != -1:
				continue
			a[i] = 0
			queue = [i]
			while queue:
				node = queue.pop(0)
				for new_node in sames[node]:
					if a[new_node] == -1:
						a[new_node] = a[node]
						queue.append(new_node)
					elif a[new_node] != a[node]:
						ans = False
						break
				if not ans:
					break
				for new_node in differents[node]:
					if a[new_node] == -1:
						a[new_node] = (a[node] + 1) % 2
						queue.append(new_node)
					elif a[new_node] == a[node]:
						ans = False
						break
				if not ans:
					break
	print('yes') if ans else print('no')