28924번 - Помогите спасти Землю! 스페셜 저지다국어

Отряд супергероев спешит на помощь защитникам Земли на битву с Таносом. Супергерои сейчас находятся на Титане, и у них есть только один космический шатл, в который помещается $k$ пассажиров и один пилот. Отряд состоит из одного мудрого предводителя и еще $n$ супергероев. К сожалению, некоторые пары супергероев недолюбливают друг друга, могут повздорить, или даже того хуже --- нанести вред друг другу. Но когда рядом находится предводитель, супергерои никогда не будут конфликтовать, потому что предводитель это жестко пресекает.

Решено, что шатлом будет управлять предводитель. Теперь его интересует вопрос, получится ли переправить всех супергероев на Землю. Процесс переправки будет происходить следующим образом:

• Не более чем $k$ супергероев садятся в шатл вместе с предводителем. Среди оставшихся на Титане супергероев, не должно быть ни одной конфликтующей пары, иначе возможны печальные последствия.
• Шатл летит на Землю. Во время полета, супергерои на корабле находятся рядом с предводителем, поэтому не будут драться.
• На Земле из шатла высаживаются все супергерои, которые в нем находились. При этом среди супергероев, находящихся в этот момент на Земле, может быть конфликтующая пара. Они не подерутся, потому что рядом находится предводитель.
• Не более чем $k$ супергероев садятся в шатл. Среди оставшихся на Земле супергероев не должно быть конфликтующей пары.
• Шатл летит на Титан.
• На Титане из шатла высаживаются все супергерои. Среди находящихся в этот момент на Титане супергероев, может быть конфликтующая пара.

Пункты повторяются по циклу, пока все супергерои и предводитель не окажутся на Земле. Предводитель может лететь с планеты на планету и вовсе без супергероев, если это необходимо. Если на планете нет предводителя, на ней не должно быть конфликтующей пары. Других ограничений на конфликтующие пары нет.

Вам дан список конфликтующих пар. Помогите предводителю определить порядок действий для транспортировки всех супергероев на Землю, либо сообщите, что это невозможно. Обратите внимание, что минимизировать количество полетов не требуется. Однако, предводителя интересует способ, содержащий не более $100\,000$ перелетов. Можно доказать при данных ограничениях, что если существует способ доставить всех на Землю, существует способ доставить всех на Землю за не более, чем $100\,000$ перелетов.

В первой строке даны три целых числа $n$, $m$ и $k$ --- количество супергероев, количество конфликтующих пар и количество супергероев, помещающихся в шатл ($1 \le n \le 15$, $0 \le m \le n \cdot (n - 1) / 2$, $1 \le k \le 15$).

В следующих $m$ строках даны пары целых чисел $a_i$, $b_i$ --- номера супергероев, которые конфликтуют ($1 \le a_i, b_i \le n$, $a_i \neq b_i$).

Гарантируется, что каждая пара супергероев встречается не более одного раза, в том числе если во входных данных есть пара $a_i$, $b_i$, тогда во входных данных не может быть пары $b_i$, $a_i$.

Если невозможно переправить всех супергероев и предводителя на Землю, в единственной строке выведите $-1$.

Иначе, в первой строке выведите целое число $t$ --- количество перелетов, которое должен совершить шатл, чтобы на Земле оказались все супергерои и предводитель ($t \le 100\,000$). В $i$-й из следующих $t$ строк выведите список супергероев, которые будут находиться шатле во время $i$-го перелета. В начале выведите $q_i$ --- размер этого списка, а затем $q_i$ различных чисел --- номера супергероев, которые будут находиться в шатле во время $i$-го перелета.