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