Bipartite Graph Check

Given an undirected graph with \(n\) vertices and \(m\) edges, determine if the graph can be colored using exactly two colors such that no two adjacent vertices share the same color. If such a coloring exists, output "YES" and a valid color assignment (using 1 and 2) for all vertices. Otherwise, output "NO".

The graph may be disconnected, and the vertices are numbered from 1 to \(n\). For each disconnected component, you should start by assigning the color 1 to the first encountered vertex and then alternate the colors using breadth-first search (BFS).

Formally, given a graph \(G = (V,E)\) with \(|V| = n\) and \(|E| = m\), determine if there exists a function \(f : V \to \{1,2\}\) such that for every edge \((u,v) \in E\), \(f(u) \neq f(v)\).

inputFormat

The input is given via standard input (stdin). The first line contains two integers \(n\) and \(m\), representing the number of vertices and the number of edges respectively.

The following \(m\) lines each contain two integers \(u\) and \(v\), indicating that there is an undirected edge between vertices \(u\) and \(v\).

outputFormat

If the graph is bipartite, print "YES" on the first line. On the second line, print \(n\) integers separated by spaces indicating the color (either 1 or 2) assigned to the vertices in order from 1 to \(n\).

If the graph is not bipartite, print "NO".

## sample

4 4
1 2
2 3
3 4
4 1

YES
1 2 1 2

</p>