ICPC
Uzun illərdir ki, ICPC adlı sirli bir kult mövcuddur. Şahidlərin dediyinə görə, bu kultun üzvləri çox qəribə işlərlə məşğuldurlar. Onlar üç nəfərlik qruplara bölünərək, anlaşılmaz bir paneldə qruplaşdırılmış düymələrə güclü şəkildə basaraq, işıq saçan bir ekrana ibadət edirlər. Bu ünsiyyət birtərəfli deyil - bəzən "tanrı" cavab olaraq razılıq işarələri verir və bu zaman xidmətçilərin sevinc dolu qışqırıqları eşidilir. Lakin, əksər diqqətsiz xidmətçilər üçün bu vəziyyət çox nadir hallarda baş verir. Çox vaxt "tanrı" narazı qalır ki, bu da ibadət edənləri əvvəlcə çaşqınlığa, sonra isə kədərə salır.
"Tanrı"nın təbiəti haqqında müxtəlif şayiələr dolaşır. Bəziləri iddia edir ki, "tanrı" bir çox təcəssümlərdə mövcuddur və hər biri xüsusi bir şəxs (bəlkə də bu şəxs deyil, daha yüksək səviyyəli bir varlıq) - Admin tərəfindən idarə olunur. Xüsusilə Böyük Saqqallı Admin adlı biri məşhur olmuşdur. Həmçinin, çoxdan bəri "tanrı"nın kefirə xüsusi bir meyli olduğu haqqında şayiələr dolaşır... Amma bu artıq bir cəfəngiyyatdır və biz də mövzudan uzaqlaşdıq.
İndi isə əsl məsələyə keçək. Bir gün N ICPC kultunun xidmətçiləri bir araya gəlib qərara gəldilər ki, ənənəvi ibadət metodları köhnəlib, bezdirib və ümumiyyətlə, o qədər də qorxunc deyil. Onlar qərara gəldilər ki, klaviaturaya güclü şəkildə vurmaq əvəzinə qaranlıq enerji mübadiləsi etməlidirlər. Bir plan hazırlandı - M cütlükdən (A, B) ibarət bir çoxluq, bu o deməkdir ki, A nömrəli xidmətçi B nömrəli xidmətçiyə enerji ötürməlidir (müvafiq olaraq, B nömrəli xidmətçi A nömrəli xidmətçidən enerji almalıdır).
Onlar plana uyğun hərəkət etməyə başladılar, amma enerji nədənsə ötürülmədi. Özünüz də başa düşürsünüz ki, problem heç cür ICPC xidmətçilərinin heç bir qaranlıq enerjiyə malik olmamasında ola bilməz! Xidmətçilər də bunu başa düşürdülər. Bir müddət sonra anladılar ki, planın işləməsi üçün müəyyən bir şəkildə yerləşməlidirlər. Onlar sehrli bir dairə çəkdilər və onun sərhədində yerləşdilər.
Əlbəttə, dairənin mövcudluğu kifayət deyil, enerji ötürmə prosesinin dairə ilə əlaqələndirilməsi də lazımdır. Ümumiyyətlə məlumdur ki, enerji ötürməsi dairə ilə əlaqələndirilir, əgər hər bir xidmətçi enerjini dairədə (saat əqrəbi istiqamətində) birbaşa ondan sonra gələn xidmətçilərə ötürürsə və enerjini dairədə birbaşa ondan əvvəl gələn xidmətçilərdən alırsa.
Bunu daha rəsmi şəkildə müəyyən edək. Gəlin next(X) - dairədə (saat əqrəbi istiqamətində) X xidmətçisindən dərhal sonra gələn xidmətçinin nömrəsi, prev(X) - dairədə X xidmətçisindən dərhal əvvəl gələn xidmətçinin nömrəsi olsun. i > 1 üçün next^i(X) = next(next^{i-1}(X)) və prev^i(X) = prev(prev^{i-1}(X)) böyüklüklərini müəyyən edək (həmçinin next^1(X) = next(X) və prev^1(X) = prev(X) olduğunu qəbul edəcəyik). Enerji ötürməsi sehrli dairə ilə əlaqələndirilir, əgər hər bir xidmətçi üçün aşağıdakı şərtlər yerinə yetirilirsə:
o, enerjini next^i(X) xidmətçilərinə ötürür, 1 ≤ i ≤ A, burada A - enerjini ötürdüyü xidmətçilərin ümumi sayıdır;
o, enerjini prev^i(X) xidmətçilərindən alır, 1 ≤ i ≤ B, burada B - enerjini aldığı xidmətçilərin ümumi sayıdır.
Hədəf heç vaxt bu qədər yaxın olmamışdı, amma ICPC xidmətçiləri toplaşaraq enerji ötürməsinin sehrli dairə ilə əlaqələndirilməsinə nail olmaq üçün dairə şəklində yerləşə bilmədilər. ICPC kultunun qardaşları olaraq, əlbəttə ki, onlara kömək etmək üçün maksimum səy göstərəcəksiniz!
Giriş verilənləri
Giriş faylı bir neçə testdən ibarətdir. Faylın ilk sətirində onların sayı T qeyd olunub, sonra isə T testin təsviri gəlir.
Hər bir testin təsviri N və M ədədlərini ehtiva edən bir sətirlə başlayır. Sonra enerji ötürmə planını təsvir edən M sətir gəlir. Bu sətirlərin hər biri iki tam ədəd - A və B ehtiva edir. Xidmətçilər 1 -dən N -ə qədər nömrələnmişdir.
Giriş faylındakı bütün ədədlər tam ədədlərdir. N ≥ 3. Bir fayldakı bütün testlər üzrə N dəyərlərinin cəmi 100 000 -i keçmir. Bir fayldakı bütün testlər üzrə M dəyərlərinin cəmi 200 000 -i keçmir. 1 ≤ A, B ≤ N. A ≠ B. Bir test daxilində hər bir cütlük (A, B) bir dəfədən çox olmur. Bir test daxilində eyni zamanda həm (A, B) həm də (B, A) cütlükləri mövcud ola bilməz.
Çıxış verilənləri
Giriş faylındakı hər bir test üçün 1 -dən N -ə qədər olan ədədlərin bir permutasiyasını çıxarın - xidmətçilərin sehrli dairə ilə əlaqələndirilmiş enerji ötürməsinə nail olmaq üçün necə yerləşməli olduqlarını göstərən sıra. Çıxarılan sıra dairənin saat əqrəbi istiqamətində keçilməsinə uyğun olmalıdır. Əgər bir neçə həll yolu varsa, onlardan hər hansı birini çıxarın. Əgər həll yolu yoxdursa, "Epic fail" (tırnaq işarələri olmadan) çıxarın.