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.
Examples
| # |
Input |
Output |
| 1 |
3
0 1 1
1 0 1
1 1 0
|
NO |
| 2 |
3
0 1 1
1 0 0
1 0 0
|
YES
1 2 2
|