Lirili Larila

문제

Sokrat: Reci Platone, slažeš li se sa mnom oko ovoga: najjači borci su oni leteći, poput Bombardira Crocodilla ili Bombombinija Gusinija.

Platon: To naprosto nije tako. Kopneni borci, poput Brr Brr Patapima ili Tung Tung Tung Sahura postigli su svoje rezultate usprkos tome što nemaju mogućnost letenja.

Sokrat: Smatram da je jedini način da dođemo do istine da pustimo borce da se bore te da odredimo ishod na temelju toga.

Platon: Bravo Sokrate, slažem se da ćemo tako doći do istine.

Odlučujuća borba odvijat će se na povezanom grafu s $NN$ čvorova i $MM$ bridova. Lirili Larila, polu slonica polu kaktus, vlasnica je grafa pa će osigurati da je riječ o njezinoj najdražoj vrsti grafa: kaktus grafu. Za potrebe ovog zadatka, kaktus graf definiramo kao jednostavan povezani graf u kojem svaki čvor pripada najviše jednom ciklusu.

Borba se odvija na sljedeći način. Na početku, svi leteći borci smješteni su u određenom početnom čvoru, a svi kopneni borci smješteni su u nekom drugom početnom čvoru. Kako se borba odvija, borci šire svoj utjecaj na graf te nastoje pokoriti što više čvorova. U konačnici, čvor će biti pokoren od strane ili letećih ili kopnenih boraca, ovisno o tome je li udaljenost toga čvora bliža početnom čvoru letećih boraca ili početnom čvoru kopnenih boraca. Čvorovi koji se nalaze na jednakoj udaljenosti od početnih čvorova letećih i kopnenih boraca predstavljaju veliki izazov za obje skupine boraca pa oni ostaju nepokoreni.

Lirili Larila želi namjestiti ishod borbe. Naime, ona je već unaprijed odredila prirodne brojeve $AA$ i $BB$, koji predstavljaju broj pokorenih čvorova redom od strane letećih i kopnenih boraca. Pomozite ovoj umiljatoj kaktus-slonici da odabere početne čvorove za obje vrste boraca tako da na kraju borbe brojevi pokorenih čvorova odgovaraju brojevima $AA$ i $BB$.

Dodatno, potrebno je napraviti takav odabir za $TT$ različitih situacija.

입력

U prvom je retku prirodni broj $TT$, broj različitih situacija.

U sljedećim retcima slijede redom opisi situacija. Svaki opis zadan je u sljedećem formatu.

U prvom su retku prirodni brojevi $NN$, $MM$, $AA$ i $BB$, redom broj čvorova i broj bridova u danom kaktus grafu te brojevi pokorenih čvorova redom od strane letećih i kopnenih boraca.

U sljedećih $MM$ redaka nalaze se parovi brojeva $aa$ i $bb$ (1 ≤ a, b ≤ N, $a\mathrm{\ne }ba\; \backslash ne\; b$), redom bridovi grafa.

Dani graf bit će kaktus graf, to jest jednostavan povezani graf u kojem svaki čvor pripada najviše jednom ciklusu.

Testni podaci će biti takvi da je uvijek moguće pronaći izbor početnih čvorova koji zadovoljava uvjete zadatka.

출력

Ispišite $TT$ redaka, po jedan za svaku situaciju.

U $ii$-tom retku ispišite dva prirodna broja odvojena razmakom, koji predstavljaju oznake početnih čvorova letećih i kopnenih boraca, željeni odabir za $ii$-tu situaciju. Ukoliko postoji više rješenja, ispišite bilo koje.

힌트

Pojašnjenje prvog probnog primjera: Leteći borci pokore čvorove 4, 5 i 6, a kopneni čvor 3. Čvorovi 1 i 2 ostaju nepokoreni.

Pojašnjenje drugog probnog primjera: Leteći borci pokore čvorove 1, 2 i 4, a kopneni čvorove 5 i 6. Čvor 3 ostaje nepokoren.

Pojašnjenje trećeg probnog primjera: Leteći borci pokore čvorove 4, 5 i 6, a kopneni čvorove 1, 2 i 3. Ne postoje nepokoreni čvorovi.

1
6 5 3 1
1 2
2 3
2 4
4 5
5 6

4 3

1
6 6 3 2
1 2
2 3
3 4
4 1
3 5
5 6

1 6

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

4 2