BATGODEL and SUPERTURING

All submissions for this problem are available.
Problem description.
Superman is afraid of Batman (Yes he is). Batman is building a Super BatGun which emplifies power of Kryptonite stone.
Superman wants to destroy the Gun before it's working. Superman knows all hideouts of Batman (thanks to infrared vision). There are many hideouts and in each hideout Batman have enough security. Superman is super but he fears that he may not be powerful enough to attack all hideouts in given time (some hideouts have Kryptonites). Knowing that such a Super BatGun puts some constraints on the circuit design of hideout, Superman thinks that he may plan his attacks to beat Batman.
A circuit design of Batman's hideout can be considered as a weighted directed graph with self loops but no multiple edges between two vertices.
The constraint on such a graph, G, is that it BatGodel(G) must be odd. Before defining BatGodel, let's look at SuperTuring(G).
SuperTuring(G) is set of TuringSubgraphs of G. We call G' to be TuringSubgraphs of G if G' is
 Subgraph of G.
 Every vertex in G is in G'.
 Every vertex belong to exactly one cycle in G'.
We define FlashCayley(G) = Product of weight of all edges of G.
Help Superman in beating Batman (he needs it yes he does!!!). Superman will give you a directed graph, G, and you need to tell whether BatGodel(G) is odd or even.
Input
Input description.
 The first line of the input contains an integer t denoting the number of test cases.

In each test case

first line contains two integers separated by space n and m.
n is number of vertices and m is number of edges in graph. 
Then m lines follows each containing three integers u, v and w which means there is
an edge from u to v of weight w

first line contains two integers separated by space n and m.
Note that multiple edges between two vertices are not allowed but self loops are allowed.
Output
Output description.
 For each test case, output a single line. If BatGodel(G) is odd print "1" else print "0".
Constraints
 1 <= t <= 100
 1<=n<=100
 0<=m<=n*n
 1<=u,v<=n
 0<=w<=10^{5}
Example
Input: 3 1 1 1 1 2 2 2 1 2 3 2 1 5 2 1 1 2 5 Output: 0 1 0
Explanation
In first and second case there is only 1 TuringSubgraph of G. In third there are no TuringSubgraph of G.
Author:  admin2 
Tags  admin2 
Date Added:  10032016 
Time Limit:  1 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