Signed graph P38073


Statement
 

pdf   zip

html

An undirected graph is signed if each edge has a positive or negative sign. A signed graph is called balanced if the product of all signs around every cycle is positive.

Given a signed graph, can you tell if it is balanced or not?

Input

Input consists of several cases, each one with the number of vertices n, followed by the number of edges m, followed by m triples x y s to indicate an edge between x and y with sign s ∈ { −1, 1 }. Assume 1 ≤ n ≤ 105, 0 ≤ m ≤ 5n, that vertices are numbered between 0 and n−1, x ≠ y, and that there is no more than one edge between x and y.

Output

For every graph, print “yes” if it is balanced; otherwise print “no”.

Public test cases

  • Input

    7 5
0 1 1
1 2 -1
1 4 1
2 4 -1
6 5 -1

3 3
0 1 -1
2 0 -1
2 1 -1

    Output

    yes
no
    • Information
    Author
    Conrado Martínez
    Language
    English
    Official solutions
    C++
    User solutions
    C++