C. Паросочетание vs независимое множество
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан неориентированный граф, состоящий из $$$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$$$, то вы можете вывести любое из таких паросочетаний или любое из таких независимых множеств.

Пример
Входные данные
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
Выходные данные
Matching
2
IndSet
1
IndSet
2 4
Matching
1 15
Примечание

Первые два графа из примера совпадают, однако в этом графе есть как паросочетание размера 1, так и независимое множество размера 1. Любое из таких паросочетаний и независимых множеств является правильным ответом.

В третьем графе нет паросочетания размера 2, однако есть независимое множество размера 2. В этом графе также есть независимое множество размера 5: 2 3 4 5 6. Тем не менее, такой ответ не является верным, потому что вас просят найти независимое множество (или паросочетание) размера ровно $$$n$$$.

В четвёртом графе нет независимого множества размера 2, однако есть паросочетание размера 2.