Индиана Джонс и проигранный Кубок по футболу

В 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.

Примеры