Two colors P29033


Statement
 

pdf   zip

thehtml

Write a program that, given an undirected graph, tells if we can paint all vertices with only two colors, in such a way that no two neighboring vertices have the same color.

Input

Input consists of several cases, each with the number of vertices n and the number of edges ‍m, followed by m pairs x y indicating an edge between x and y. Suppose 1 ≤ n ≤ 104, 0 ≤ m ≤ 5n, that vertices are numbered from 0 to n − 1, xy, and that there is no more than one edge between any pair x y.

Output

For every case, print “yes” if the graph is two-colorable, and “no” otherwise.

Public test cases
  • Input

    2 1
    0 1
    
    4 3
    1 2  3 2  3 1
    
    1 0
    
    4 2
    0 3  2 1
    

    Output

    yes
    no
    yes
    yes
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++ Python
    User solutions
    C++ Python