HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Graph problems and UF > problem:


50699 - Fighting Vampires

Guest
• Review clarifications (1)

Section problems

• 50692 - How much money?
• 50694 - The Cheapest Flight
• 50841 - My grand-grand-grandfather
• 50697 - Base Stations
• 50695 - Longest link between neurons
• 50414 - Traffic
• 50698 - Ayran Delivery
• 50978 - Albanian Coders
• 50699 - Fighting Vampires
• 50857 - Nine-Stones Game
• 50929 - Present from your uncles
• 51076 - Key person
• 51080 - Deepest Point
• 51079 - Key person - 2
• 50464 - From Tirana to Durres
• 50691 - The traveling salesman prob...
• 50701 - Cell Removal

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.
Question by Faruk Bulut.

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