Separate Cities

You are given an undirected graph representing cities and roads. The graph has n vertices (cities) and m edges (roads). Your task is to determine whether it is possible to partition the set of cities into two disjoint groups such that no two cities within the same group are directly connected by a road. In other words, you need to check if the graph is bipartite.

If a valid partition exists, output YES on the first line followed by a line of n integers where the i-th integer (either 1 or 2) indicates the group to which city i belongs. If no valid partition exists, simply output NO.

Note: If there are multiple valid answers, printing any one of them is acceptable.

Mathematical Formulation:

The condition for a bipartite graph is that its vertex set V can be partitioned into two subsets V₁ and V₂ such that for every edge \( (u, v) \), we have \( u \in V_1 \) and \( v \in V_2 \) or vice versa. In other words, no edge connects two vertices within the same subset.

inputFormat

The input is given from stdin and has the following format:

n m
u1 v1
...
um vm

Here, n is the number of cities, m is the number of roads, and each subsequent line contains two integers representing an undirected edge between two cities.

outputFormat

Output to stdout. If the graph is bipartite, print YES on the first line, followed by a second line containing n integers (each being either 1 or 2) representing the partition of the cities. If the graph is not bipartite, simply print NO.

## sample

4 4
1 2
2 3
3 4
4 1

YES
1 2 1 2

</p>