Siqaret tüstüsü#4014
Andy: "Billy the Kid birinci atəş açdı!"
Larry: "Xeyr, mən əminəm ki, ilk atəş John tərəfindən gəldi!"
Böyük atışmadan sonra köhnə vəhşi qərbdə bir məhkəmədə mübahisələr davam edirdi. Möcüzəvi şəkildə, hər kəs sağ qalmışdı (baxmayaraq ki, ciddi yaralanmalar var idi), lakin atəşlərin dəqiq ardıcıllığı barədə heç kim razılaşa bilmirdi. Hər kəsin ən çox bir atəş açdığı məlum idi, lakin hər şey çox sürətlə baş vermişdi. Atəşlərin dəqiq ardıcıllığını müəyyənləşdirmək günah və cəzaların təyin edilməsi üçün vacib idi.
Amma sonra şerif, Willy the Wise, müdaxilə etdi: "Baxın, atışma vaxtında çəkilmiş peyk görüntüm var, hər kəsin harada yerləşdiyini dəqiq göstərir. Məlum oldu ki, Larry John-a Billy the Kid-dən daha yaxın idi, Andy isə John-a Billy the Kid-dən bir az daha yaxın idi. Beləliklə, səs saniyədə 340 metr sürətlə yayıldığı üçün Larry, Billy the Kid birinci atəş açsa belə, John-un atəşini birinci eşitmiş ola bilər. Amma Andy, John-a Billy the Kid-dən daha yaxın olsa da, Billy the Kid-in atəşini birinci eşitdi – beləliklə, biz dəqiq bilirik ki, Billy the Kid birinci atəş açan idi!
Sizin vəzifəniz yuxarıdakı kimi vəziyyətlərdə atəşlərin dəqiq ardıcıllığını müəyyən edən bir proqram yazmaqdır.
Birinci sətirdə müsbət tam ədəd: test hallarının sayı, ən çox 100. Bundan sonra hər test halı üçün:
bir sətir iki tam ədəd ilə n (2 ≤ n ≤ 100) və m (1 ≤ m ≤ 1000): iştirak edən insanların sayı və müşahidələrin sayı.
n sətir bir sətir S, ən çox 20 kiçik və böyük hərflərdən ibarət, və iki tam ədəd x və y (0 ≤ x,y ≤ 1000000): bir şəxsin unikal identifikatoru və onun Kartes koordinatlarında mövqeyi, mənşədən metrlərlə.
m sətir "S1 S2-nin S3-dən əvvəl atəş açdığını eşitdi" formasında, burada S1, S2 və S3 iştirak edən şəxslərin identifikatorlarıdır və S2 ≠ S3.
Əgər bir şəxs heç vaxt S2 və ya S3 kimi qeyd olunmayıbsa, bu şəxs heç vaxt atəş açmamış və yalnız şahid kimi çıxış etmişdir. Heç iki şəxs eyni mövqedə yerləşmir. Test halları elə qurulub ki, bir məsafə hesablamasında 10^{-7}-dən az səhv çıxışa təsir etməyəcək.
Hər test halı üçün:
müşahidələrlə uyğun olan atəş açanların ardıcıllığını bir sətirdə, identifikatorlar arasında tək boşluq ilə formatlaşdırılmış şəkildə.
Əgər bir neçə fərqli ardıcıllıq mümkün olarsa, "UNKNOWN" çıxış edin. Əgər heç bir ardıcıllıq müşahidələrlə uyğun deyilsə, "IMPOSSIBLE" çıxış edin.
Nümunə 1