给你一个无向图,其中有 $$$n$$$ 个顶点和 $$$m$$$ 个边。 Also, you are given an integer $$$k$$$.
找到大小为 $$$k$$$ 的团或顶点的非空子集,使得该子集的每个顶点在子集中至少有 $$$k$$$ 邻居。如果没有这样的派系和子集,请报告此事。
如果顶点子集的大小为 $$$k$$$ 并且子集中的每两个顶点之间存在一条边,则该顶点子集称为大小为 $$$k$$$ 的团。如果一个顶点之间存在边,则该顶点称为另一个顶点的邻居。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — 测试用例的数量。接下来的几行包含测试用例的描述。
每个测试用例描述的第一行包含三个整数 $$$n$$$, $$$m$$$, $$$k$$$ ($$$1 \leq n, m, k \leq 10^5$$$, $$$k \leq n$$$)。
接下来的 $$$m$$$ 行包含两个整数 $$$u, v$$$ $$$(1 \leq u, v \leq n, u \neq v)$$$,表示顶点 $$$u$$$ 和 $$$v$$$ 之间的边。
保证不存在自环或多重边。保证所有测试用例的$$$n$$$总和以及所有测试用例的$$$m$$$总和不超过$$$2 \cdot 10^5$$$。
输出
对于每个测试用例:
如果您找到一个顶点子集,并且该子集的每个顶点在第一行输出的子集中至少有 $$$k$$$ 个邻居,则输出 $$$1$$$ 和子集的大小。在第二行以任意顺序输出子集的顶点。
如果您发现一个大小为 $$$k$$$ 的派系,则在第一行中输出 $$$2$$$ 并在第二行中以任意顺序输出该派系的顶点。
如果没有必需的子集和派系,则打印 $$$-1$$$。
如果存在多个可能的答案,您可以打印其中任何一个。
示例
输入 #1
3 5 9 4 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 10 15 3 1 2 2 3 3 4 4 5 5 1 1 7 2 8 3 9 4 10 5 6 7 10 10 8 8 6 6 9 9 7 4 5 4 1 2 2 3 3 4 4 1 1 3
输出 #1
2 4 1 2 3 1 10 1 2 3 4 5 6 7 8 9 10 -1
注意
在第一个测试用例中:子集 $$$\{1, 2, 3, 4\}$$$ 是一个大小为 $$$4$$$ 的派系。
在第二个测试用例中:原始图中每个顶点的度数至少为$$$3$$$。所以所有顶点的集合就是正确答案。
在第三个测试用例中:没有大小为 $$$4$$$ 的派系或所需子集,因此答案为 $$$-1$$$。