인디아나 존스와 사라진 축구 트로피

1930년, 제1회 FIFA 월드컵이 우루과이에서 열렸고, 개최국 우루과이는 아르헨티나와의 극적인 결승전 끝에 우승을 차지했다. 그 후로 아주 오랜 세월이 흘러, 이제 그 첫 월드컵에는 신화와 전설이 감돌고 있다. 어떤 이들은 우루과이가 우승의 대가로 받은 원래의 우승 트로피에 신비한 힘이 깃들어 있어, 어느 팀에게든 월드컵에서 우승할 힘을 준다고까지 말한다. 그 트로피는 오래전에 사라졌고, 그 힘이 거의 틀림없이 이야기일 뿐이라 해도, 트로피는 박물관에 있어야 할 중요한 유물이다. 그것을 되찾으려면 분명 전문가가 필요하다.

유명한 고고학자이자 모험가인 인디아나 존스가 이 위험한 임무를 맡아 트로피를 찾으러 우루과이로 떠났다. 수색 끝에 그는 트로피가 숨겨져 있다고 전해지는 고대 지하 동굴로 들어서게 되었다. 동굴에는 함정이 가득했고, 오직 그의 직감과 믿음직한 채찍만이 그를 확실한 죽음에서 구해 주었다. 이제 그는 거대하고 신비로운 문 앞에 다다랐고, 트로피가 그 문 뒤에 있으리라 짐작한다. 하지만 문은 굳게 닫혀 있다.

문에는 스위치와 레버가 가득 달려 있으며, 각각에는 문자와 숫자가 적혀 있다. 짐작하겠지만, 스위치와 레버를 올바른 순서대로 조작해야만 문이 열린다. 그러나 조심하라. 순서를 하나라도 틀리면 파멸이 기다린다.

다행히 인디는 동굴을 탐험하던 중 올바른 순서에 대한 암호 같은 힌트를 여러 개 찾아냈다. 하나는 “믿는 자는 X가 O보다 먼저 온다는 것을 안다”라고 적혀 있었다. 또 다른 하나는 “Θ를 움직이기 전에는 무슨 일이 있어도 ∆를 건드리지 말라!”라고 경고했다. 이 단서들은 순서에 제약을 주지만, 스위치와 레버도 많고 단서도 많다. 인디에게는 도움이 필요하다.

인디가 모은 모든 힌트가 주어질 때, 레버와 스위치를 조작해야 하는 올바른 순서를 알아낼 수 있는가? 다만 조심하라. 인디는 어떤 힌트를 놓쳤을 수도 있고, 어떤 힌트를 잘못 해석했을 수도 있다. 힌트가 부족하면 보통 가능한 순서가 둘 이상 남고, 잘못 해석했다면 가능한 순서가 아예 없게 된다. 이 두 경우를 찾아내어 인디에게 알려 주어야 한다.

첫째 줄에 테스트 케이스의 개수 $C$ $(C \le 30)$가 주어진다.

각 테스트 케이스는 두 정수, 즉 문에 달린 스위치/레버의 개수 $n$ $(1 \le n \le 10000)$과 인디가 찾아낸 힌트의 개수 $h$ $(0 \le h \le 100000)$가 적힌 줄로 시작한다. 이어지는 $h$개의 줄에는 각각 두 정수 $a$와 $b$ $(1 \le a, b \le n,\ a \ne b)$가 주어지며, 이는 레버 $a$를 레버 $b$보다 먼저 조작해야 함을 뜻한다.

각 테스트 케이스마다 한 줄을 출력한다. 가능한 순서가 정확히 하나뿐이라면 $1$부터 $n$까지의 수를 그 순서대로 공백 하나로 구분하여 출력한다. 가능한 순서가 없다면 대신 recheck hints를 출력한다. 가능한 순서가 둘 이상이라면 대신 missing hints를 출력한다.