В огромной подземной лаборатории злая корпорация Зонтик создает клонов для своих страшных экспериментов. Однажды компания клонировала мальчика по имени Андрюша, который был умнее своих сверстников. Андрюша понял, что вокруг творится что-то неладное. Он поднял клонов на борьбу против корпорации, и те начали искать выход из лаборатории. Компании ничего не оставалось, кроме как запустить процесс самоуничтожения подземного комплекса.
Лаборатория представляет собой связный граф из n вершин и m ребер. В некоторых вершинах этого графа k клонов Андрюши начинают поиск выхода из лаборатории. В процессе поиска каждую секунду они переходят по ребру в соседнюю вершину, причем в каждой вершине может одновременно находиться сколько угодно клонов. Каждый клон может в некоторый момент времени остановиться и прекратить поиски, но он обязательно должен их начать, то есть посетить хотя бы одну вершину. Более того, выход может находиться в произвольном месте лаборатории, поэтому клоны должны обойти граф целиком, то есть каждая вершина графа должна быть посещена хотя бы одним клоном хотя бы один раз.
Время клонов ограничено, и каждый из них сможет обойти не более 
комнат до того, как лаборатория взорвется.
Ваша задача заключается в том, чтобы расставить клонов по вершинам графа и для каждого клона вывести путь, по которому он должен обходить граф. При этом количество вершин в каждом пути должно быть не больше .
В первой строке находятся три целых числа n, m и k (1 ≤ n ≤ 2·105, n - 1 ≤ m ≤ 2·105, 1 ≤ k ≤ n) — число вершин в графе, число ребер в графе и количество клонов.
В каждой из следующих m строк находятся два целых числа xi и yi (1 ≤ xi, yi ≤ n) — номера двух вершин, соединенных очередным ребром. В графе могут быть петли и кратные ребра.
Гарантируется, что граф связный.
Выведите k строк. В начале i-й строки выведите целое число ci (
) — количество вершин, которые посетит i-й клон, а затем выведите ci целых чисел — номера вершин, которые он посетит, в порядке их посещения. Выводите вершину каждый раз, когда клон ее посещает, даже если он посещал ее до этого.
Гарантируется, что ответ существует.
3 2 1
2 1
3 1
3 2 1 3
5 4 2
1 2
1 3
1 4
1 5
3 2 1 3
3 4 1 5
В первом тесте есть всего 1 клон, он посещает вершины в порядке (2, 1, 3), что укладывается в ограничение 6 посещенных вершин.
Во втором тесте есть 2 клона, они посещают вершины в порядке (2, 1, 3) и (4, 1, 5), что укладывается в ограничение 5 посещенных вершин.
