총격전

큰 총격전이 벌어진 뒤, 총이 발사된 순서를 놓고 재판이 열렸다. 다행히 총격전에 참가한 사람은 아무도 죽지 않았지만, 총이 발사된 순서에 대해서는 모두의 진술이 엇갈렸다. 총을 발사한 순서를 알아내는 것은 유죄와 무죄를 가리는 데 매우 중요하다.

각 사람의 정확한 위치는 알려져 있다. 각 사람은 총을 최대 한 발 발사했고, 소리는 공기 중에서 1초에 340미터를 이동한다. 어떤 사람 $P$가 시각 $t_P$에 총을 쏘면, 그 총소리는 위치가 $Q$인 사람에게 시각 $t_P + \frac{d(P, Q)}{340}$에 도달한다. 여기서 $d(P, Q)$는 두 사람 사이의 거리(미터)이다.

각 진술은 "S1 heard S2 firing before S3" 형태이며, 이는 사람 S1의 위치에서 S2의 총소리가 S3의 총소리보다 먼저 들렸다는 뜻이다. 즉 $t_{S2} + \frac{d(S1, S2)}{340} < t_{S3} + \frac{d(S1, S3)}{340}$ 가 성립한다.

모든 진술을 동시에 만족하는 발사 시각이 존재하고, 그때 총을 쏜 사람들의 발사 순서가 유일하게 결정되면 그 순서를 구하는 프로그램을 작성하시오.

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

각 테스트 케이스의 첫째 줄에는 총격전에 연루된 사람의 수 $n$ ($2 \le n \le 100$)과 진술의 수 $m$ ($1 \le m \le 1000$)이 주어진다.

다음 $n$개 줄에는 각 사람의 이름 $S$와 위치 좌표 $x$, $y$가 주어진다. 이름은 최대 20글자이며 알파벳 대소문자로만 이루어진다. 좌표의 단위는 미터이고, 두 사람이 같은 위치에 있는 경우는 없다.

다음 $m$개 줄에는 각 진술이 "S1 heard S2 firing before S3" 형태로 주어진다. S1, S2, S3은 사람의 이름이며 $S2 \ne S3$이다.

어떤 사람이 어떤 진술에서도 S2나 S3으로 언급되지 않았다면, 그 사람은 총을 쏘지 않은 것으로 본다.

테스트 데이터는 거리 계산에서 $10^{-7}$ 미만의 오차가 정답을 바꾸지 않도록 만들어져 있다.

각 테스트 케이스마다 한 줄에 답을 출력한다. 총을 쏜 사람들의 발사 순서가 유일하게 결정되면, 그 사람들의 이름을 발사한 순서대로 공백 하나로 구분하여 출력한다. 가능한 순서가 여러 가지이면 "UNKNOWN"을, 모든 진술을 동시에 만족하는 순서가 존재하지 않으면 "IMPOSSIBLE"을 출력한다.