对于这个世界,我们人类知之甚少,实际上,这个世界远远没有我们想象的简单。
实际上,我们的世界是分周目的,我们当前存在的时空属于某个周目,而在另一个周目中有另一个你,虽然身份一样,但是每个周目世界的发展却是各自按照不同的轨迹发展的。
每个周目都有一个控制世界稳定运行的神,在整个世界进行到今天,每个周目世界的神都是 Zeus(宙斯)
Zeus:
Zeus已经控制了这个世界1024万年了,Zeus寿命将至,而每个周目世界不能没有控制世界的神,于是Zeus在寻找他的继承人。
Zeus需要找到一位强大的继承人,所以Zeus选择了 N 位候选人,这N 个候选人将要进行一场死亡游戏,最后生存的玩家将成为新的神。
为了游戏的正常运行,Zeus为每位玩家准备了一部有特殊预知未来功能的手机,叫做日记。
玩家们通过运用日记的预知功能互相杀死对方。
Zeus寿命剩余不多了,所以他希望尽快结束游戏,所以他希望所有人能尽快地找到其他玩家并杀害,这就需要玩家们能知道对方的线索。
玩家一 知道 玩家二的线索,并不代表玩家二也知道玩家一的线索,但是如果玩家一知道玩家二的线索,而玩家二知道玩家三的线索,那么玩家一也就知道了玩家三的线索。
现在N位玩家中存在M个线索,为了让游戏能公平地筛选出胜利者,Zeus需要对玩家们提供最少的线索,使得所有玩家能直接或间接地得知所有其他玩家的线索。请你帮Zeus计算一下最少需要为玩家们提供多少条线索能使游戏进行下去。
输入要求
第一行输入一个T(1<=T<=10)表示接下来有T组数据
每组数据的第一行输入一个 N (1<=N<= 10,000),和一个M(1 <= M <= 50,000),表示有N位候选人参加游戏 ,当前已存在M条线索。
接下来的M行每行输入两个值 ai,bi,表示玩家ai知道玩家bi的线索(1<= ai,bi <=N)
输出要求
每次输出占一行,样式为Case #i: ans,表示第i组测试数据答案为ans,表示需要为游戏添加 ans 条线索
测试数据输入示例1
3 2
1 2
2 3
输出示例Case #1: 1小贴士
对于样例 玩家 1 知道 玩家 2的线索,玩家2知道玩家3的线索,所以只需要给玩家3提供玩家1的线索即可使所有玩家得知所有人的线索,所以只需要提供一条线索
实际上,我们的世界是分周目的,我们当前存在的时空属于某个周目,而在另一个周目中有另一个你,虽然身份一样,但是每个周目世界的发展却是各自按照不同的轨迹发展的。
每个周目都有一个控制世界稳定运行的神,在整个世界进行到今天,每个周目世界的神都是 Zeus(宙斯)
Zeus:
Zeus已经控制了这个世界1024万年了,Zeus寿命将至,而每个周目世界不能没有控制世界的神,于是Zeus在寻找他的继承人。
Zeus需要找到一位强大的继承人,所以Zeus选择了 N 位候选人,这N 个候选人将要进行一场死亡游戏,最后生存的玩家将成为新的神。
为了游戏的正常运行,Zeus为每位玩家准备了一部有特殊预知未来功能的手机,叫做日记。
玩家们通过运用日记的预知功能互相杀死对方。
Zeus寿命剩余不多了,所以他希望尽快结束游戏,所以他希望所有人能尽快地找到其他玩家并杀害,这就需要玩家们能知道对方的线索。
玩家一 知道 玩家二的线索,并不代表玩家二也知道玩家一的线索,但是如果玩家一知道玩家二的线索,而玩家二知道玩家三的线索,那么玩家一也就知道了玩家三的线索。
现在N位玩家中存在M个线索,为了让游戏能公平地筛选出胜利者,Zeus需要对玩家们提供最少的线索,使得所有玩家能直接或间接地得知所有其他玩家的线索。请你帮Zeus计算一下最少需要为玩家们提供多少条线索能使游戏进行下去。
输入要求
第一行输入一个T(1<=T<=10)表示接下来有T组数据
每组数据的第一行输入一个 N (1<=N<= 10,000),和一个M(1 <= M <= 50,000),表示有N位候选人参加游戏 ,当前已存在M条线索。
接下来的M行每行输入两个值 ai,bi,表示玩家ai知道玩家bi的线索(1<= ai,bi <=N)
输出要求
每次输出占一行,样式为Case #i: ans,表示第i组测试数据答案为ans,表示需要为游戏添加 ans 条线索
测试数据输入示例1
3 2
1 2
2 3
输出示例Case #1: 1小贴士
对于样例 玩家 1 知道 玩家 2的线索,玩家2知道玩家3的线索,所以只需要给玩家3提供玩家1的线索即可使所有玩家得知所有人的线索,所以只需要提供一条线索