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.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'store=dict()\nclass node:\n def __init__(self,data):\n  self.data=data\n  self.parent=None\n  self.rank=0\n  self.color=None\ndef makeset(data):\n new_node=node(data)\n new_node.parent=new_node\n store[data]=new_node\ndef union(data1,data2):\n node1=store[data1]\n node2=store[data2]\n\n parent1=findset(node1)\n parent2=findset(node2)\n if parent1.data==parent2.data :\n  return\n if parent1.rank >= parent2.rank :\n  parent1.rank+=int(parent1.rank==parent2.rank)\n  parent2.parent=parent1\n else:\n  parent1.parent=parent2\ndef findset(new_node):\n parent=new_node.parent\n if new_node==parent :\n  return new_node\n new_node.parent=findset(new_node.parent)\n return new_node.parent\ndef repre(data):\n return findset(store[data])\nfrom sys import stdin,stdout\nfor _ in range(int(stdin.readline())):\n n,q=list(map(int,stdin.readline().split()))\n store=dict();different=[]\n for i in range(1,n+1):\n  makeset(i)\n for i in range(q):\n  a,b,c=list(map(int,stdin.readline().split()))\n  if c==0:\n   union(a,b)\n  else:\n   different.append([a,b])\n ans=True\n for i in range(len(different)):\n  ob1=repre(different[i][0])\n  ob2=repre(different[i][1])\n  if ob1.data==ob2.data:\n   ans=0\n   break\n  elif ob1.color==ob2.color and ob1.color!=None:\n   ans=0\n   break\n  else:\n   if ob1.color==None and ob2.color==None :\n    ob1.color=True\n    ob2.color= not ob1.color\n   elif ob1.color==None :\n    ob1.color= not ob2.color\n   elif ob2.color==None:\n    ob2.color= not ob1.color\n   \n if ans:\n  stdout.write("yes\\n")\n else:\n  stdout.write("no\\n")\n\n\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 17409