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

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

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

Разбиения множества N_n можно упорядочить лексикографически. Для того, чтобы определить этот порядок, вначале определим лексикографический порядок на подмножествах N_n. Будем говорить, что подмножество A={a₁, a₂, ..., a_k} (a₁ < a₂ < ... < a_k) множества N_n лексикографически меньше подмножества B={b₁, b₂, ..., b_m} (b₁ < b₂ < ... < b_m) множества N_n и писать A < B, если верно одно из следующих утверждений:

• найдётся i, такое что a₁ = b₁, a₂ = b₂, ..., a_{i - 1} = b_{i - 1} и a_i < b_i;
• k < m и при этом a₁ = b₁, a₂ = b₂, ..., a_k = b_k.

Таким образом, для любых двух подмножеств A и B верно ровно одно из трёх утверждений: или A < B, или A совпадает с B, или B < A, а также есть транзитивность: если A < B и B < C, то A < C. Теперь определим каноническое представление разбиения как представление, в котором объединяемые множества упорядочены лексикографически.

Разбиения упорядочиваются лексикографически следующим образом. Разбиение N_n = A₁ U A₂ U … U A_k лексикографически меньше разбиения N_n = B₁ U B₂ U … U B_m, если существует такое i, что A₁ = B₁, A₂ = B₂, . . . , A_i-1 = B_i-1 и A_i < B_i.

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

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

Входной файл INPUT.TXT содержит несколько описаний тестов. Каждое описание является каноническим представлением разбиения. Первая строка описания содержит n и k - количество элементов в разбиваемом множестве и количество частей в разбиении (1 ≤ n ≤ 200). Последующие k строк содержат элементы разбиения. Элементы каждого множества упорядочены по возрастанию. Описания тестов отделены друг от друга пустыми строками. Последняя строка входного файла содержит два нуля. Этот тест не должен обрабатываться. Сумма n по всем описаниям не превосходит 2000.

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

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

Пример

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]