For a load-balancing experiment, Rakib wants to know if the network can be split into exactly two groups such that every connection goes between groups (never within one). Given an undirected graph with N nodes and M edges, print "YES" if it can be 2-colored (bipartite), else "NO". Use BFS/DFS coloring, and remember the graph might not be connected.
Input
Line1: N M. Next M lines: u v.
Output
"YES" or "NO".
Constraints
1 ≤ N ≤ 10^5, 0 ≤ M ≤ 2×10^5
Sample Input
4 4 1 2 2 3 3 4 4 1
Sample Output
YES
main.c
Loading editor…
Write C, then Run (custom I/O) or Submit (sample tests). ⌘/Ctrl+Enter submits.