题目描述
小 η 最近学习了动态图完全连通性,对于给定的无向图 G=(V,E),称节点 x,y 是可达的当且仅当存在有限长度顶点序列 p=(p1,p2,⋯,pm),使得 p1=x,pm=y 且对于 1≤i<m 均有边 (pi,pi+1)∈E。特别的,当 x=y 时总有 x,y 可达。
有一张由 n 个节点构成的无向图 G,节点编号依次为 1,2,⋯,n,初始时(时刻 0)图中没有无向边,即 V={1,2,⋯,n},E=∅。
接下来会发生 m 次变化,对于每个整数 0≤i<m,在时刻 i+0.5,有一个非空边集 Ei 的存在状态会被同时翻转。具体而言,对于每条边 (u,v)∈Ei:
- 若在变化前 (u,v) 不在图中,则将其加入图中;
- 若在变化前 (u,v) 已经在图中,则将其从图中删除。
小 η 只关心整数时刻 0,1,⋯,m 时刻的图,小 η 希望回答 q 次询问,每次询问为给定三个整数 x,l,r,小 η 希望你帮忙计算出有多少个节点 y 满足对于任意 l≤t≤r,在时刻 t 的图中,点 x 与点 y 均连通。
输入格式
本题有多组测试数据。输入的第一行两个整数 c,T 表示测试点编号和测试数据组数,特别的,在样例输入中,c=0。
对于每组测试数据:
- 第一行三个整数 n,m,q,分别表示图的节点数、变化次数和询问次数;
- 接下来描述 m 次变化。对于每个 0≤i<m,先输入一个正整数 ki,表示 ∣Ei∣,接下来 ki 行每行两个正整数 u,v,表示一条存在状态被反转的无向边;
- 接下来 q 行,每行三个整数 x,l,r,表示一次询问。
输出格式
对于每次询问输出一行一个非负整数,表示满足条件的节点 y 的数量。
样例
样例输入 1
0 2
4 3 4
1
1 2
1
2 3
1
1 2
1 0 0
1 1 2
3 2 3
4 0 3
5 4 4
2
1 2
4 5
1
2 3
2
1 2
2 3
1
3 4
1 1 2
2 2 3
4 1 4
3 0 4
样例输出 1
1
2
2
1
2
1
2
1
样例解释 1
对于第一组测试数据:
- 时刻 0 时没有边;
- 时刻 0.5 时 E0={(1,2)},故时刻 1 时边集为 {(1,2)};
- 时刻 1.5 时 E1={(2,3)},故时刻 2 时边集为 {(1,2),(2,3)};
- 时刻 2.5 时 E2={(1,2)},故时刻 3 时边集为 {(2,3)}。
因此,对询问 x=1,l=1,r=2,节点 1 与节点 2 在时刻 1,2 均连通,而节点 3 只在时刻 2 与节点 1 连通,故答案为 2(符合条件的节点为 1,2)。
数据范围与提示
记 S 为一个测试点内单组测试数据的 i=0∑m−1ki。对于所有测试数据:
- 1≤T≤5;
- 2≤n≤105;
- 1≤m≤S≤105;
- 1≤q≤3×105;
- 1≤u,v≤n,u=v,并保证同一个边集 Ei 中不会出现相同的无向边;
- 1≤x≤n;
- 0≤l≤r≤m。
| 测试点编号 |
n≤ |
m≤ |
S≤ |
q≤ |
特殊性质 |
| 1∼2 |
5 |
无 |
| 3∼4 |
100 |
| 5∼7 |
105 |
105 |
3×105 |
A |
| 8∼11 |
B |
| 12∼13 |
100 |
无 |
| 14 |
105 |
500 |
100 |
| 15∼16 |
105 |
| 17 |
5000 |
| 18∼19 |
105 |
5000 |
| 20∼21 |
5×104 |
105 |
| 22∼23 |
8×104 |
2×105 |
| 24∼25 |
105 |
3×105 |
- 特殊性质 A:对于每次询问,均有 l=r;
- 特殊性质 B:对于每条输入的边,均有 v=u+1。
【提示】
请注意本题特别的时空限制。