Лимит времени 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
Для отправки решений необходимо выполнить вход.
|