给您一个未加权、无向图 $$$G$$$,其中包含 $$$n$$$ 节点和 $$$m$$$ 边。图 $$$G$$$ 不包含自环或多重边。
我们将$$$G$$$的节点集表示为$$$V$$$。对于任意节点子集 $$$V' \subseteq V$$$,相应的导出子图用 $$$G[V']$$$ 表示,定义如下:
- $$$G[V']$$$ 是节点集为 $$$V'$$$ 的图,其边集由 $$$G$$$ 中的所有边组成,且两个端点都在 $$$V'$$$ 中。
您的任务是回答 $$$q$$$ 查询。每个查询提供三个整数$$$l$$$、$$$r$$$ 和$$$k$$$。表示$$$V'=\{l,l+1,\ldots,r\}$$$,你需要找到$$$f(l,G[V'])$$$, $$$f(l+1,G[V'])$$$, $$$\ldots$$$ , $$$f(r,G[V'])$$$中的第$$$k$$$个最小值(即按升序排列的第 $$$k$$$ 个值;重复的值会被计算多次)。
这里,$$$f(u,G[V'])=\bigoplus_{(u,v)\in G[V']}v$$$。换句话说,它是图$$$G[V']$$$中节点$$$u$$$的所有相邻节点的标签的按位异或值。
您可能需要阅读注释以更好地理解。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1.5 \cdot 10^4$$$)。测试用例的描述如下。
每个测试用例都以两个整数 $$$n$$$ 和 $$$m$$$ 开头($$$2 \leq n \leq 1.5 \cdot 10^5$$$, $$$1 \leq m \leq 1.5 \cdot 10^5$$$)——分别是节点和边的数量。
接下来的 $$$m$$$ 行每行包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \neq v_i$$$),表示节点 $$$u_i$$$ 和 $$$v_i$$$ 之间的无向边。
下一行包含一个整数 $$$q$$$ ($$$1 \leq q \leq 1.5 \cdot 10^5$$$) — 查询数。
接下来的 $$$q$$$ 行包含三个整数 $$$l$$$、$$$r$$$ 和 $$$k$$$ ($$$1 \leq l \leq r \leq n$$$, $$$1 \le k \le r-l+1$$$),定义有关导出子图的查询$$$G[\{l,\ldots,r\}]$$$。
保证图不包含自环或重边。
保证所有测试用例的 $$$n$$$、$$$m$$$ 和 $$$q$$$ 之和分别不超过 $$$1.5 \cdot 10^5$$$。
输出
对于每个测试用例,输出 $$$q$$$ 整数,表示每个查询的答案。
示例
输入复制
24 51 31 42 32 43 431 2 21 3 12 4 32 12 131 1 12 2 11 2 2
输出复制
0 3 7 0 0 2
注意
在第一个测试用例中,输入图 $$$G$$$ 如下图所示。
给定的图表$$$G$$$。 在第一个查询中,导出子图 $$$G[\{1,2\}]$$$ 如下图所示。我们可以看到节点$$$1$$$和$$$2$$$没有相邻节点。因此,$$$f(1,G[\{1,2\}])=f(2,G[\{1,2\}])=0$$$。 $$$2$$$第一个最小值是$$$0$$$。
$$$G[\{1,2\}]$$$。 在第二个查询中,导出子图 $$$G[\{1,2,3\}]$$$ 如下图所示。我们可以看到 $$$f(1,G[\{1,2,3\}])=3$$$,$$$f(2,G[\{1,2,3\}])=3$$$,$$$f(3,G[\{1,2,3\}])=1 \oplus 2=3$$$。 $$$1$$$-st 最小值是 $$$3$$$。
$$$G[\{1,2,3\}]$$$。 在第三个查询中,导出子图 $$$G[\{2,3,4\}]$$$ 如下图所示。我们可以看到 $$$f(2,G[\{2,3,4\}])=3 \oplus 4=7$$$、$$$f(3,G[\{2,3,4\}])=2 \oplus 4=6$$$ 和 $$$f(4,G[\{2,3,4\}])=2 \oplus 3=1$$$。 $$$3$$$-rd 最小值是 $$$7$$$。
$$$G[\{2,3,4\}]$$$。