<PREV Problem:
Solved by 95 users: ...

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 =