← 返回题目列表

Codeforces · 1198/C

C. 匹配与独立集

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

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

输出

打印出每个 $$$T$$$ 图表的答案。按以下格式输出单个图表的答案。

如果您发现大小为 $$$n$$$ 的匹配,请在第一行打印“Matching”(不带引号),并在第二行打印 $$$n$$$ 整数 - 匹配中边缘的索引。边按照输入顺序从 $$$1$$$ 到 $$$m$$$ 编号。

如果您找到大小为 $$$n$$$ 的独立集合,请在第一行打印“IndSet”(不带引号),并在第二行打印 $$$n$$$ 整数 - 独立集合中顶点的索引。

如果没有匹配且没有指定大小的独立集,则打印“Impossible”(不带引号)。

您可以按任意顺序打印边和顶点。

如果有多个解决方案,请打印其中一个。特别是,如果同时存在大小为 $$$n$$$ 的匹配和大小为 $$$n$$$ 的独立集合,那么您应该精确打印其中一个此类匹配或恰好一个此类独立集合。

示例

输入 #1

4
1 2
1 3
1 2
1 2
1 3
1 2
2 5
1 2
3 1
1 4
5 1
1 6
2 15
1 2
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
3 4
3 5
3 6
4 5
4 6
5 6

输出 #1

Matching
2
IndSet
1
IndSet
2 4
Matching
1 15

注意

前两张图是相同的,并且都有大小为 1 的匹配和大小为 1 的独立集。这些匹配和独立集中的任何一个都是正确答案。

第三张图没有尺寸 2 的匹配,但是,有一个独立的尺寸 2 的集合。此外,还有一个独立的尺寸 5 的集合: 2 3 4 5 6。但是这样的答案是不正确的,因为你被要求找到一个独立的集合(或匹配)的尺寸恰好 $$$n$$$。

第四张图没有大小为2的独立集合,但有大小为2的匹配。