#P17728. [2026年福建省队集训]动态图连通性问题 2

[2026年福建省队集训]动态图连通性问题 2

题目描述

小 η\eta 最近学习了动态图完全连通性,对于给定的无向图 G=(V,E)G=(V,E),称节点 x,yx,y 是可达的当且仅当存在有限长度顶点序列 p=(p1,p2,⋯ ,pm)p=(p_1,p_2,\cdots,p_m),使得 p1=x,pm=yp_1=x,p_m=y 且对于 1≤i<m1\le i<m 均有边 (pi,pi+1)∈E(p_i,p_{i+1})\in E。特别的,当 x=yx=y 时总有 x,yx,y 可达。

有一张由 nn 个节点构成的无向图 GG,节点编号依次为 1,2,⋯ ,n1,2,\cdots,n,初始时(时刻 00)图中没有无向边,即 V={1,2,⋯ ,n},E=∅V=\{1,2,\cdots,n\},E=\varnothing。

接下来会发生 mm 次变化,对于每个整数 0≤i<m0\le i<m,在时刻 i+0.5i+0.5,有一个非空边集 EiE_i 的存在状态会被同时翻转。具体而言,对于每条边 (u,v)∈Ei(u,v)\in E_i:

  • 若在变化前 (u,v)(u,v) 不在图中,则将其加入图中;
  • 若在变化前 (u,v)(u,v) 已经在图中,则将其从图中删除。

小 η\eta 只关心整数时刻 0,1,⋯ ,m0,1,\cdots,m 时刻的图,小 η\eta 希望回答 qq 次询问,每次询问为给定三个整数 x,l,rx,l,r,小 η\eta 希望你帮忙计算出有多少个节点 yy 满足对于任意 l≤t≤rl\le t\le r,在时刻 tt 的图中,点 xx 与点 yy 均连通。

输入格式

本题有多组测试数据。输入的第一行两个整数 c,Tc,T 表示测试点编号和测试数据组数,特别的,在样例输入中,c=0c=0。

对于每组测试数据:

  • 第一行三个整数 n,m,qn,m,q,分别表示图的节点数、变化次数和询问次数;
  • 接下来描述 mm 次变化。对于每个 0≤i<m0\le i<m,先输入一个正整数 kik_i,表示 ∣Ei∣|E_i|,接下来 kik_i 行每行两个正整数 u,vu,v,表示一条存在状态被反转的无向边;
  • 接下来 qq 行,每行三个整数 x,l,rx,l,r,表示一次询问。

输出格式

对于每次询问输出一行一个非负整数,表示满足条件的节点 yy 的数量。

样例

样例输入 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

对于第一组测试数据:

  • 时刻 00 时没有边;
  • 时刻 0.50.5 时 E0={(1,2)}E_0=\{(1,2)\},故时刻 11 时边集为 {(1,2)}\{(1,2)\};
  • 时刻 1.51.5 时 E1={(2,3)}E_1=\{(2,3)\},故时刻 22 时边集为 {(1,2),(2,3)}\{(1,2),(2,3)\};
  • 时刻 2.52.5 时 E2={(1,2)}E_2=\{(1,2)\},故时刻 33 时边集为 {(2,3)}\{(2,3)\}。

因此,对询问 x=1,l=1,r=2x=1,l=1,r=2,节点 11 与节点 22 在时刻 1,21,2 均连通,而节点 33 只在时刻 22 与节点 11 连通,故答案为 22(符合条件的节点为 1,21,2)。

数据范围与提示

记 SS 为一个测试点内单组测试数据的 ∑i=0m−1ki\sum\limits_{i=0}^{m-1} k_i。对于所有测试数据:

  • 1≤T≤51\le T\le 5;
  • 2≤n≤1052\le n\le 10^5;
  • 1≤m≤S≤1051\le m\le S\le 10^5;
  • 1≤q≤3×1051\le q\le 3\times 10^5;
  • 1≤u,v≤n1\le u,v\le n,u≠vu\neq v,并保证同一个边集 EiE_i 中不会出现相同的无向边;
  • 1≤x≤n1\le x\le n;
  • 0≤l≤r≤m0\le l\le r\le m。
测试点编号 n≤n\le m≤m\le S≤S\le q≤q\le 特殊性质
1∼21\sim 2 55 无
3∼43\sim 4 100100
5∼75\sim 7 10510^5 10510^5 3×1053\times 10^5 A
8∼118\sim 11 B
12∼1312\sim 13 100100 无
1414 10510^5 500500 100100
15∼1615\sim 16 10510^5
1717 50005000
18∼1918\sim 19 10510^5 50005000
20∼2120\sim 21 5×1045\times10^4 10510^5
22∼2322\sim 23 8×1048\times10^4 2×1052\times 10^5
24∼2524\sim 25 10510^5 3×1053\times 10^5
  • 特殊性质 A:对于每次询问,均有 l=rl=r;
  • 特殊性质 B:对于每条输入的边,均有 v=u+1v=u+1。

【提示】

请注意本题特别的时空限制。