28875번 - Защитники Асгарда 스페셜 저지다국어

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

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

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

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

В следующих $n$ строках даны описания подчиненных воинов. В $i$-й из них содержится список подчиненных $i$-го воина, он начинается с целого числа $k_i$ --- количества подчиненных $i$-го воина, далее следует $k_i$ целых чисел $c_{ij}$ --- индексы воинов, являющихся подчиненными $i$-го воина ($0 \le k_i \le 7$, $1 \le c_{ij} \le n$).

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

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

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