ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Чемпионат УрГУ 2000

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

D. Авиакомпания

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
Некоторая авиакомпания является спонсором празднования 80-летия Уральского государственного университета. В обмен на это авиакомпания хочет, чтобы университет помог ей. Авиакомпания обслуживает N аэропортов и выполняет рейсы между некоторыми из них. Для упрощения работы рейсы нумеруются целыми числами от 1 до M. Если между двумя аэропортами есть рейс, то самолет летит в обоих направлениях с одним и тем же номером рейса. Между любыми двумя аэропортами может быть только один рейс. Из любого аэропорта можно добраться до любого другого, используя рейсы только этой авиакомпании.
Авиакомпания понимает, что ее самолеты могут привлечь террористов. Чтобы создать им трудности, компания хочет пронумеровать рейсы неким особым образом. Если есть несколько рейсов, которые отправляются из одного аэропорта, то наибольший общий делитель номеров их рейсов должен быть равен единице. Компания обращается к вам за помощью и помните, что это спонсор – вы должны поработать как следует.
Необходимо написать программу, которая найдет требуемую нумерацию или сообщит, что выполнить требования невозможно. Если возможно несколько нумераций, то достаточно найти любую из них.

Исходные данные

Первая строка содержит целые числа N и M (2 ≤ N ≤ 50; 1 ≤ MN · (N − 1) / 2). Следующие M строк содержат информацию о рейсах. Каждый рейс задается номерами аэропортов, которые он соединяет. Номера аэропортов – различные целые числа в диапазоне от 1 до N.

Результат

В первой строке выведите «YES», если можно найти требуемую нумерацию, и «NO» в противном случае. Если ответ «YES», то вторая строка должна содержать любую возможную нумерацию рейсов. Номера должны следовать в том порядке, в котором эти рейсы были перечислены во входных данных.

Пример

исходные данныерезультат
6 6
1 2
2 3
2 4
4 3
5 6
4 5
YES
4 2 3 1 5 6
Автор задачи: Дмитрий Филимоненков
Источник задачи: Пятый командный чемпионат УрГУ по программированию (Октябрь 2000 г.)
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1040. Авиакомпания