Дан неориентированный граф, состоящий из \(3 \cdot n\) вершин и \(m\) ребер. Требуется найти паросочетание, состоящее из \(n\) ребер, или независимое множество, состоящее из \(n\) вершин.
Множество рёбер называется паросочетанием, если никакие два ребра этого множества не имеют общих вершин.
Множество вершин называется независимым, если никакие две вершины этого множества не соединены ребром.
Выходные данные
Выведите ответы для каждого из \(T\) графов. Формат ответа для одного графа описан ниже.
Если вы нашли паросочетание размера \(n\), то в первой строке выведите «Matching» (без кавычек), а во второй строке выведите \(n\) чисел, разделённых пробелами, — номера рёбер паросочетания. Рёбра нумеруются от \(1\) до \(m\) в порядке ввода.
Если вы нашли независимое множество размера \(n\), то в первой строке выведите «IndSet» (без кавычек), а во второй строке выведите \(n\) чисел, разделённых пробелами, — номера вершин независимого множества.
Если в графе нет ни того, ни другого, выведите «Impossible» (без кавычек).
Номера рёбер или вершин можно выводить в произвольном порядке.
Если существует несколько решений, вы можете вывести любое. В том числе, если в графе есть как паросочетание размера \(n\), так и независимое множество размера \(n\), то вы можете вывести любое из таких паросочетаний или любое из таких независимых множеств.
Примечание
Первые два графа из примера совпадают, однако в этом графе есть как паросочетание размера 1, так и независимое множество размера 1. Любое из таких паросочетаний и независимых множеств является правильным ответом.
В третьем графе нет паросочетания размера 2, однако есть независимое множество размера 2. В этом графе также есть независимое множество размера 5: 2 3 4 5 6. Тем не менее, такой ответ не является верным, потому что вас просят найти независимое множество (или паросочетание) размера ровно \(n\).
В четвёртом графе нет независимого множества размера 2, однако есть паросочетание размера 2.
Примеры
| № | Входные данные | Выходные данные |
|
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
|
Matching
2
IndSet
1
IndSet
2 4
Matching
1 15
|