Hədiyyələr

Manao axşam məclisi təşkil etməyə qərar verdi. O, evini parlaq şəkildə bəzədi, menyunu diqqətlə seçdi, yaxın dostlarını dəvət etdi... və birdən hədiyyələri unutduğunu anladı!

Manao hər zaman axşam məclisində qonaqlara hədiyyələr verir. Üstəlik, o, hər kəsə elə bir şey verir ki, həmin şəxs buna sevinir. Qonaqlar da özləri ilə hədiyyə gətirirlər, hər biri bir dənə. Çünki vaxt azdır, Manao hədiyyələr almağa çatdırmayacaq, ona görə də vəziyyətdən çıxış yolu tapmalıdır. Və o zaman onun ağlına dahiyanə bir fikir gəlir: qonaqların gətirdiyi hədiyyələri onların arasında yenidən bölüşdürmək! Əlbəttə ki, bir insana öz gətirdiyi hədiyyəni vermək olmaz. Manao dostlarını yaxşı tanıyır və əvvəlcədən deyə bilər ki, kimə kimin gətirdiyi hədiyyə xoş gələcək.

Amma təəssüf ki, elə ola bilər ki, hədiyyələri elə bölüşdürmək mümkün olmayacaq ki, bütün dostlar razı qalsın. Buna görə də Manao əlavə olaraq bir neçə tanışını dəvət etməyə qərar verdi. Manao onları da yaxşı tanıyır və ona görə də əminliklə proqnozlaşdıra bilər ki, kim nə gətirəcək və nəyə sevinəcək. Manao tanışlarını da incitmək istəmir, ona görə də hər biri də sevinəcəyi bir hədiyyə almalıdır. Amma axşam məclisini tam bir qarışıqlığa çevirməmək üçün Manao elə az sayda tanış dəvət edəcək ki, bu, bütün qonaqlar arasında hədiyyələri elə bölüşdürməyə imkan versin ki, hər kəs razı qalsın.

Manao-nun N dostu və M digər tanışı var. Dostları 1-dən N-ə qədər, tanışları isə N+1-dən N+M-ə qədər nömrələyək. Sizə hansı hədiyyənin kimə xoş gələcəyini müəyyən etmək üçün bir matrisa verilir. Dəvət edilməli olan ən az sayda tanışın sayını müəyyən edin. Əgər bu mümkün deyilsə, -1 rəqəmini çıxarın.

Giriş verilənləri

Giriş faylının ilk sətiri iki ədəd N və M ehtiva edir. Növbəti N+M sətirin hər biri N+M simvolu "Y" və ya "N" ehtiva edir. Bu sətirlərdən i-ci sətirdəki j-ci simvol, i nömrəli şəxsin j nömrəli şəxsin hədiyyəsini bəyənib-bəyənməyəcəyini göstərir.

2 ≤ N ≤ 100, 0 ≤ M ≤ 100. Heç bir qonaq öz hədiyyəsini bəyənə bilməz.

Çıxış verilənləri

Əgər heç bir tanış dəstəsi Manao-nun axşam məclisini xilas edə bilməzsə, -1 çıxarın, əks halda belə minimal dəstənin ölçüsünü çıxarın.

Nümunələr

Qeyd

Birinci nümunədə 3 nömrəli şəxsi dəvət etmək olar, sonra 2 nömrəli qonağa 3 nömrəli qonağın gətirdiyi hədiyyəni, 3 nömrəli qonağa 1 nömrəli qonağın gətirdiyi hədiyyəni, 1 nömrəli qonağa isə 2 nömrəli qonağın hədiyyəsini vermək olar. Üçüncü nümunədə hər iki tanışı dəvət edərək, birinci və ikinci dostların hədiyyələrini dəyişmək, dördüncü şəxsə üçüncünün hədiyyəsini, üçüncü şəxsə beşincinin hədiyyəsini, beşinci şəxsə isə dördüncünün hədiyyəsini vermək olar.