BATGODEL and SUPERTURING
All submissions for this problem are available.
Superman is afraid of Batman (Yes he is). Batman is building a Super Bat-Gun 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 Bat-Gun 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 Turing-Subgraphs of G. We call G' to be Turing-Subgraphs 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.
- 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.
- For each test case, output a single line. If BatGodel(G) is odd print "1" else print "0".
- 1 <= t <= 100
Input: 3 1 1 1 1 2 2 2 1 2 3 2 1 5 2 1 1 2 5 Output: 0 1 0
In first and second case there is only 1 Turing-Subgraph of G. In third there are no Turing-Subgraph of G.
|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|
Fetching successful submissions