e-olymp
Задачи

Разбиения множества

Разбиения множества

Рассмотрим множество, состоящее из первых n натуральных чисел: Nn = {1, 2, ..., n}. Разбиение - это представление этого множества в виде объединения одного или нескольких непустых множеств. Примерами разбиений для n=5 являются:

{1, 2, 3, 4, 5} = {1, 2, 3} U {4, 5}

{1, 2, 3, 4, 5} = {1, 3, 5} U {2, 4}

{1, 2, 3, 4, 5} = {1, 2, 3, 4, 5}

{1, 2, 3, 4, 5} = {1} U {2} U {3} U {4} U {5}

Всего существует 52 разбиения множества N5. Заметим, что разбиения, отличающиеся только порядком объединяемых множеств, не различаются.

Разбиения множества Nn можно упорядочить лексикографически.

Для того, чтобы определить этот порядок, вначале определим лексикографический порядок на подмножествах Nn. Будем говорить, что множество ATM_podmnNn лексикографически меньше множества BTM_podmnNn и писать A < B, если верно одно из следующих утверждений:

  • найдется i, такое что iTM_inA, iTM_not_inB, для всех j < i: jTM_inA iff jTM_inB, и найдется k > i, такое что kTM_inB;
  • ATM_podmnB и i < j для всех iTM_inA и jTM_inB \ A.

Очевидно, что введенное отношение является полным порядком на подмножествах множества Nn. Теперь определим каноническое представление разбиения, как представлние, в котором объединяемые множества упорядочены лексикографически.

Разбиения упорядочиваются лексикографически следующим образом. Разбиение Nn = A1 U A2 U ... U Akлексикографически меньше разбиения Nn = B1 U B2 U ... U Bl, если существует такое i, что A1 = B1, A2 = B2, ..., Ai-1 = Bi-1 и Ai < Bi.

По разбиению множества Nn найдите следующее в лексикографическом порядке разбиение.

Входные данные

Входной файл содержит несколько описаний тестов. Каждое описание является каноническим представлением разбиения. Первая строка описания содержит n и k — количество элементов в разбиваемом множестве и количество частей в разбиении (1n200). Последующие k строк содержат элементы разбиения. Элементы каждого множества упорядочены по возрастанию.

Описания тестов отделены друг от друга пустыми строками. Последняя строка входного файла содержит два нуля. Этот тест не должен обрабатываться.

Сумма n по всем описаниям не превосходит 2000.

Выходные данные

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

Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные
5 2
1 2 3
4 5

5 2
1 3 5
2 4

5 1
1 2 3 4 5

5 5
1
2
3
4
5

0 0
Выходные данные
5 2
1 2 3 4
5

5 4
1 4
2
3
5

5 2
1 2 3 5
4

5 4
1
2
3
4 5