Yeni səma

Це — Yalnız çıxış məsələsidir. Yəni, yalnız çıxış faylını təqdim etməlisiniz (kod yox). Göndərərkən "Plain Text" kompilyatorundan istifadə edin. Giriş testi https://static.e-olymp.com/problems/10457/input.txt linkində mövcuddur.

Marsın kolonizasiyası artıq keçmişin məsələsidir. İndi daha uzaqgörən düşünmək lazımdır. Məsələn, bizim qalaktikamızın hüdudlarından kənarda kolonizatorların qarşısına hansı problemlər çıxacaq? Yeni planetlər, yeni qitələr, yeni ulduzlu səma.

Əgər qitələrin kolonizasiyası ilə özümüzü idarə edə bilsək: hansısa bir ərazini götürüb Yeni Yeni İngiltərə adlandırarıq, orada Yeni Yeni Orlean tikərik, - ulduzlu səma ilə hər şey asan deyil. İnsanlıq həmişə yalnız bir səma ilə yaşamışdır, yaxşı, əgər yarımkürələri nəzərə alsaq, onda ikisi ilə. Və məsələn, yad səma ilə necə istiqamətlənmək olar: orada Kiçik Ayı haradadır, Cənub Xaçı haradadır və ümumiyyətlə, onlar oradadırmı, bunu heç kim bilmir.

Beləliklə, yeni səmada köhnə bürcləri axtaracağıq.

Qoy ulduzlu səma yönsüz qrafla təmsil olunsun. Ulduzlar zirvələr olacaq, və bürcləri formalaşdıra biləcək təsəvvür edilən xətlər, – kənarlar. Qoy məlum bürclər də belə qraflar olsun. Biz bürclərin siyahısını və səmanın xəritəsini təqdim edirik, siz isə bu bürcləri xəritədə tapırsınız.

Hər bir ulduz və səmanın təsəvvür edilən xətti yalnız bir bürcə aid ola bilər. Axtarılan bütün bürclər səma sferasında mövcud deyil. Axı, bu başqa qalaktikadır. Bununla belə, bəziləri bir neçə dəfə mövcud ola bilər, belə olan halda ilk uyğun yerləşməni tapmaq kifayət edəcək.

Hər bir testdə alınan balların sayı uğurla tapılmış bürclərin sayına uyğundur.

Giriş verilənləri

Birinci sətir T - testlərin sayını ehtiva edən bir tam ədəddir.

Hər bir testin birinci sətri tək tam ədəd K ehtiva edir. Sonra K+1 blok gəlir, burada ilk K blok axtarılan bürcləri təsvir edir, sonuncu isə bütün səma xəritəsini.

Hər bir blok iki sətirdən ibarətdir, birincidə iki tam ədəd: $N_i$ - qrupdakı ulduzların sayı və $M_i$ – cari qrupdakı ulduzlar arasında ümumi əlaqələrin sayı. İkinci sətir $M_i$ cüt tam ədəd ehtiva edir, burada hər bir cüt cari qrupdakı ulduzlar arasında əlaqəni təsvir edir, ulduzların nömrələnməsi sıfırdan başlayır.

Çıxış verilənləri

Hər bir test üçün əgər bu testə cavabınız varsa 1, yoxdursa 0 çıxış etməlisiniz.

Əgər cavabınız varsa, çıxış faylı K sətir ehtiva etməlidir, burada hər bir sətir müvafiq axtarılan bürcü təsvir edir (giriş məlumatlarındakı eyni ardıcıllıqla).

Sətir bürc tapılmadıqda -1, ya da cari bürcü formalaşdıran səma sferasının $N_i$ ulduzlarının nömrələrini ehtiva etməlidir. Ulduzlar axtarılan bürcün əlaqələrinin ilkin təsvirinə uyğun olan ardıcıllıqla sadalanmalıdır.

Nümunələr

1
3
4 4
0 1 1 2 2 3 3 0
3 3 
0 1 1 2 2 0
4 3
0 1 0 2 0 3
7 7
0 1 1 4 1 2 2 3 3 5 3 6 5 6

1
-1
3 5 6
1 0 2 4