Muzey#5733
Muzey böyük və dəbdəbəli otaqlar, parlaq dəhlizlərlə doludur. O qədər genişdir ki, burada bir tur planlaşdırmaq ciddi bir problemə çevrilir. Bu, sizin köməyinizin lazım olduğu yerdir. Siz, binada naviqasiyanı asanlaşdıracaq işarələrin planlaşdırılmasına kömək etməlisiniz. Fikir belədir ki, əgər bir otaqda digər otaqlara dəhlizlər vasitəsilə aparan d qapı varsa, bu qapılar və müvafiq dəhlizlər (yerli olaraq) 1, 2, ..., d nömrələri ilə işarələnir. Sonra bütün ziyarətçilərə sadə bir proseduru izləmək tövsiyə olunur. Əgər onlar turunun əvvəlində v otağındadırsa, 1 nömrəli qapını seçməli və müvafiq dəhlizdən keçməlidirlər. Əgər onlar v otağındadırsa və ora i nömrəli qapıdan daxil olublarsa, növbəti nömrəli qapını seçməlidirlər (yəni əgər i < d isə i+1 və əgər i = d isə 1) və müvafiq dəhlizdən keçməlidirlər. Budur sadə bir nümunə, burada turistlər 1 otağında başlayır və bu sırayla 1, 2, 3, 4, 5, 6 otaqlarını ziyarət edirlər, hər dəhlizdən ən azı bir dəfə keçərək:
Bu muzeydə eksponatlar yalnız otaqlarda deyil, həm də müxtəlif otaqları birləşdirən dəhlizlərdə yerləşir. Dəhlizlər rəsmlər və fotoqrafiya nümayiş etdirmək üçün yaxşı uyğun gəlir! Beləliklə, qaydalara əməl edən turistlərin, turu başladığı otaqdan asılı olmayaraq, kifayət qədər uzun müddət gəzdikləri təqdirdə, hər dəhlizdən ən azı bir dəfə keçəcəyinə əmin olmaq istəyirik. Sizin vəzifəniz belə bir işarələmə tapmaqdır.
Məlum olur ki, hər otaqdan ən çox 3 dəhliz çıxır və bütün muzey birləşmişdir, yəni, yolda digər otaqlardan keçməklə, istənilən iki otaq arasında gəzmək mümkündür. Bir otaqdan çıxan bütün dəhlizlər müxtəlif otaqlara aparır.
Bir neçə test halı ehtiva edir. Birinci sətir test hallarının sayını t (t ≤ 100) ehtiva edir. Hər test, otaqların sayını n (3 ≤ n ≤ 10^5) ehtiva edən bir sətirlə başlayır. Növbəti n sətir bütün dəhlizlərin təsvirini ehtiva edir. Onlardan i-ci, i-ci otağı digərləri ilə birləşdirən dəhlizləri təsvir edir. O, bu otaqdakı qapıların sayını göstərən bir tam ədəd d (1 ≤ d ≤ 3) ilə başlayır, ardınca bu qapıların aparacağı otaqların nömrələrini verən d tam ədədlər r_1, r_2, ..., r_d gəlir (1 ≤ r_j ≤ n və r_j ≠ r_k əgər j ≠ k və r_j ≠ i). Bütün dəhlizlər ikitərəflidir, belə ki, əgər x otağından y otağına qapı varsa, y otağından x otağına da qapı var. Girişin ümumi ölçüsü 50 MB-dan çox olmayacaq.
Hər test halı üçün dəqiq n sətir çıxarın. Onlardan i-ci, i otağı ilə birbaşa dəhlizlərlə birləşən otaqların nömrələrini, onlara təyin edilmiş etiketlərin sırası ilə ehtiva etməlidir. Siz etibarlı qapı işarələməsinin həmişə mövcud olduğunu qəbul edə bilərsiniz, sadəcə birini tapmalısınız.
Nümunə 1