Score : 600 points
Kenkoooo found a simple connected graph. The vertices are numbered 1 through n. The i-th edge connects Vertex u_i and v_i, and has a fixed integer s_i.
Kenkoooo is trying to write a positive integer in each vertex so that the following condition is satisfied:
Find the number of such ways to write positive integers in the vertices.
Input is given from Standard Input in the following format:
n m u_1 v_1 s_1 : u_m v_m s_m
Print the number of ways to write positive integers in the vertices so that the condition is satisfied.
3 3 1 2 3 2 3 5 1 3 4
1
The condition will be satisfied if we write 1,2 and 3 in vertices 1,2 and 3, respectively. There is no other way to satisfy the condition, so the answer is 1.
4 3 1 2 6 2 3 7 3 4 5
3
Let a,b,c and d be the numbers to write in vertices 1,2,3 and 4, respectively. There are three quadruples (a,b,c,d) that satisfy the condition:
8 7 1 2 1000000000 2 3 2 3 4 1000000000 4 5 2 5 6 1000000000 6 7 2 7 8 1000000000
0