|Online MIPT programming contest||РУССКИЙ|
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.
8 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
© acm.mipt DevGroup
The page was generated in 210ms