Задача «Двудольный граф»

Граф называется двудольным, если его вершины можно раскрасить в два цвета так, что нет ребер, соединяющих вершины одинакового цвета (то есть каждое ребро идет из вершины 1-го цвета в вершину 2-го).

Дан граф. Требуется проверить, является ли он двудольным, и если да, то раскрасить его вершины.

Формат входного файла input.txt:

Во входном файле задано сначала число N - количество вершин графа (не превышает 100). Далее идет матрица смежности - матрица размером NxN из 0 и 1 (0 обозначает отсутствие ребра, 1 - наличие). Граф неориентированный, без петель.

Формат выходного файла output.txt:

В первую строку выведите одно из сообщений YES или NO (в зависимости от того, является ли граф двудольным или нет). В случае ответа YES во второй строке выведите N чисел - цвета, в которые нужно раскрасить вершины.

Пример:                Входной файл       Выходной файл

1                             3                                        NO

0 1 1

1 0 1

1 1 0

2                             3                                        YES

0 1 1                                   1 2 2

1 0 0

1 0 0