Індіана Джонс і програний Кубок з футболу

У 1930 році в Уругваї відбувся перший чемпіонат світу з футболу, де Уругвай здобув перемогу в драматичному фіналі проти Аргентини. Це сталося багато років тому, і тепер навколо цього історичного чемпіонату світу існує безліч міфів та легенд. Деякі навіть вважають, що оригінальний кубок, вручений Уругваю за перемогу, має міфічну силу, здатну допомогти будь-якій команді виграти чемпіонат світу.

Зараз ця оригінальна чаша загублена в часі. Хоча її міфічна сила, ймовірно, лише казка, вона залишається важливим артефактом, якому місце в музеї. Очевидно, що для її відновлення потрібен спеціаліст.

Відомий археолог і шукач пригод Індіана Джонс взяв на себе цю небезпечну місію і вирушив до Уругваю, щоб знайти чашу. Його пошуки привели його до стародавньої підземної системи печер, де, за чутками, була схована чаша. У цих печерах приховано безліч пасток, і лише його інстинкт та вірний батіг врятували Інді від вірної смерті. Тепер він досяг загадкових величезних воріт і може лише припускати, що чаша, ймовірно, схована за цими воротами. На жаль, вони зачинені.

Ворота оснащені перемикачами і важелями, всі вони позначені літерами і цифрами. Як ви вже здогадалися, ворота відкриються лише тоді, коли перемикачі і важелі будуть активовані в правильному порядку, але будьте обережні! — Якщо хтось помилиться в порядку, його чекає загибель.

На щастя, під час дослідження печер Інді знайшов кілька зашифрованих підказок, які вказують на правильну послідовність дій. Ось одна з них: "Правовірні знають, що $X$ передує $O$". І ще: "Ні за яких обставин не можна чіпати $a$, якщо $b$ не переміщено"! Очевидно, що ці підказки вказують на правильний порядок, але тут багато перемикачів і важелів, а також багато підказок. Інді потрібна допомога!

Маючи всі підказки, які зібрав Інді, чи зможеш ти допомогти йому визначити правильний порядок важелів і перемикачів, щоб він зміг успішно завершити свою пригоду? Але будьте обережні — Інді міг пропустити деякі підказки; або, можливо, він неправильно витлумачив деякі з них. У першому випадку, швидше за все, залишиться більше однієї можливої послідовності, а в другому взагалі не буде можливої послідовності. Ви повинні виявити ці випадки і попередити Інді.

Вхідні дані

Перший рядок містить кількість тестів $t(t\le 30)$. Для кожного тесту є один рядок з кількістю $n(1\le n\le 10^4)$ перемикачів/важелів на воротах і числом $h(0\le h\le 10^5)$ підказок, які знайшов Інді. Потім слідують $h$ рядків, по одному для кожної підказки, з числами $a$ і $b(1\le a,b\le n,a\ne b)$, що означають, що необхідно потягнути важіль $a$ перед тим, як важіль $b$.

Вихідні дані

Для кожного тесту виведіть один рядок з правильною послідовністю чисел від $1$ до $n$. Якщо можливої послідовності немає, то виведіть recheck hints. Якщо ж існує кілька можливих послідовностей, то виведіть missing hints.

Приклади