Südləmə qaydası (Qızıl)
n fermer Cohnun 1..n nömrələnmiş inəkləri hər səhər sağdığı sosial iyerarxiya inkişaf etdirmişlər.
Cohn bu struktur haqqında m müşahidə aparmışdır. Hər müşahidə, onun inəklərindən bəzilərinin müəyyən bir sırada sağılmalı olduğunu göstərən sıralı bir siyahıdır. Məsələn, 2 5 1 siyahısı, əvvəlcə inək 2-ni, bir müddət sonra inək 5-i və daha sonra inək 1-i sağmalı olduğunu göstərir.
Cohnun müşahidələri prioritetləşdirilmişdir, buna görə də onun məqsədi ilk X müşahidənin şərtlərini yerinə yetirmək üçün X dəyərini maksimuma çatdırmaqdır. Əgər bir neçə sağım sırası X müşahidələrini təmin edə bilirsə, o, nömrəsi daha kiçik olan inəyin əvvəl sağılacağı sıranı seçir. Başqa sözlə, əgər bir neçə sağım sırası bu şərtləri təmin edirsə, Cohn leksikoqrafik olaraq ən kiçik olanı seçir. Sıra x, sıra y-dən leksikoqrafik olaraq kiçikdir, əgər bəzi j üçün x[i] = y[i] bütün i < j üçün və x[j] < y[j] (başqa sözlə, iki sıra müəyyən bir nöqtəyə qədər eynidir, bu nöqtədə isə x y-dən kiçikdir).
Cohna inəklərini sağmaq üçün ən yaxşı sıranı müəyyən etməyə kömək edin.
Giriş Məlumatları
Birinci sətir n (1 ≤ n ≤ 10^5) və m (1 ≤ m ≤ 50000) ədədlərini ehtiva edir. Növbəti m sətirin hər biri bir müşahidəni təsvir edir. i + 1 sətiri i müşahidəsini təsvir edir və bu müşahidədəki inəklərin sayını m[i], ardından bu müşahidədəki inəklərin sırasını müəyyən edən m[i] tam ədədlər siyahısını ehtiva edir. m[i] cəmi 200000-i keçmir.
Çıxış Məlumatları
Cohnun inəklərini sağmalı olduğu sıranı verən 1..n ədədlərinin bir permutasiyasını çıxarın.
Nümunə
Burada Cohnun 4 inəyi var və o, inək 1-i inək 2-dən əvvəl və inək 2-ni inək 3-dən əvvəl sağmalıdır (birinci müşahidə), həmçinin inək 4-ü inək 2-dən əvvəl sağmalıdır (ikinci müşahidə) və inək 3-ü inək 4-dən əvvəl və inək 4-ü inək 1-dən əvvəl sağmalıdır (üçüncü müşahidə). İlk iki müşahidə eyni vaxtda təmin edilə bilər, lakin üçüncü ilə alınmır, çünki inək 1-i inək 3-dən əvvəl və inək 3-ü inək 1-dən əvvəl sağmaq lazımdır.
Bu, iki mümkün sıra olduğunu göstərir: 1 4 2 3 və 4 1 2 3, bunlardan birincisi leksikoqrafik olaraq ən kiçikdir.