ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Сборники > Kovrov IT 2007 > задача:

F. Parliament

Задачи сборника

• A. Phalanx
• B. Bitsorting
• C. Cubes
• D. Factorial
• E. Lights
• F. Parliament
• G. Strange Numbers
• H. Two Captains
• I. Boundary Troops
• J. Wedding

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 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.

The first line of the input contains integers N and K (2 ≤ N ≤ 1000; 0 ≤ KN). 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, YN and X <> Y in each insult. Besides, the list of insults is sure to have no repetitions.
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

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.

Для отправки решений необходимо выполнить вход.