Олимпиадный тренинг

Задача . F. Граф без длинных ориентированных путей

Задача

Темы: графы поиск в глубину и подобное *1700

Дан связный неориентированный граф, состоящий из $n$ вершин и $m$ ребер. В заданном графе нет ни петель, ни кратных ребер.

Ориентируйте ребра графа таким образом, что в полученном ориентированном графе не будет путей, состоящих из двух или более ребер.

Входные данные

В первой строке заданы два целых числа $n$ и $m$ ($2 \le n \le 2 \cdot 10^5$, $n - 1 \le m \le 2 \cdot 10^5$) — количество вершин и ребер, соответственно.

Следующие $m$ строк задают ребра: ребро $i$ задается парой вершин $u_i$, $v_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$). В заданном графе нет кратных ребер, т. е. для каждой пары ($u_i, v_i$) не существует других пар ($u_i, v_i$) и ($v_i, u_i$) в списке ребер. Также гарантируется, что данный граф является связным (между любой парой вершин существует путь).

Выходные данные

Если невозможно ориентировать ребра таким образом, что в графе не будет путей из двух или более ребер, выведите "NO" в первой строке.

Иначе в первой строке выведите "YES", а затем выведите любую подходящую ориентацию ребер в виде бинарной строки (строки, состоящей только из '0' и '1') длины $m$. $i$-й символ строки должен быть '0', если $i$-е ребро графа надо ориентировать из $u_i$ в $v_i$, и '1' в противном случае. Ребра пронумерованы в том же порядке, в котором заданы во входных данных.

Примечание

Граф в первом примере из условия: $\text{[math]}$

Один из возможных ответов: $\text{[math]}$

Примеры

№	Входные данные	Выходные данные
1	6 5 1 5 2 1 1 4 3 1 6 1	YES 10100

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	5

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет