ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

USU Championship 2000

About     Problems     Submit solution     Judge status     Standings
Contest is over

D. Airline Company

Time limit: 0.5 second
Memory limit: 64 MB

Background

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).

Problem

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.

Input

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.

Output

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.

Sample

inputoutput
6 6
1 2
2 3
2 4
4 3
5 6
4 5
YES
4 2 3 1 5 6
Problem Author: Dmitry Filimonenkov
Problem Source: Ural State University Internal Contest October'2000 Students Session
To submit the solution for this problem go to the Problem set: 1040. Airline Company