<PREV Problem:
Solved by 95 users: ...
pav07 oct 2007Ruby904.47248 
pav08 oct 2007Ruby1004.30250 
Fat18 feb 2008Ruby1802.90370 
RAVEman11 jan 2009C++100.35374 
DAV11 jun 2009C++2100.35429 
tomek19 nov 2006C++200.45430 
DAV11 jun 2009C++1900.34435 
li0n05 sep 2011C++100.73453 
DAV10 jun 2009C++1800.34463 
dan02 may 2007C++200.77472 
Junk13 nov 2006C++1501.08478 
Lukasz16a29 jun 2008C++200.20508 
JohnJones_00125 oct 2006C++501.44509 

K-harmonious Workgroup

Time limit = 2 second(s)

Company "New Soft LTD" incurs losses and has almost stopped working because of the lack of friendly climate among its staff.

The company's CEO Petr Novikov has to take strong measures, and here's what he decided to do.

First he has to gather information about friendship relations among his employees. Then Petr will form the most harmonious workgroup from the company's staff. Others... others will have to be fired.

Harmonicity of a workgroup is defined by its weak link. A weak link of a workgroup A is an employee X from A having the least number of friends in A. The number of X's friends in A is called the harmonicity of A (clearly, this definition doesn't depend on the choice of X if there are several employees with the least number of friends).

Of course Petr can be a weak link too, but he is not going to fire himself. It is guaranteed that Petr has at least one friend among the staff.

You are to write a program that helps Petr to find a workgroup $B$ that has the greatest harmonicity among those containing himself. If there are several possible answers, find the one that has the greatest number of employees in it. If there are still several possible answers, output any.

Input. The first line contains integer M --- the total number of friendship relations among company's staff, 0 < M < 40000. M lines follow, each containing two nicknames of employees that are friends of each other, separated by a single space. Each nickname consists of uppercase and lowercase letters and its length is less than 32. Petr Novikov has nickname Petr. Nicknames of different employees differ. Company's staff size does not exceed 7000 employees.


The first line of output should contain the size of a workgroup B and its harmonicity K, separated by a space. The second line of output should contain the nicknames of employees from B, separated by spaces in lexicographical order.

Petr Vasya
Petr Kolya
Sergey Max
Petr Lena
Lena Vasya
Lena Kolya
Vasya Kolya
Sergey Lena
4 3
Kolya Lena Petr Vasya

Voroztsov Artem, ACM ICPC Moscow Subregion, October 2006 (with some changes in input data restrictions and extended test set)
22 October 2006

<PREV | Problem set | Search related messages | NEXT>

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

SW soft NIX
ID =