CF1439B Graph Subset Problem

给定一个无向图，包含 $n$ 个顶点和 $m$ 条边。同时，给定一个整数 $k$。 请你找到以下两种情况之一： 1. 一个大小为 $k$ 的团（clique），即该子集内任意两点之间都有边相连。 2. 一个非空顶点子集，使得该子集内每个顶点在该子集内至少有 $k$ 个邻居。 如果不存在上述两种情况，请输出无解。 一个大小为 $k$ 的顶点子集被称为团（clique），如果该子集的大小为 $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 \times 10^5$。

对于每个测试用例： - 如果你找到了一个顶点子集，使得该子集内每个顶点在该子集内至少有 $k$ 个邻居，则第一行输出 $1$ 和该子集的大小，第二行输出该子集的所有顶点（顺序任意）。 - 如果你找到了一个大小为 $k$ 的团，则第一行输出 $2$，第二行输出该团的所有顶点（顺序任意）。 - 如果不存在满足条件的子集或团，输出 $-1$。 如果存在多种答案，可以输出任意一种。

在第一个测试用例中：子集 $\{1, 2, 3, 4\}$ 是一个大小为 $4$ 的团。 在第二个测试用例中：原图中每个顶点的度数至少为 $3$，因此所有顶点组成的集合就是一个合法答案。 在第三个测试用例中：不存在大小为 $4$ 的团或满足条件的子集，因此答案为 $-1$。 由 ChatGPT 4.1 翻译