366. Can It Be Two-Coloured
Print Yes if the vertices can be split into two groups so that every edge
joins a vertex in one group to a vertex in the other. Print No otherwise.
Think of it as colouring with two colours so that no edge joins two vertices of the same colour.
The method writes itself. Colour a starting vertex, then colour every neighbour the opposite colour, and so on. There is never a choice: once one vertex is coloured, everything reachable from it is forced.
A conflict, meaning an edge between two vertices already the same colour, proves it is impossible.
The tests are chosen to show what actually decides this. A four-cycle can be two-coloured and a triangle and a five-cycle cannot: the obstruction is an ODD cycle, and nothing else.
Constraints - `1 ≤ n ≤ 100000` - `0 ≤ m ≤ 200000` - There are no self-loops and no repeated edges.
Input
The first line contains two integers n and m, the number of vertices and
edges. Each of the next m lines contains two integers u and v, an
undirected edge between those vertices. Vertices are numbered 1 to n.
Output
Print Yes or No on one line.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.