Доказ, що викриває#4014
Енді: "Біллі Кід стріляв першим!"
Ларрі: "Ні, я впевнений, що перший постріл був від Джона!"
Суперечки тривали під час суду після великої перестрілки десь на старому дикому заході. Дивом усі вижили (хоча були серйозні поранення), але ніхто не міг погодитися щодо точної послідовності пострілів. Було відомо, що кожен зробив не більше одного пострілу, але все сталося дуже швидко. Визначення точної послідовності пострілів було важливим для встановлення вини та покарань.
Але тоді шериф, Віллі Мудрий, втрутився: "Дивіться, у мене є супутникове зображення з моменту стрілянини, яке показує, де саме знаходився кожен. Виявляється, Ларрі був розташований набагато ближче до Джона, ніж до Біллі Кіда, тоді як Енді був трохи ближче до Джона, ніж до Біллі Кіда. Таким чином, оскільки звук поширюється з кінцевою швидкістю 340 метрів на секунду, Ларрі міг почути постріл Джона першим, навіть якщо Біллі Кід стріляв першим. Але, хоча Енді був ближче до Джона, ніж до Біллі Кіда, він почув постріл Біллі Кіда першим – отже, ми точно знаємо, що Біллі Кід стріляв першим!
Ваше завдання - написати програму, яка визначить точну послідовність пострілів у подібних ситуаціях.
На першому рядку позитивне ціле число: кількість тестових випадків, не більше . Після цього для кожного тестового випадку:
один рядок з двома цілими числами (2 \le n \le 100) та (1 \le m \le 1000): кількість людей, які беруть участь, та кількість спостережень.
рядків з рядком , що складається з до літер верхнього та нижнього регістрів, та двома цілими числами та (0 \le x, y \le 1000000): унікальний ідентифікатор для людини та її положення в декартових координатах, у метрах від початку координат.
рядків у формі "S1 heard S2 firing before S3", де S1, S2 та S3 є ідентифікаторами серед залучених людей, і S2 \ne S3.
Якщо про людину ніколи не згадувалося як про S2 або S3, то можна вважати, що ця людина ніколи не стріляла, а лише була свідком. Жодні дві особи не знаходяться в одній позиції. Тестові випадки сконструйовані так, що похибка менше 10^{-7} у розрахунку відстані не вплине на результат.
Для кожного тестового випадку:
один рядок з порядком стрільців, який сумісний з усіма спостереженнями, відформатований як ідентифікатори, розділені пробілами.
Якщо можливі кілька різних порядків, виведіть "UNKNOWN". Якщо жоден порядок не сумісний зі спостереженнями, виведіть "IMPOSSIBLE".
Приклад 1