Fill The Matrix

All submissions for this problem are available.
Read problems statements in mandarin chinese, russian and vietnamese as well.
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 ≤ 10^{6}
 2 ≤ N ≤ 10^{5}
 1 ≤ Q ≤ 10^{6}
 1 ≤ i, j ≤ N
 0 ≤ val ≤ 1
 Sum of each of N, Q over all test cases doesn't exceed 10^{6}
Subtasks
 Subtask #1 (40 points) 2 ≤ N ≤ 10^{3}, 1 ≤ Q ≤ 10^{3}, Sum of each of N, Q over all test cases doesn't exceed 10^{4}
 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 0This 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.
Author:  admin2 
Tester:  jingbo_adm 
Editorial  https://discuss.codechef.com/problems/FILLMTR 
Tags  admin2, bipartite, easymedium, sept17 
Date Added:  16082017 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions