<ПРЕД Задача:
СЛЕД>
Задачу решили 95 пользователей: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Стабильный коллектив

Time limit = 2 секунд(ы)

В фирме OAO "Новый Софт" работа совсем не идёт, фирма несёт убытки, а всё из-за того, что рабочий коллектив не дружен, а правильные отношения не налажены.

Директор фирмы, Пётр Новиков, решил принять радикальные меры, а именно, уволить часть сотрудников, чтобы остался максимально стабильный коллектив.

Для начала, необходимо выяснить, кто с кем дружит (известно, что дружба всегда взаимна). Затем, на основании этих данных найти коллектив (непустое подмножество сотрудников) с максимальной стабильностью.

Стабильность коллектива A определяется слабым звеном. Слабое звено коллектива A — это человек, у которого меньше всего друзей в коллективе A. Число друзей у слабого звена и есть стабильность коллектива.

Да, и ещё — Петр Новиков хотел бы остаться работать в фирме и себя он увольнять не собирается, хотя, в принципе, он может быть слабым звеном. Известно, что у Петра Новикова есть друзья среди своих сотрудников.

Помогите Петру и напишите программу, которая среди коллективов, в которых он есть, находит коллектив с максимальной стаблильностью. Седи возможных коллективов, удовлетворяющих этому свойству, найдите тот, у которого максимальный размер. Если таких коллективов несколько, то найдите один из возможных.

Вход. В первой строке дано количество M дружных пар, 0 < M < 40000. Затем идёт M строчек, в каждой из которых даны два разных имени, разделённые пробелом. Имена сотрудников записаны латинскими символами и имеют длину менее 32 символов. Имя Петра Новикова записано как Petr. Общее число сотрудников не превосходит 7000. Первая буква любого имени заглавная, а остальные маленькие.

Выход.

В первой строке укажите размер самого стабильного коллектива, в котором есть Пётр, а затем, через пробел, его стабильность. Во второй строке приведите список имён людей, которые вошли в этот коллектив, в лексикографическом порядке.

Вход#1
8
Petr Vasya
Petr Kolya
Sergey Max
Petr Lena
Lena Vasya
Lena Kolya
Vasya Kolya
Sergey Lena
Выход#1
4 3
Kolya Lena Petr Vasya

Автор:
Ворожцов Артем, ACM ICPC Moscow Subregion, октябрь 2006 года (расширенный набор тестов и другие ограничения на входные данные)
22 октября 2006

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 200ms

SW soft NIX
ID = 54.161.116.225