Feedback | If you notice incorrect translations in Contester, please let author know.
|
|
Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb. Автор: Павел Кузнецов, ПГУ.
Difficulty Delta
There was a hot discussion in the parliament of Byteland after another
default. The deputies did not hesitate to use strong language. However
the whole procedure was closely watched by the Speaker. On the one hand,
he never deprived any of the opponents of the right to express their views,
but on the other hand, he immediately switched off the microphone as soon
as the participant of the debate happened to insult someone. So, each
deputy had his word at the session (total number of deputies is N), and
none of them insulted more than one of their colleagues. On completion of
the first reading, the Speaker faced the task of splitting the deputies
into groups to let them have their dinner break. The only requirement was
to exclude the presence of two deputies (the insulting and the insulted
ones) in the same group. And, of course, the Speaker was interested in
minimizing the number of the groups to make the dinner break period shorter.
Your task is to make a program that, using the log of the session, will
split all the deputies into as few groups as possible, considering the
above condition. Each deputy should be given the number of the group he/she
must be referred to.
Input
The first line of the input contains integers N and K
(2 ≤ N ≤ 1000; 0 ≤ K ≤ N). N
is the quantity of the deputies, K is the quantity of the
insults during the parliament readings. Next there should be K
lines describing the insults. Each insult is assigned two integers
X and Y meaning that the deputy with the number X
insulted the deputy with the number Y. We admit that all the
deputies are given numbers from 1 to N. It is provided that
1 ≤ X, Y ≤ N and X <> Y
in each insult. Besides, the list of insults is sure to have no repetitions.
Output
The first line of the output should contain the minimum quantity of
groups the deputies can be split into. The following N lines
should contain one number of the group the given deputy is to be referred
to. If the total number of groups turns out to be M, they must be
numbered from 1 to M. If there are several answers, choose any
of them to write.
Input 1
|
Output 1
|
Figure 1
|
4 3
2 1
3 1
4 3
|
2
1
2
2
1
|
|
The drawing illustrates the example. The insults are shown by
arrows. It is evident that in the given case the deputies can be
split into two groups, one of them will include the deputies numbered
1 and 4, the other will include numbers 2 and 3.
Для отправки решений необходимо выполнить вход.
|