CF1198C Matching vs Independent Set

给定一个包含 $3 \cdot n$ 个顶点和 $m$ 条边的图。你需要找到一个大小为 $n$ 的匹配，或者一个大小为 $n$ 的独立集。 一组边称为匹配，当且仅当任意两条边没有公共端点。 一组顶点称为独立集，当且仅当任意两点之间都没有边相连。

第一行包含一个整数 $T \ge 1$，表示你需要处理的图的数量。接下来是 $T$ 个图的描述。 每个图的描述的第一行包含两个整数 $n$ 和 $m$，其中 $3 \cdot n$ 是该图的顶点数，$m$ 是该图的边数（$1 \leq n \leq 10^{5}$，$0 \leq m \leq 5 \cdot 10^{5}$）。 接下来的 $m$ 行，每行包含两个整数 $v_i$ 和 $u_i$（$1 \leq v_i, u_i \leq 3 \cdot n$），表示在顶点 $v_i$ 和 $u_i$ 之间有一条边。 保证图中没有自环和重边。 保证所有图中 $n$ 的总和不超过 $10^{5}$，所有图中 $m$ 的总和不超过 $5 \cdot 10^{5}$。

对于每个图，输出一组答案。 如果你找到了一个大小为 $n$ 的匹配，第一行输出 "Matching"（不带引号），第二行输出 $n$ 个整数，表示匹配中边的编号。边按输入顺序编号，从 $1$ 到 $m$。 如果你找到了一个大小为 $n$ 的独立集，第一行输出 "IndSet"（不带引号），第二行输出 $n$ 个整数，表示独立集中的顶点编号。 如果既没有大小为 $n$ 的匹配，也没有大小为 $n$ 的独立集，输出 "Impossible"（不带引号）。 边和顶点的输出顺序可以任意。 如果有多组解，输出任意一组即可。特别地，如果既存在大小为 $n$ 的匹配，也存在大小为 $n$ 的独立集，则你只需输出其中一种方案。

前两个图是相同的，既存在大小为 $1$ 的匹配，也存在大小为 $1$ 的独立集。任意一种匹配或独立集都是正确答案。 第三个图不存在大小为 $2$ 的匹配，但存在大小为 $2$ 的独立集。实际上还存在大小为 $5$ 的独立集：2 3 4 5 6。但这样的答案不正确，因为题目要求找到恰好大小为 $n$ 的独立集（或匹配）。 第四个图不存在大小为 $2$ 的独立集，但存在大小为 $2$ 的匹配。 由 ChatGPT 4.1 翻译