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.

Difficulty: interview

Starter code:

Solutions:
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
   # print("no")

  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

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
  else:
   #print(color)
   if 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")


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
  else:
   if 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")




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')