描述

Ann Sister 拥有一个族谱数据库服务，维护客户的家谱历史。当客户登录系统时，会提供搜索、打印、查询等多种服务。最近出现了一个系统尚不能直接回答的问题：“我家族中哪个成员拥有最多的孙辈？”提出该问题的客户不得不手动查询数据库后得到答案。Ann 决定编写软件，以便将来类似（曾孙、玄孙等）问题可以自动回答。

输入

输入包含多组测试。第一行包含一个整数，表示测试用例数量。每个测试用例先给出一行两个正整数 $n$ 和 $d$，其中 $n$ 是随后描述家谱信息的行数，$d$ 表示要查询的后代世代：$d=1$ 时询问子女数（1 代）；$d=2$ 时询问孙辈数（2 代）；以此类推。接下来的 $n$ 行格式为 name m dname1 dname2 ... dnamem，其中 name 是成员姓名，m 是其子女数，dname1~dnamem 是其子女姓名。行序无特定顺序。可假设所有 $n$ 行描述的是同一棵连通树。任一树中人员不超过 1000 人，姓名长度不超过 10 个字符。

输出

对于每个测试用例，按后代数量从多到少输出前 3 名姓名及数量，一人一行，格式为“姓名 数量”。若出现名次并列，则并列内按字母顺序输出。若符合条件的人数不足 3 人，则只输出所有数量大于 0 的人员；若第三名多人并列，则都输出。每个测试用例输出前先打印“Tree i:”，其中 i 为测试序号（从 1 开始）。测试用例间以空行分隔。

输入数据 1

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

输出数据 1

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

来源

East Central North America 2005