Kümənin parçalanması
İlk n təbii ədədlərdən ibarət çoxluğu nəzərdən keçirək: N_n = {1, 2, ..., n}. Bölünmə bu çoxluğun bir və ya bir neçə boş olmayan alt çoxluqların birləşməsi şəklində təqdim edilməsidir. Məsələn, n=5 üçün bəzi bölünmə nümunələri:
{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}
Ümumilikdə, N_5 çoxluğunun 52 bölünməsi mövcuddur. Qeyd edək ki, yalnız birləşdirilən çoxluqların sırası ilə fərqlənən bölünmələr fərqli sayılmır.
N_n çoxluğunun bölünmələrini leksikoqrafik olaraq sıralamaq mümkündür.
Bu sıralamanı müəyyən etmək üçün əvvəlcə N_n alt çoxluqlarında leksikoqrafik sıralama müəyyən edək. Deyəcəyik ki, A çoxluğu N_n leksikoqrafik olaraq B çoxluğundan kiçikdir və A < B yazacağıq, əgər aşağıdakı ifadələrdən biri doğrudursa:
Elə bir i tapılar ki, i
A, i
B, bütün j < i üçün: j
A iff j
B, və elə bir k > i tapılar ki, k
B;
A
B və i < j bütün i
A və j
B A.
Aydındır ki, təqdim olunan münasibət N_n çoxluğunun alt çoxluqlarında tam sıralamadır. İndi kanonik təqdimat bölünməsini, birləşdirilən çoxluqların leksikoqrafik olaraq sıralandığı təqdimat kimi müəyyən edək.
Bölünmələr leksikoqrafik olaraq aşağıdakı kimi sıralanır. N_n = A_1 U A_2 U ... U A_k bölünməsi leksikoqrafik olaraq N_n = B_1 U B_2 U ... U B_l bölünməsindən kiçikdir, əgər elə bir i varsa ki, A_1 = B_1, A_2 = B_2, ..., A_{i-1} = B_{i-1} və A_i < B_i.
N_n çoxluğunun bölünməsi üçün leksikoqrafik sırada növbəti bölünməni tapın.
Giriş verilənləri
Giriş faylı bir neçə test təsvirini ehtiva edir. Hər bir təsvir bölünmənin kanonik təqdimatıdır. Təsvirin ilk sətiri n və k - bölünən çoxluqdakı elementlərin sayı və bölünmədəki hissələrin sayını (1 ≤ n ≤ 200) ehtiva edir. Növbəti k sətir bölünmənin elementlərini ehtiva edir. Hər bir çoxluğun elementləri artan sırada sıralanır.
Test təsvirləri bir-birindən boş sətirlərlə ayrılır. Giriş faylının son sətiri iki sıfır ehtiva edir. Bu test işlənməməlidir.
Çıxış verilənləri
Hər bir test üçün leksikoqrafik sırada növbəti bölünməni çıxarın. Əgər giriş faylındakı bölünmə leksikoqrafik sırada sonuncudursa, leksikoqrafik sırada birinci olanı çıxarın. Giriş faylındakı formatdan istifadə edin. Bölünmələri bir-birindən boş sətirlərlə ayırın.