3062. rxms 喜欢玩耍

单点时限: 10.0 sec

内存限制: 256 MB

rxms 喜欢玩耍,她有一棵 个节点的树,节点编号为 。她提出这样 次询问,每次给定一个区间 ,求编号在 之间的节点形成多少个连通块。

输入格式

第一行为测试数据组数

对每一组数据,第一行为 表示节点个数, 表示询问次数。

接下来 行每行有两个整数 ,表示 间有一条边相连。

接下来 行每行有两个数 表示询问节点编号为区间 的连通块个数。

输出格式

对于每组数据,先输出一行 Case #X:,其中 X 表示第几组数据,再输出 行,其中第 行表示该组数据中的第 次询问的连通块个数。

样例

Input
2
3 2
1 2
1 3
1 2
2 3
5 3
1 2
1 3
2 4
2 5
1 4
2 5
3 5
Output
Case #1:
1
2
Case #2:
1
2
3

2 人解决,2 人已尝试。

3 份提交通过,共有 5 份提交。

8.0 EMB 奖励。

创建: 4 年,8 月前.

修改: 2 年,5 月前.

最后提交: 2 年,5 月前.

来源: 第四届程序设计竞赛

题目标签