2145 - 小东东发微博

题目描述

500 次啊,500 次啊~

小东东一默念着一边想着“到底要不要发微博了呢?”自从出台了有关微博转发 500 次就要...

哎!这正是现在小东东苦恼的事情。小东东想着有那么多的死党关注了自己,而且每个死党还有很多粉丝。如果每个死党和他的粉丝们都转发一次自己的微博,500 次以后估计什么也都说不清了。现在他决定一个一个的查看过去,看看自己的一条微博到底会被转发多少次。可是想想自己死党那么多,他又懒的不想动于是把这个任务交给你了,现在请你用程序帮帮他的忙。

输入

第一行一个整数 T 表示有 T 组测试数据(T \le 20),接下来的一行包含两个整数 NIDN 表示接下来有 N 个关系(N \le 100000),ID 是小东东的微博编号。

紧接着的 N 行每行两个整数 AB ,表示编号为 A 的同学关注了编号为 B 的同学(也就是 AB 的粉丝)。

每个人微博的编号在 [1,10000] 内。

输出

请根据上述的粉丝关系,计算小东东的一条微博最多会被转发多少次。(请注意输出格式,输出的冒号后有一个空格)

样例

输入

2
14 1
2 1
3 1
4 1
6 1
3 2
4 2
3 4
3 5
4 5
6 5
4 6
5 6
4 7
6 7
4 4
1 2
2 3
3 4
4 1

输出

Case #1: 5
Case #2: 3
说明

如果 A 关注了 BAB 的粉丝),那么 B 发送的每条微博 A 都会转发,相同的微博每个人只发一次。

来源

图论

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 0
通过人数 0
金币数量 1 枚
难度 入门


上一题 下一题