eolymp
Competitions

2011 Зимняя Школа, Харьков, День 8, День Виталия Гольдштейна

Регулярное паросочетание

Максим с детства увлекается теорией графов. Сейчас его интересует все, что связано с двудольными графами. Двудольным графом называют граф, вершины которого можно разбить на две части так, что не существует ребер, соединяющих вершины из одной части. В одной замечательной книжке Максим прочитал, что в регулярном двудольном графе существует совершенное паросочетание. В этой же книге было написано, что регулярный граф — это граф, у которого степени всех вершин одинаковые, а совершенное паросочетание — разбиение всех вершин графа на пары соединенных ребром вершин. Однако, в этой книге ничего не было написано как найти это паросочетание. Всю ночь Максим провел в поиске алгоритма, однако нашел только маленькую сноску в огромной книге, что эта задача легко решается для двудольных регулярных графов с степенью 2k. Помогите ему найти совершенное паросочетание.

Входные данные

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

Выходные данные

Выведите ровно n чисел — для каждой вершины первой доли номер вершины второй доли, с которой она будет объединена в совершенном паросочетании. В выводе должна быть некоторая перестановка чисел от 1 до n. Если решений несколько, выведите любое.

Time limit 3 seconds
Memory limit 256 MiB
Input example #1
2
1
1
2
Output example #1
1
2
Author Vitaly Goldstein
Source Winter School, Kharkov, 2011, Day 9