← 返回题目列表

Codeforces · 1439/B

B. 图子集问题

中文机器翻译题面 查看原题

给你一个无向图,其中有 $$$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$$$。