Минималистичная игра Вы играете в компьютерную игру. В этой игре есть 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. Можно показать, что порядок обхода лексикографичски меньше этого нельзя получить ни за какое количество действий.
// PascalABC.NET 3.1, сборка 1198 от 11.03.2016
begin
var a:=ArrRandom(ReadInteger('n='),0,2); a.Println;
a.Sorted.Println
end.
Тестовое решение:
n= 15
1 2 0 2 2 0 2 0 2 0 0 1 0 0 2
0 0 0 0 0 0 0 1 1 2 2 2 2 2 2
2. Но, поскольку считается, что школьникам больше заняться нечем, их заставляют писать примерно в таком стиле (и время займет, и ощибок понаделают):
// PascalABC.NET 3.1, сборка 1198 от 11.03.2016
const
nn=100;
var
i,j,n,t:integer;
a:array[1..nn] of integer;
begin
Write('n='); Read(n);
Randomize;
for i:=1 to n do begin
a[i]:=Random(3);
Write(a[i],' ')
end;
Writeln;
for i:=1 to n-1 do
for j:=1 to n-1 do
if a[j]>a[j+1] then begin
t:=a[j]; a[j]:=a[j+1]; a[j+1]:=t
end;
for i:=1 to n do Write(a[i],' ');
Writeln;
end.
Тестовое решение:
n=15
0 1 1 0 2 1 0 2 1 2 1 0 0 2 0
0 0 0 0 0 0 1 1 1 1 1 2 2 2 2
function
Transpose(a: array[,] of integer): array[,] of integer;
//Поворот на 90гр по часовой стрелке
begin
var m := Length(a, 0);
var n := Length(a, 1);
Result := new integer[n, m];
for var i := 0 to n-1 do begin
for var j := 0 to m-1 do
Result[i, j] := a[m-1-j, i];
end;
end;
begin
var n := ReadInteger('Введите n:');
//Заполнение матрицы NxN сл. числами и вывод на экран
var a :=MatrixRandom(n, n);
for var i:=0 to n-1 do begin
for var j:=0 to n-1 do
Print(a[i,j]);
println;
end;
println;
Println('поворот влево на 90 гр');
var b := Transpose(a);
b:=Transpose(b);
b:=Transpose(b);
for var i:=0 to n-1 do begin
for var j:=0 to n-1 do
Print(b[i,j]);
println;
end;
println;
Println('поворот вправо на 90гр');
b := Transpose(a);
for var i:=0 to n-1 do begin
for var j:=0 to n-1 do
Print(b[i,j]);
println;
end;
println;
Println('поворот на 180 гр');
b := Transpose(a);
b := Transpose(b);
for var i:=0 to n-1 do begin
for var j:=0 to n-1 do
Print(b[i,j]);
println;
end;
end.