3062. rxms 喜欢玩耍

输入格式

第一行为测试数据组数 $T$。

对每一组数据，第一行为 $N,Q$ $(1\le N,Q\le {10}^5)$，$N$ 表示节点个数，$Q$ 表示询问次数。

接下来 $N-1$ 行每行有两个整数 $a,b$，表示 $a$ 跟 $b$ 间有一条边相连。

接下来 $Q$ 行每行有两个数 $L,R$ $(1\le L\le R\le N)$ 表示询问节点编号为区间 $[L,R]$ 的连通块个数。

输出格式

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

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

Case #1:
1
2
Case #2:
1
2
3