|
Граф называется двудольным, если его вершины можно раскрасить в два цвета
так, что нет ребер, соединяющих вершины одинакового цвета (то есть
каждое ребро идет из вершины 1-го цвета в вершину 2-го).
Дан граф. Требуется проверить, является ли он двудольным, и если да,
то раскрасить его вершины.
Input
Сначала вводится число N - количество вершин графа (не превышает 100).
Далее идет матрица смежности - матрица размером
N x N из нулей и единиц (где 0 обозначает отсутствие ребра, 1 - наличие). Граф
неориентированный, без петель.
Output
Выведите YES или NO в зависимости от того, является ли граф двудольным. В случае ответа YES
во второй строке выведите N чисел - цвета, в которые нужно раскрасить вершины. В случае нескольких правильных вариантов выведите любой.
Sample
| Input | Output |
|---|
3
0 1 1
1 0 1
1 1 0
|
NO
|
3
0 1 1
1 0 0
1 0 0
|
YES
1 2 2
|
| 