Дан простой связный неориентированный граф, состоящий из \(n\) вершин и \(m\) ребер. Вершины пронумерованы от \(1\) до \(n\).
Вершинное покрытие графа — это такой набор вершин, что у каждого ребра есть хотя бы один конец в наборе.
Назовем свободным вершинным покрытием такое вершинное покрытие, что не более одного ребра имеет оба конца в наборе.
Найдите свободное вершинное покрытие графа или сообщите, что его нет. Если существует несколько ответов, то выведите любой из них.
Выходные данные
На каждый набор входных данных в первой строке выведите YES, если свободное вершинное покрытие существует и NO, если нет. Если оно существует, то во второй строке выведите бинарную строку \(s\) длины \(n\), где \(s_i = 1\) означает, что \(i\)-я вершина в вершинном покрытии, а \(s_i = 0\) означает, что \(i\)-я вершина не в нем.
Если существует несколько ответов, то выведите любой из них.
Примечание
Здесь изображены графы из первого примера. Вершины в свободном вершинном покрытии помечены красным.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
6 5
1 3
2 4
3 4
3 5
4 6
4 6
1 2
2 3
3 4
1 4
1 3
2 4
8 11
1 3
2 4
3 5
4 6
5 7
6 8
1 2
3 4
5 6
7 8
7 2
4 5
1 2
2 3
3 4
1 3
2 4
|
YES
001100
NO
YES
01100110
YES
0110
|
|
2
|
1
10 15
9 4
3 4
6 4
1 2
8 2
8 3
7 2
9 5
7 8
5 10
1 4
2 10
5 3
5 7
2 9
|
YES
0101100100
|
|
3
|
1
10 19
7 9
5 3
3 4
1 6
9 4
1 4
10 5
7 1
9 2
8 3
7 3
10 9
2 10
9 8
3 2
1 5
10 7
9 5
1 2
|
YES
1010000011
|