Минималистичная игра Вы играете в компьютерную игру. В этой игре есть n уровней. Изначально у вас открыт один уровень с номером 1. Для каждого уровня задан упорядоченный набор напрямую зависимых от него уровней. Уровень a называется косвенно зависимым от b, если либо a напрямую зависит от b, либо a косвенно зависит от одного из уровней, который напрямую зависит от b. Гарантируется, что каждый уровень косвенно зависим от первого, а также все уровни, кроме первого, зависимы напрямую от ровно одного другого уровня. Более формально, уровни представляют корневое дерево, с корнем - уровнем 1. При прохождении уровня i открывается первый уровень из набора напрямую зависимых от i уровней, после прохождения первого уровня и всех косвенно зависимых от него уровней открывается второй и так далее. Таким образом мы выполним все уровни. Более формально выполняется левый обход дерева, где самый левый сын - первый в списке. Для лучшего понимания посмотрите секцию с примечаниями.

У вас есть чит-код, который позволяет сделать не более k изменений. За одно изменение можно выбрать вершину, и поменять местами две соседних в наборе зависимых от нее вершин. Вам нужно сделать порядок посещения вершин минимально лексикографически возможным. Первый порядок лексикографически меньше второго, если для какого-то t (1 ≤ t ≤ n - 1) первые t уровней в порядках совпадают, а t + 1 уровень меньше в первом порядке.

Формат входных данных
В первой строке вводятся два целых числа n и k - количество уровней и ограничение на количество изменений (1 ≤ n ≤ 5 * 105, 0 ≤ k ≤ 1012).

В последующих n строках идет описание уровней. На i-й строке сначала вводится целое число ti (0 ≤ ti ≤ n - 1) - количество уровней напрямую зависимых от i-го, после чего вводится ti целых чисел - номера уровней напрямую зависимых от i-го.

Формат результата
Выведите n чисел - минимальный лексикографически возможный порядок после не более чем k изменений.

Примеры
Входные данные
5 1
2 3 2
2 5 4
0
0
0
Результат работы
1 2 5 4 3
Входные данные
5 2
2 3 2
2 5 4
0
0
0
Результат работы
1 2 4 5 3
Входные данные
5 4
4 5 3 2 4
0
0
0
0
Результат работы
1 2 3 4 5
Примечания
Система оценки:

Решения, работающие при n ≤ 10, будут набирать не менее 10% .

Решения, работающие, когда от каждого уровня напрямую зависит не более двух других уровней, будут набирать не менее 25% .

Решения, работающие при n ≤ 5000, будут получать не менее 30% .

Решения, работающие, когда все уровни напрямую зависимы от первого, будут получать не менее 35% .

Решения, работающие, когда от каждого уровня напрямую зависит не более десяти других уровней, будут набирать не менее 50% .

Решения, работающие при n ≤ 200000, будут получать не менее 65% .

Разбор примеров:
Зависимости уровней в первом и втором тесте из условия не отличаются, отличаются лишь значения k. Изначальный обход дерева выглядит следующим образом: 1 3 2 5 4.

Рисунок снизу соответствует одному изменению в первом примере

После этого изменения порядок посещения станет: 1 2 5 4 3.

Рисунок снизу соответствует второму изменения во втором примере

После этого изменения порядок посещения станет: 1 2 4 5 3. Можно показать, что порядок обхода лексикографичски меньше этого нельзя получить ни за какое количество действий.

procedure CalcArray (const Ax: array of Integer; var S: Integer; var M: Real); // var в параметрах означает, что переменная используется для возврата значения

var

i, c: Integer;

begin

S := 0;

c := 0;

for i := 0 to High (Ax) do begin

S := S + Ax [i]; // здесь накапливаем сумму элементов

c := c + 1;

end;

M := S / c; // когда найдена сумму, рассчитываем среднеарифметическое

end;

var

A: array [0..4] of Integer; // размерность массивов можно делать любой, но начинаться с 0

B: array [0..14] of Integer;

C: array [0..9] of Integer;

i, s: Integer;

m: Real;

begin

SetConsoleCP (1251);

SetConsoleOutputCP (1251);

Randomize; // инициализация датчика случайных чисел

WriteLn ('Массив 1:');

for i := Low (A) to High (A) do begin

A [i] := Random (10); // заполняем элементы массива случайными значениями

Write (IntToStr (A [i]) + ' '); // выводим их для просмотра

end;

CalcArray (A, s, m); // вызов процедуры

WriteLn; // показываем возвращаемые из функции переменные

WriteLn ('Сумма элементов = ' + IntToStr (s));

WriteLn ('Среднеарифметическое = ' + FloatToStr (m));

WriteLn; // аналогично поступаем с другими массивами

WriteLn ('Массив 2:');

for i := Low (B) to High (B) do begin

B [i] := Random (10);

Write (IntToStr (B [i]) + ' ');

end;

CalcArray (B, s, m);

WriteLn;

WriteLn ('Сумма элементов = ' + IntToStr (s));

WriteLn ('Среднеарифметическое = ' + FloatToStr (m));

WriteLn;

WriteLn ('Массив 3:');

for i := Low (C) to High (C) do begin

C [i] := Random (10);

Write (IntToStr (C [i]) + ' ');

end;

CalcArray (C, s, m);

WriteLn;

WriteLn ('Сумма элементов = ' + IntToStr (s));

WriteLn ('Среднеарифметическое = ' + FloatToStr (m));

end.

procedure CalcArray (const Ax: array of Integer; var S: Integer; var M: Real);  // var в параметрах означает, что переменная используется для возврата значения

var

 i, c: Integer;

begin

 S := 0;

 c := 0;

 for i := 0 to High (Ax) do begin

   S := S + Ax [i];   // здесь накапливаем сумму элементов

   c := c + 1;

 end;

 M := S / c;   // когда найдена сумму, рассчитываем среднеарифметическое

end;

var

 A: array [0..4] of Integer;     // размерность массивов можно делать любой, но начинаться с 0

 B: array [0..14] of Integer;

 C: array [0..9] of Integer;

 i, s: Integer;

 m: Real;

begin

 SetConsoleCP (1251);

 SetConsoleOutputCP (1251);

 Randomize;   // инициализация датчика случайных чисел

 WriteLn ('Массив 1:');

 for i := Low (A) to High (A) do begin

   A [i] := Random (10);   // заполняем элементы массива случайными значениями

   Write (IntToStr (A [i]) + ' ');   // выводим их для вызов процедуры

 WriteLn;   // показываем возвращаемые из функции переменные

 WriteLn ('Сумма элементов = ' + IntToStr (s));

 WriteLn ('Среднеарифметическое = ' + FloatToStr (m));

 WriteLn;   // аналогично поступаем с другими массивами

 WriteLn ('Массив 2:');

 for i := Low (B) to High (B) do begin

   B [i] := Random (10);

   Write (IntToStr (B [i]) + ' ');

 end;

 CalcArray (B, s, m);

 WriteLn;

 WriteLn ('Сумма элементов = ' + IntToStr (s));

 WriteLn ('Среднеарифметическое = ' + FloatToStr (m));

 WriteLn;

 WriteLn ('Массив 3:');

 for i := Low (C) to High (C) do begin

   C [i] := Random (10);

   Write (IntToStr (C [i]) + ' ');

 end;

 CalcArray (C, s, m);

 WriteLn;

 WriteLn ('Сумма элементов = ' + IntToStr (s));

 WriteLn ('Среднеарифметическое = ' + FloatToStr (m));

end.