CF1198C.Matching vs Independent Set

You are given a graph with $3 \cdot n$ vertices and $m$ edges. You are to find a matching of $n$ edges, or an independent set of $n$ vertices.

A set of edges is called a matching if no two edges share an endpoint.

A set of vertices is called an independent set if no two vertices are connected with an edge.

给你一个包含 $3 \cdot n$ 个顶点和 $m$ 条边的图。你需要找出一个包含 $n$ 条边的匹配，或一个包含 $n$ 个顶点的独立集。

若一组边中任意两条边均不共享端点，则称该边集为一个匹配。

若一组顶点中任意两个顶点之间均无边相连，则称该顶点集为一个独立集。

The first line contains a single integer $T \ge 1$ — the number of graphs you need to process. The description of $T$ graphs follows.

The first line of description of a single graph contains two integers $n$ and $m$, where $3 \cdot n$ is the number of vertices, and $m$ is the number of edges in the graph ($1 \leq n \leq 10^{5}$, $0 \leq m \leq 5 \cdot 10^{5}$).

Each of the next $m$ lines contains two integers $v_i$ and $u_i$ ($1 \leq v_i, u_i \leq 3 \cdot n$), meaning that there is an edge between vertices $v_i$ and $u_i$.

It is guaranteed that there are no self-loops and no multiple edges in the graph.

It is guaranteed that the sum of all $n$ over all graphs in a single test does not exceed $10^{5}$, and the sum of all $m$ over all graphs in a single test does not exceed $5 \cdot 10^{5}$.

第一行包含一个整数 $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}$。

Print your answer for each of the $T$ graphs. Output your answer for a single graph in the following format.

If you found a matching of size $n$, on the first line print "Matching" (without quotes), and on the second line print $n$ integers — the indices of the edges in the matching. The edges are numbered from $1$ to $m$ in the input order.

If you found an independent set of size $n$, on the first line print "IndSet" (without quotes), and on the second line print $n$ integers — the indices of the vertices in the independent set.

If there is no matching and no independent set of the specified size, print "Impossible" (without quotes).

You can print edges and vertices in any order.

If there are several solutions, print any. In particular, if there are both a matching of size $n$, and an independent set of size $n$, then you should print exactly one of such matchings or exactly one of such independent sets.

对每个图输出你的答案。单个图的答案按以下格式输出：

• 如果你找到了一个大小为 $n$ 的匹配，在第一行输出 "Matching"（不带引号），在第二行输出 $n$ 个整数——即该匹配中各边的编号。边按输入顺序从 $1$ 到 $m$ 编号。
• 如果你找到了一个大小为 $n$ 的独立集，在第一行输出 "IndSet"（不带引号），在第二行输出 $n$ 个整数——即该独立集中各顶点的编号。
• 如果既不存在大小为 $n$ 的匹配，也不存在大小为 $n$ 的独立集，则输出 "Impossible"（不带引号）。

边和顶点的输出顺序可以任意。

若存在多个解，输出任意一个即可。特别地，若同时存在大小为 $n$ 的匹配和大小为 $n$ 的独立集，则你只需输出其中某一个匹配或某一个独立集。

The first two graphs are same, and there are both a matching of size 1 and an independent set of size 1. Any of these matchings and independent sets is a correct answer.

The third graph does not have a matching of size 2, however, there is an independent set of size 2. Moreover, there is an independent set of size 5: 2 3 4 5 6. However such answer is not correct, because you are asked to find an independent set (or matching) of size exactly $n$.

The fourth graph does not have an independent set of size 2, but there is a matching of size 2.

前两张图是相同的，它们都存在大小为 1 的匹配和大小为 1 的独立集。任意一个这样的匹配或独立集都是正确答案。

第三张图不存在大小为 2 的匹配，但存在大小为 2 的独立集。此外，还存在大小为 5 的独立集：2 3 4 5 6。但该答案不正确，因为题目要求你找出大小恰好为 $n$ 的独立集（或匹配）。

第四张图不存在大小为 2 的独立集，但存在大小为 2 的匹配。