Codeforces Round 576 (Div. 1) |
---|
Закончено |
Дан неориентированный граф, состоящий из $$$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.
Название |
---|