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

Турниры > CEN303_2016Questions > задача:


HW082. 50699 - Fighting Vampires

CEN303_2016Questions

Старт: 28.окт.2016 в 17:00:00
Финиш: 01.ноя.2016 в 05:00:00
Турнир завершён!
• Турнирная таблица

Гость
• Вопросы к жюри (1)

Задачи турнира

• HW033. 50925 - Optimizing Elevator...
• HW051. 51019 - Finding the hidden...
• HW052. 51020 - Number of nodes r...
• HW061. 50448 - Paint Buckets
• HW062. 51021 - Number of Nodes
• HW071. 51042 - The most frequent ...
• HW072. 51043 - Genome Sequencing
• HW081. 51044 - Number of Trees
• HW082. 50699 - Fighting Vampires
• HW083. 50671 - Phalanx
• HW091. 51061 - The Longest Path
• HW101. 50682 - Hotel Durres
• HW102. 51067 - Jumping frog
• HW111. 50506 - The Biggest Island
• HW112. 50698 - Ayran Delivery
• PE11. 51023 - Preparing Keyword I...
• PE12. 50835 - Club Presidency

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

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

Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
IMPC 2014-15- Ind_04-40.

Fighting Vampires

In Dajti mountain, there are some vampires living and some of them are fighting each other. As a volunteer, Lady Gaga is planning to gather all vampires together to reconcile the fighting pairs. For this purpose, she would like to arrange a dinner program and invite all of them in order to settle the peace.

Before dinner, Ms. Gaga firstly tries to divide the visitors in different groups. Each group will have the dinner on a separate table. And in each group there should not be any fighting pair of vampires. As it is clear, if there are any fighting vampires in the same table, the peace process can be cancelled on the start.

Question: Your task is to help Lady Gaga in arranging tables for the dinner. Every vampire is sited on the first table that it doesn't have any other vampire fighting.

Input specification: In first line, the first integer is the total number of vampires, N (1 ≤ N ≤ 4,000). The second integer M (0 ≤ M ≤ 5,000) is the number of pairs that are enemy vampires to each other. In the following M lines, you will be given two integers (fighting vampires). Assume that the guests are numbered from 1 to N.

Output specification
Show two information: 1) the number of guests on the biggest table 2) the guests in that table in increasing order. Note: Show the first table, if there are several tables with the same max value.

Sample Input I
11 9
1 2
3 4
5 1
4 6
7 8
9 10
11 9
1 3
6 8
Sample Output I
6
2 3 5 6 10 11

Explanation:
There are 11 guests and 9 pairs of fighting vampires. There are three tables

  • Table 1: 1 4 7 9
  • Table 2: 2 3 5 6 10 11
  • Table 3: 8


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

www.contester.ru