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