Защитники Асгарда
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

До Асгарда долетела весть, что богиня смерти, Хела, вырвалась из заточения. Защитникам Асгарда нужно срочно отрепетировать боевое построение. Структура войск в Асгарде выглядит следующим образом: войско состоит из n воинов, каждому воину присвоен уникальный номер от 1 до n, один из воинов является военачальником, у каждого воина есть от 0 до 7 подчиненных, каждый воин, кроме военачальника, является подчиненным ровно одного другого воина, военачальник не является ни чьим подчиненным, начиная с военачальника и переходя в подчиненного, можно дойти до любого воина. Иными словами, структура войска представляет собой подвешенное дерево, каждая из вершин которого имеет не более 7 детей.

Военачальник принял решение, что всех воинов нужно выстроить в шеренгу, при этом он хочет, чтобы в этой шеренге было как можно меньше инверсий. Инверсией называется пара воинов, таких, что номер воина идущего раньше больше, чем номер воина идущего позже. Построение происходит так: построение начинает военачальник, он упорядочивает своих подчиненных некоторым образом и в таком порядке вызывает их для совершения построения, очередной воин, вызванный для совершения построения, упорядочивает своих подчиненных некоторым образом, в таком порядке вызывает их для совершения построения, каждый раз перед вызовом следующего подчиненного дожидается, пока предыдущий завершит построение, затем встает в строй сам и завершает свое построение, в конце в строй встает военачальник. Обратите внимание, что стратегия поведения военачальника не отличается от стратегии поведения всех остальных воинов.

Вам дано описание армии Асгарда, найдите минимальное количество инверсий, которое может быть в построении, и определите, в каком порядке каждый из воинов должен вызывать своих подчиненных, чтобы достичь минимального количества инверсий в построении.

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

В первой строке даны два целых числа n и r — количество воинов в войске и номер воина, являющегося военачальником (1 ≤ n ≤ 200 000, 1 ≤ r ≤ n).

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

Гарантируется, что каждый воин, кроме военачальника, появляется в списках ровно один раз, а военачальник не появляется ни в одном списке. Гарантируется, что списки задают дерево, подвешенное за вершину r.

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

В первой строке выведите минимальное количество инверсий, которое может получится в итоговом построении. В следующих n строках выведите описание войска в том же формате, что и во входных данных. Список подчиненных каждого воина выводите в том порядке, в котором он должен их вызывать на построение.

Если ответов несколько, можете вывести любой.

Примеры

Входные данные
4 2
0
3 3 1 4
0
0
Выходные данные
2
0
3 1 3 4
0
0
Входные данные
7 2
2 7 6
3 1 5 3
1 4
0
0
0
0
Выходные данные
11
2 6 7
3 3 5 1
1 4
0
0
0
0