Это особая задача. Внимательно прочитайте примечание (замечание).
Совунья случайно нашла в старых вещах $$$n$$$ писем от своего ухажёра из прошлого. Её накрыли воспоминания о $$$n$$$ памятных датах, и в порыве чувства упущенного счастья она решила уничтожить все письма как можно скорее.
Каждое письмо соединяет ребром какие-то памятные даты $$$v$$$ и $$$u$$$. Каждую пару памятных дат соединяет не более одного письма.
Памятные даты $$$v$$$ и $$$u$$$ находятся в одной компоненте связности, если можно добраться из $$$v$$$ в $$$u$$$ по рёбрам. Известно, что изначально все памятные даты находятся в одной компоненте связности.
За одно действие Совунья может порвать не более половины писем в каждой компоненте связности. Половина округляется вверх до ближайшего целого.
Помогите Совунье порвать все письма за как можно меньшее количество действий.
В первой строке дано целое число $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — количество памятных дат и писем.
В следующих $$$n$$$ строках даны целые числа $$$v$$$, $$$u$$$ ($$$1 \le v, u \le n$$$, $$$v \neq u$$$) — описание писем.
Гарантируется, что все памятные даты находятся в одной компоненте связности.
В первой строке выведите целое число $$$k$$$ ($$$1 \le k \le 20$$$) — количество действий.
Далее выведите описание действий.
В первой строке $$$i$$$-й итерации выведите целое число $$$c_i$$$ ($$$1 \le c_i \le n$$$) — количество удалённых писем.
Во второй строке $$$i$$$-й итерации выведите $$$c_i$$$ целых чисел $$$d_1, d_2, \ldots, d_{c_i}$$$ ($$$1 \le d_j \le n$$$) — номера удалённых писем в порядке ввода.
51 23 45 12 33 5
4 2 1 4 1 2 1 5 1 3
В этой задаче всего один скрытый тест, сгенерированный случайно. Вы будете соревноваться на нём с другими участниками олимпиады. В разделе «Протокол» для каждой успешной посылки вы увидите количество операций, за которое справились. Для посылок со статусом «Неправильный ответ» вы увидите короткое сообщение чекера, которое может помочь при дебаге.
Во время тура ваше решение проверяется на корректность, но не на минимальность. Вы можете получить вердикт «Ожидает подтверждения». Он означает, что решение вывело корректную последовательность операций. Если вы сдадите корректное решение повторно, статус предыдущего решения поменяется на «Проигнорировано». К финальному тестированию на минимальность будет допущено ваше последнее корректное решение.
Финальное тестирование будет проведено после окончания тура. Участники, порвавшие все письма за минимальное количество действий среди всех участников, получат вердикт «ОК». Остальные участники, сдавшие корректное решение, получат вердикт «Неправильный ответ». Решение жюри не участвует в соревновании. Например, если корректное решение сдал всего один участник, он гарантированно получит вердикт «ОК», но если корректное решение сдали четыре участника, из них первые два справились за шесть действий, третий за семь, а четвёртый за двадцать, вердикт «ОК» получат только первые два.
Штраф считается по обычным правилам, как-будто посылка с вердиктом «Ожидает подтверждения» является посылкой с вердиктом «ОК», при этом посылки с вердиктом «Проигнорирована» игнорируются.
