До Асгарда долетела весть, что богиня смерти, Хела, вырвалась из заточения. Защитникам Асгарда нужно срочно отрепетировать боевое построение. Структура войск в Асгарде выглядит следующим образом: войско состоит из 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