Applying Depth Traversal

During a test, Professor Floyd noticed that some of the students were exchanging notes. At first, he wanted to give them all twos, but that day the professor was kind, and therefore he decided to divide the students into two groups: those who cheated and those who let them cheat, and give only the first two.

 

The professor has a record of all pairs of students who exchanged notes. It is required to determine whether he can divide the students into two groups so that any exchange of notes is carried out from a student of one group to a student of another group.

 

Input: The first line contains two numbers N and M - the number of students and the number of pairs of students exchanging notes (1<=N<=100, 0<=M<=(N(N−1))/2. Next, M lines contain descriptions of pairs of students: two numbers corresponding to the numbers of students exchanging notes (students are numbered starting from 1) Each pair of students is listed at most one times.

Output: You need to output the answer to Professor Floyd's problem. If it is possible to divide the students into two groups, print YES; otherwise print NO.

Examples

#	Input	Output
1	3 2 1 2 2 3	YES
2	3 3 1 2 2 3 1 3	NO

A graph is called bipartite if its vertices can be colored in two colors so that there are no edges connecting vertices of the same color (that is, each edge goes from the vertex of the 1st color to the vertex of the 2nd).

Given a graph. It is required to check whether it is bipartite, and if so, color its vertices.

 

Input
The first line first contains the number N - the number of graph vertices (does not exceed 100). Next comes the adjacency matrix - a NxN matrix of 0 and 1 (0 means no edge, 1 means presence). The graph is undirected, without loops.

 

Imprint 
On the first line print one of the messages YES or NO (depending on whether the graph is bipartite or not). If the answer is YES, in the second line print N numbers - the colors to color the vertices: for the first color use the value 1, for the second color - the value 2. The first vertex should be color 1.