Şirkət Təşkilatı
Bir neçə il əvvəl bir şirkət qurmusunuz və xoşbəxtlikdən bu şirkət çox uğurlu olub. Şirkət böyüdükcə işçiləri daha yaxşı təşkil etmək üçün qruplar yaratmağa və işçiləri bu qruplara təyin etməyə qərar verdiniz.
İndi şirkətdəki layihələrə uyğun olaraq n qrup yaratmağı planlaşdırırsınız. Bəzən qruplardakı üzvlərlə bağlı müəyyən məhdudiyyətləriniz olur. Məsələn, bir qrup digər qrupun alt qrupu olmalıdır, çünki əvvəlki qrup sonrakı qrupun təcrübəli üzvlərindən ibarət olacaq; iki qrupdakı üzvlər eyni olmalıdır, çünki iki layihənin cari fəaliyyətləri bir-biri ilə sıx əlaqəlidir; iki qrupdakı üzvlər tamamilə fərqli olmalıdır ki, korrupsiyadan qaçınılsın; iki qrupda ümumi işçi ola bilməz, çünki təhlükəsizlik səbəbi var; və iki qrupda əməkdaşlığı asanlaşdırmaq üçün ümumi işçi olmalıdır.
Xülasə, Xi (i = 1, ..., n)-nin i-ci qrupa təyin edilmiş işçilərin dəsti olduğunu nəzərə alaraq, aşağıdakı beş növ məhdudiyyətimiz var.
X_i
X_j
X_i = X_j
X_i ≠ X_j
X_i
X_j = ∅
X_i
X_j ≠ ∅
Məhdudiyyətləri ardıcıllığı nəzərə almadan siyahıya aldığınız üçün, bütün məhdudiyyətləri təmin edə bilməyəcəyiniz bir vəziyyət ola bilər. Məhdudiyyətlər buna görə prioritetlərinə görə sıralanır və indi ən yüksək prioritetli neçə məhdudiyyətin təmin edilə biləcəyini bilmək istəyirsiniz.
İşçilərin bacarıqlarını nəzərə almağa ehtiyac yoxdur. Yəni, istənilən şəxsi istənilən qrupa təyin edə bilərsiniz. Həmçinin, heç bir işçisi olmayan qruplar yarada bilərsiniz. Üstəlik, daha çox məhdudiyyəti təmin edə bilsəniz, istədiyiniz qədər işçi işə götürə və ya işdən çıxara bilərsiniz. Məsələn, nümunə girişindəki ilk datasetə uyğun olaraq, üç qrup üzərində aşağıdakı beş məhdudiyyətin olduğunu fərz edək.
X_2
X_1
X_3
X_2
X_1
X_3
X_1 ≠ X_3
X_3
X_1
X_1, X_2 və X_3-ə eyni işçi dəstini təyin edərək ilk üç məhdudiyyəti təmin edə bilərik. Lakin, X_1, X_2 və X_3-ə işçiləri necə təyin etməyimizdən asılı olmayaraq, eyni zamanda ilk dörd ən yüksək prioritetli məhdudiyyəti təmin edə bilmərik. Halbuki, eyni zamanda ilk üç məhdudiyyəti və beşinci məhdudiyyəti təmin edə bilərik, cavab üç olmalıdır.
Giriş verilənləri
Giriş bir neçə datasetdən ibarətdir. Datasetin ilk sətri iki tam ədəd n (2 ≤ n ≤ 100) və m (1 ≤ m ≤ 10000) ilə başlayır, bu da qrupların sayını və məhdudiyyətlərin sayını göstərir. Sonra m məhdudiyyətin təsviri gəlir. Hər bir məhdudiyyətin təsviri üç tam ədəd s (1 ≤ s ≤ 5), i (1 ≤ i ≤ n), və j (1 ≤ j ≤ n; j ≠ i) ilə ibarətdir, bu da i-ci qrup və j-ci qrup üzərində tətbiq olunan s-ci növ məhdudiyyəti bildirir. Məhdudiyyət nömrəsi yuxarıda göstərildiyi kimi sıralanır. Məhdudiyyətlər prioritetlərinin azalan sırasına görə verilir.
Giriş iki sıfırdan ibarət bir sətrlə bitir.
Çıxış verilənləri
Hər bir dataset üçün eyni zamanda təmin edilə bilən ən yüksək prioritetli məhdudiyyətlərin sayını çıxış edin.