Metro
Bəzi şəhərlərdə metro şəbəkəsi ağac formasında olur, yəni hər iki stansiya arasında yalnız bir unikal yol mövcuddur. Belə metro şəbəkələrinin unikal mərkəzi stansiyası var. Təsəvvür edin ki, siz belə bir şəhərdə turistsiniz və bütün metro şəbəkəsini öyrənmək istəyirsiniz. Siz mərkəzi stansiyadan başlayırsınız, təsadüfi bir istiqamət seçirsiniz və növbəti stansiyaya gedirsiniz. Hər dəfə stansiyaya çatanda, hələ getmədiyiniz bir qolu seçirsiniz. Əgər cari stansiyada belə qollar yoxdursa, ilk dəfə gəldiyiniz stansiyaya geri dönürsünüz. Bu, bütün qolları iki dəfə (hər istiqamətdə bir dəfə) keçənə qədər davam edir. Bu anda siz mərkəzi stansiyada olmalısınız. Belə bir səyahət ikilik sıranı aşağıdakı kimi kodlaşdırıla bilər. 0 rəqəmi bizi mərkəzi stansiyadan uzaqlaşdıran səfəri, 1 rəqəmi isə mərkəzi stansiyaya yaxınlaşdıran səfəri kodlaşdırır. Eyni metro şəbəkəsi üçün bir neçə mümkün kodlaşdırma sırasi mövcuddur, çünki "tədqiq olunmamış" qollar təsadüfi seçilir.
Eyni metro şəbəkəsini təsvir edib-etmədiyini müəyyən edən bir proqram yazın.
Giriş verilənləri
Giriş faylının birinci sətrində N (1 ≤ N ≤ 20) tam ədədi - testlərin sayı var. Sonra N cüt sıra gəlir, hər biri 0 və 1 rəqəmlərindən ibarət, uzunluğu ən çox 3000 simvol.
Hər sətirdə bir metro şəbəkəsinin düzgün tədqiqi kodlaşdırılıb.
Çıxış verilənləri
Çıxış faylında hər bir sıra cütü üçün "same" mesajını yazın, əgər hər iki sıra eyni metro şəbəkəsinin tədqiqini kodlaşdırırsa, və ya "different" mesajını yazın, əgər tədqiq olunan metro şəbəkələri fərqlidirsə.