Максим с детства увлекается теорией графов. Сейчас его интересует все, что связано с двудольными графами. Двудольным графом называют граф, вершины которого можно разбить на две части так, что не существует ребер, соединяющих вершины из одной части. В одной замечательной книжке Максим прочитал, что в регулярном двудольном графе существует совершенное паросочетание. В этой же книге было написано, что регулярный граф — это граф, у которого степени всех вершин одинаковые, а совершенное паросочетание — разбиение всех вершин графа на пары соединенных ребром вершин. Однако, в этой книге ничего не было написано как найти это паросочетание. Всю ночь Максим провел в поиске алгоритма, однако нашел только маленькую сноску в огромной книге, что эта задача легко решается для двудольных регулярных графов с степенью 2k. Помогите ему найти совершенное паросочетание.
В первой строке задано число n
(1 ≤ n ≤ 50000
) — количество вершин в каждой доле графа. Во второй строке записана степень каждой вершины d
(d
= 2k, где 0 ≤ k ≤ 5
). В последующих n
строках для каждой вершины первой доли записано по d
чисел – номера смежных вершин второй доли. Вершины первой и второй доли нумеруются независимо от 1 до n
. В графе могут быть кратные ребра. Гарантируется, что степени всех вершин, как первой, так и второй доли, равны d
. В графе допускаются кратные ребра, то есть пару вершин могут соединять более одного ребра.
Выведите ровно n
чисел — для каждой вершины первой доли номер вершины второй доли, с которой она будет объединена в совершенном паросочетании. В выводе должна быть некоторая перестановка чисел от 1 до n
. Если решений несколько, выведите любое.