Update appNew update is available. Click here to update.

Colour The Graph

Last Updated: 7 Jul, 2016
Difficulty: Moderate


Try Problem

You are given a graph with 'N' vertices numbered from '1' to 'N' and 'M' edges. You have to colour this graph in two different colours, say blue and red such that no two vertices connected by an edge are of the same colour.

Note :
The given graph may have connected components.
Input Format :
The first line of input contains two integers 'V' and 'E', separated by a single space. They denote the total number of vertices and edges respectively. 

From the second line onwards, the next 'E' lines represent an edge between the two vertices.

Every edge is represented by two vertices(u, v) that share an edge between them. The values of the vertices would again be separated by a single space.
Output Format :
Print "YES" if it is possible else print "NO".
 Constraints :
1 <= E <= 10 ^ 5
1 <= V <= 10 ^ 6

Time Limit: 1 sec