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

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

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

D. Airline Company

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ


An airline company is a sponsor of the 80-th Anniversary celebration at the Ural State University. In return for it the company wants the University to help it. The company serves N airports and carries out flights between some of them. In order to simplify the work the flights are numbered with integers from 1 up to M. If there is a flight between two airports a plane flies in the both directions with the same flight number. There may be only one flight between any two airports. One can fly between any pair of airports served by company using only its flights.
The airline company understands that its planes may attract terrorists. In order to create difficulties for terrorists the company wants to number the flights in some special manner. If there are several flights that depart from one airport then the greatest common divisor of their flight numbers should be equal to 1. The company turns to you for help (remember, this is a sponsor; you are to work properly).


You should write a program that finds a required numbering or informs that it is impossible to satisfy the requirements. If several numberings are possible, it is sufficient to find any one of them.

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

The first line of input contains numbers N and M separated with a space (2 ≤ N ≤ 50). The next M lines contain information on flights. Each flight is determined by the numbers of the airports that it connects. The numbers of the airports are separated with a space.


The first line of an output should contain YES, if it is possible to find a required numbering, and NO otherwise. If the answer is YES, the second line should contain a possible numbering of flights. The numbers are to be ordered as it is done in the input. Flight numbers are to be separated with a space.


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