|
Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб. Автор: Павел Кузнецов, ПГУ. Сложность Дельта 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.
Для отправки решений необходимо выполнить вход. |