Macəra

Hamı Hindistanlı Consun macəra tarixini bilir. Adəti üzrə Cons macəra axtarışında mürəkkəb situasiyalara düşür. İndi o, qədim Hind məbədindədir. Məbədin zalındakı divarında məbədin xəritəsi təsvir olunub. Məbəd - yalnız bir istiqamətdə hərəkət etmək mümkün olan dəhlizlərlə (koridorlarla) birləşdirilmiş otaqlar çoxluğudur. Qədim əlyazmalara görə kimsə ya bütün otaqları keçər və ya xəzinə tapır, məbəd dağılır və azadlığa çıxmaq mümkün olur. Həmçinin məlumdur ki, əgər siz istənilən bir otağa daxil olduqda və ya çıxdıqda bu otağın tavanı dağılır, gələcəkdə bu otaqdan keçmək mümkün olmayacaq. Xəritə məbədin bütün otaqlarını və onlar arasında tuneli, həmçinin bəzi otaqlarda xəzinə yerləşə biləcəyi ehtimalını müəyyənləşdirir.

Hindlilər bütün insanlar kimi tənbəldirlər və məsələni həll etməyi xahiş edirlər. Tunellər üzrə keçilən yollara görə gözlənilən orta yolu minimallaşdırmaq lazımdır.

O, həmçinin məlumat verib ki, istənilən otağı uzaqdan dağıda bilər.

Sizə bütün otaqlar üzrə bizim minimum gözlənilən məsafəni aldığımız yolu tapmaq lazımdır. Əgər bütün otaqların hamısını əhatə edən belə yol yoxdursa, Consu məlumatlandırmaq lazımdır, belə li, bu halda mümkündür ki, Cons məbəddən heç vaxt geri dönə bilməsin.

Giriş verilənləri

Giriş faylında bir neçə test yerləşir. Hər bir test məbədin xəritəsidir. Hər bir testin birinci sətrində məbəddəki otaqların sayı olan 1 £ N £ 100 ədədi yazılmışdır. Bundan sonra hər birində N aij (|aij| < 1000) ədədi olan N sətir gəlir. Əgər i-ci sətrin j-cu mövqeyində aij ədədi yerləşirsə, bu onu göstərir ki, i-ci otaqdan j-cu otağa aij uzunluqlu tunel var.Əgər aij sıfırdan kiçikdirsə, bu onu göstərir ki, tunel dolmuş və oradan keçmək olmaz. Sonra Npi ədədləri yerləşən sətir gəlir. pi ədədi i nömrəli otaqda xəzinənin olması ehtimalıdır.

Sonuncu testdə N = 0-dır və emal edilməməlidir.

Çıxış verilənləri

Hər bir test üçün orta məsafəni vergüldən sağda üç işarə olmaqla verin. Əgər bütün otaqları əhatə edən yol yoxdursa, onda çıxışa -1 verin.