给你一个有 $n$ 个顶点和 $m$ 条边的无向图，和一个整数 $k$。
请你找到一个大小为 $k$ 的团（称一个 $k$ 个点的集合为团，当且仅当点集大小为 $k$，并且该子集的每两个顶点之间存在一条边）或一个非空的顶点子集，使该子集的每个顶点在该子集中至少有 $k$ 个邻居。
输出方案。
对于每个测试用例：
- 如果找到一个合法点集，在第 $1$ 行输出 `1` 和子集的大小。在第 $2$ 行，以任意顺序输出子集的顶点。
- 如果找到一个大小为 $k$ 的团，那么在第 $1$ 行输出 `2`。第 $2$ 行中，以任意顺序输出该团的顶点。
- 如果没有所需的子集和集团，请输出 `-1`。
- 如果存在多个可能的答案，输出其中任意一个。
数据范围：$1 \le n, m, k \le 10^5$，$1 \le \sum n \le 2 \times 10^5$。
### Sol
首先如果 $k > \sqrt m$，那么一定无解。然后先把所有度数小于 $k - 1$ 的点删掉（要更新度数）。发现如果满足条件的团一定可以有一个点在当前的图中度数为 $k - 1$，不然我可以找到一个点集。对于所有当前度数为 $k - 1$ 的点，暴力枚举所有连出去的点，判断两两之间是否有连边，由于这样的点不超过 $\lfloor \frac mk \rfloor$ 个，使用 umap 可以使判定变为 $\mathcal{O}(1)$。这一部分的复杂度为 $\mathcal{O}(mk)$。然后删掉所有度数小于 $k$ 的点。如果这个时候，点集被变成了空集，此时就是无解的。如果还有剩下的点，则这些点构成一个合法的点集。然后删点的过程显然可以用一个类似于拓扑排序的东西解决。时间复杂度 $\mathcal{O}(m\sqrt m)$。
### Code
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int n, m, K;
int deg[100005], vis[100005], vse[100005];
vector<pii> e[100005];
queue<int> que;
unordered_map<int, int> mp[100005];
int tp, stk[100005];
int Work(int x) {
if ((int) mp[x].size() == K - 1) {
tp = 0;
for (auto i : mp[x])
stk[++tp] = i.first;
int mark = 1;
for (int i = 1; i <= tp && mark; i++)
for (int j = i + 1; j <= tp && mark; j++)
if (!mp[stk[i]].count(stk[j]))
mark = 0;
if (mark) {
printf("2\n%d ", x);
for (int i = 1; i <= tp; i++)
printf("%d%c", stk[i], " \n"[i == tp]);
return 1;
}
}
for (auto i : mp[x]) {
deg[i.first]--;
if (deg[i.first] == K - 1)
que.emplace(i.first);
mp[i.first].erase(x);
}
mp[x].clear(), deg[x] = 0;
return 0;
}
int ans[200005];
void Solve() {
for (int i = 1; i <= n; i++)
deg[i] = vis[i] = 0, e[i].clear(), mp[i].clear();
scanf("%d%d%d", &n, &m, &K);
for (int i = 1, u, v; i <= m; i++) {
scanf("%d%d", &u, &v);
e[u].emplace_back(v, i), e[v].emplace_back(u, i);
deg[u]++, deg[v]++;
}
if (K > ceil(sqrt(2 * m)))
return puts("-1"), void();
for (int i = 1; i <= n; i++)
if (deg[i] < K - 1)
que.emplace(i), vis[i] = 1;
while (!que.empty()) {
int u = que.front();
que.pop();
for (auto i : e[u]) {
int v = i.first, id = i.second;
if (vse[id])
continue;
vse[id] = 1;
deg[v]--;
if (deg[v] < K - 1 && !vis[v])
que.emplace(v), vis[v] = 1;
}
}
for (int i = 1; i <= n; i++)
for (auto j : e[i])
if (!vse[j.second])
mp[i][j.first] = 1;
for (int i = 1; i <= m; i++)
vse[i] = 0;
for (int i = 1; i <= n; i++)
if (deg[i] == K - 1)
que.emplace(i);
int mark = 0;
while (!que.empty()) {
int u = que.front();
que.pop();
if (!mark)
mark = Work(u);
}
if (mark)
return;
int aCnt = 0;
for (int i = 1; i <= n; i++)
if (deg[i] >= K)
ans[++aCnt] = i;
if (!aCnt)
return puts("-1"), void();
printf("1 %d\n", aCnt);
for (int i = 1; i <= aCnt; i++)
printf("%d%c", ans[i], " \n"[i == aCnt]);
}
int main() {
int T;
scanf("%d", &T);
while (T--)
Solve();
return 0;
}
```