CDOWN - Countdown

Ann Sister owns a genealogical database service, which maintains family tree history for her clients. When clients login to the system, they are presented with a variety of services: searching, printing, querying, etc. One recent question that came up which the system was not quite prepared for was the following: “Which member of my family had the most grandchildren?” The client who posed this question eventually had to answer it by manually searching the family tree database herself. Ann decided to have software written in case this question (or ones similar to it asking for great-grandchildren, or great-great-grandchildren, etc.) is asked in the future.

Input

Input will consist of multiple test cases. The first line of the input will contain a single integer indicating the number of test cases. Each test case starts with a single line containing two positive integers n and d, where n indicates the number of lines to follow containing information about the family tree, and d indicates the specific question being asked about the tree: if d = 1, then we are interested in persons with the most children (1 generation away); if d = 2, then we are interested in persons with the most grandchildren (2 generations away), and so on. The next n lines are of the form

name m dname1 dname2 ... dnamem

where name is one of the family members’ names, m is the number of his/her children, and dname1 through dnamem are the names of the children. These lines will be given in no particular order. You may assume that all n lines describe one single, connected tree. There will be no more than 1000 people in any one tree, and all names will be at most 10 characters long.

Output

For each test case, output the three names with the largest number of specified descendants in order of number of descendants. If there are ties, output the names within the tie in alphabetical order. Print fewer than three names if there are fewer than three people who match the problem criteria (you should not print anyone’s name who has 0 of the specified descendants), and print more than three if there is a tie near the bottom of the list. Print each name one per line, followed by a single space and then the number of specified descendants. The output for each test case should start with the line

Tree i:

where i is the test case number (starting at 1). Separate the output for each problem with a blank line.

Example

Input:
3
8 2
Barney 2 Fred Ginger
Ingrid 1 Nolan
Cindy 1 Hal
Jeff 2 Oliva Peter
Don 2 Ingrid Jeff
Fred 1 Kathy
Andrea 4 Barney Cindy Don Eloise
Hal 2 Lionel Mary
6 1
Phillip 5 Jim Phil Jane Joe Paul
Jim 1 Jimmy
Phil 1 Philly
Jane 1 Janey
Joe 1 Joey
Paul 1 Pauly
6 2
Phillip 5 Jim Phil Jane Joe Paul
Jim 1 Jimmy
Phil 1 Philly
Jane 1 Janey
Joe 1 Joey
Paul 1 Pauly

Output:
Tree 1:
Andrea 5
Don 3
Cindy 2

Tree 2:
Phillip 5
Jane 1
Jim 1
Joe 1
Paul 1
Phil 1

Tree 3:
Phillip 5

Added by:Camilo Andrés Varela León
Date:2007-07-26
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:East Central North America 2005

hide comments
2019-03-28 09:42:15
Why don't they provide more test cases? I am getting NZEC error.
2018-03-12 19:11:18
Change the sample output for the god sake!!
2017-06-29 05:15:10
that sucks

Last edit: 2017-06-29 05:15:36
2017-02-19 14:49:00
my 100'th
2014-12-20 09:13:20 Deepak Gupta
Remember n is number of lines to follow,not the total number of people.
2013-04-03 01:41:21 Tarun Gehlaut
@Camilo Andrés Varela León: please correct the sample output and add a blank line after every test case. Its quite confusing
2012-10-27 23:05:56 Rishav Raushan
sir, my code runs fine at my compiler and adheres strictly to the output format you've prescribed. but spoj says the code to be "wrong answer".
please, let me know if there are any intricacies involved with the blank lines pertaining to the o/p format u talk about.
2010-01-01 11:47:15 Sudhakar
First paragraph in the output is more important. Especially only names of persons having top three descendants. (if more than three names)


Last edit: 2010-01-01 11:47:33
2009-05-22 10:28:13 .:: Pratik ::.
notes about this problem.
You must print the blank line, even though it's not shown in the problem statement.

You may also find this useful.
If you are printing a lower number of ancestors, then you must only print it given that you have printed less than 3 lines before in that case.
Hope it's not too confusing :P
2009-03-07 13:26:12 Paul Draper
The example is not separated by blank lines?

Last edit: 2009-03-07 13:26:12
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.