286. Ancient decoration
Time limit per test: 0.25
second(s)
Memory limit: 65536
kilobytes
input: standard
output: standard
The ancient race of
has built
N cities connected with twoway roads. They believed in magic of an even number
K and built the roads in such a way that each city had exactly
K roads going from it.
The Hollars decided to decorate some roads because of their religious holiday. Because they also believe in magic of an even number 2, each city must have exactly 2 decorated roads going from it.
You have to find the roads needing to be decorated.
Input
The first line of the input contains integers
N and
K (2≤
KNK/2 lines contains description of one road, being the numbers of the cities connected by this road. The cities are numbered starting from 1. There is no road from a city to itself; each pair of cities is connected by at most one road.
Output
If it is impossible to decorate the roads, the only line of the output must contain 'NO' (without quotes). Otherwise the first line of the output must contain 'YES' (without quotes); the rest of the output must contain N lines, each containing one number of a road to be decorated. The roads are numbered starting from 1 in the same order as they appear in the input.
Example(s)
sample input

sample output

9 4
1 2
1 3
1 4
1 5
2 3
3 4
4 5
5 2
2 6
3 7
4 8
5 9
6 7
7 8
8 9
9 6
7 9
8 6

YES
4
9
5
3
12
13
10
11
15

Novosibirsk SU Contest #2, by Novosibirsk Team #1