A30983.【图论】小未的粉丝

普及-

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

小未在微博上有不少朋友关注了自己,而且每个朋友还有很多粉丝。如果每个朋友和他的粉丝们,以及粉丝的粉丝,无论隔了多少层的粉丝,都转发一次自己的微博,他的微博就会被转发很多次了。现在他想知道自己的一条微博到底会被转发多少次。现在请你用程序帮帮他的忙。

输入格式

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

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


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

输出格式

请根据上述的粉丝关系,计算小未的一条微博最多会被转发多少次。

输入输出样例

  • 输入#1

    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

    输出#1

    Case #1: 5
    Case #2: 3

说明/提示

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

首页