Adaların Birləşdirilməsi#6529
Bytelandiya okeanında vətəndaş müharibəsi sona çatıb. İki Bytelandiya adası birləşərək Bytelandiya Birləşmiş Krallığını yaratmağa qərar verib. Yeni seçilmiş hökumətin ilk narahatlıqlarından biri nəqliyyat məsələsidir.
Müharibədən əvvəl hər iki ada mükəmməl nəqliyyat şəbəkəsinə malik idi. Hər bir adada, hər bir şəhər digər şəhərlərlə qatarla əlaqələndirilmişdi. Bu əlaqələr ikitərəfli idi. Müharibə zamanı bəzi qatar xətləri pozuldu və bu səbəbdən həmin xətlərdə qatarlar dayandırıldı. Hər bir adada ən çox 15 qatar dayandırıldı. Müharibə zamanı pozulmuş qatarları yenidən işə salmaqla yanaşı, hökumət adalararası bərə əlaqələri də yaratmalıdır. Bərələr hər bir şəhəri X ilə digər adadakı hər bir şəhəri Y ilə əlaqələndirəcək. Eyni adadakı şəhərlər arasında səyahət yalnız qatarla olacaq.
Bytelandiyada hər şey ikili, o cümlədən qatar və bərə biletlərinin qiymətləri. Bilet ya 0, ya da 1 vahid valyuta dəyərindədir. Hökumət müharibə zamanı pozulmamış qatarların bilet qiymətlərini dəyişməməyə qərar verdi. Müharibə zamanı dayandırılmış qatarlar və bütün bərə xətləri üçün bilet qiymətlərini təyin edəcək. Bytelandiyalılar, güclü riyaziyyatçılar olaraq, bilet sistemini elə dizayn etməyə qərar verdilər ki, hər hansı 3 fərqli şəhər X, Y və Z üçün,
C(X, Y) + C(Y, Z) ≥ C(X , Z)
şərti təmin edilsin. Burada C(X, Y) şəhər X-dən şəhər Y-ə getməyin bilet qiymətidir (əgər onlar eyni adaya aiddirsə qatarla, əks halda bərə ilə).
Sizə Bytelandiya adalarının təsviri verilir və məqsədiniz, əgər mümkündürsə, xərclərin təyin edilməsini tapmaqdır.
Proqramınız bir və ya bir neçə test nümunəsi üzərində sınaqdan keçiriləcək. Girişin ilk sətri tək bir tam ədəd T, test nümunələrinin sayı (1 ≤ T ≤ 100) olacaq. Test nümunələrindən sonra, hər bir test nümunəsi hər iki adanın təsvirini ehtiva edir (bir-birinin ardınca). Bir adanın təsviri bir sətirlə başlayır, bu sətir həmin adadakı şəhərlərin sayını göstərən bir tam ədəd C_k ilə başlayır, ardınca C_k sətir gəlir, hər biri C_k simvoldan ibarətdir (1 ≤ C_k ≤ 100). Hər bir simvol '0', '1' və ya 'x' ola bilər. i-ci sətrin j-ci simvolu həmin adadakı şəhər i-dən şəhər j-ə qatar biletinin qiymətidir. 'x' qiyməti dayandırılmış qatar xətlərindən birini ifadə edir. Hər bir C_k x C_k cədvəli simmetrik olacaq (cədvəl[i][j] = cədvəl[j][i] hər bir fərqli i və j üçün), və hər bir cədvəldə diaqonalda '0'lar olacaq (cədvəl[i][i] = '0' hər bir fərqli i üçün), həmçinin hər bir cədvəldə ən çox 30 'x' olacaq (15 fərqli qatar, çünki hər bir qatar cədvəldə iki dəfə qeyd olunacaq).
Qeyd edək ki, girişdə eyni adalarda 3 fərqli şəhər ola bilər və onları birləşdirən qatarlar dayandırılmayıb, və bu 3 şəhərlər yuxarıda təsvir edilən şərti təmin etmir.
Hər bir test nümunəsi üçün, əgər yuxarıda təsvir edilən şərtləri təmin edən xərclərin təyin edilməsi mümkün deyilsə, tək bir sətirdə NO (tırnaqsız) çıxış edin. Əks halda, ilk sətirdə YES (tırnaqsız) yazın, ardınca C_1+C_{2 } sətir, hər biri C_1+C_2 simvoldan ibarət (C_1 birinci adadakı şəhərlərin sayı, C_2 isə ikinci adadakı şəhərlərin sayı). i-ci sətrin j-ci simvolu şəhər i-dən şəhər j-ə getməyin qiymətidir (əgər onlar eyni adaya aiddirsə qatarla, əks halda bərə ilə). Çıxışda, birinci adadakı şəhərlər 1-dən C_1-ə (daxil olmaqla) qədər nömrələnir, ikinci adadakı şəhərlər isə C_1+1-dən C_1+C_2-ə (daxil olmaqla) qədər nömrələnir. Əgər bir neçə düzgün həll varsa, onlardan birini çap edin.
Qeyd edək ki, girişdə verilmiş qiymətləri dəyişə bilməzsiniz və çıxış cədvəli simmetrik olmalıdır.
Nümunə 1