최종 순위

올해 어떤 프로그래밍 대회의 온라인 예선에 총 $n$개의 팀이 참가했다. 팀에는 $1$번부터 $n$번까지 번호가 붙어 있다. 놀랍게도 올해 참가한 팀들은 작년에 참가했던 팀들과 완전히 같다.

올해 예선 본부는 최종 순위를 공개하지 않기로 했다. 대신 작년과 비교했을 때 상대적인 순위가 뒤바뀐 팀들의 쌍만 발표한다. (작년에는 순위가 공개되었다.) 예를 들어 작년에는 팀 $13$이 팀 $6$보다 순위가 높았는데 올해는 팀 $6$이 팀 $13$보다 순위가 높다면, 쌍 $(6, 13)$이 발표된다.

이 정보만으로 올해 최종 순위를 복원하려고 한다. 작년 순위와 상대적인 순위가 바뀐 모든 팀 쌍의 목록이 주어졌을 때, 올해 순위를 계산하는 프로그램을 작성하여라. 단, 발표된 정보만으로는 올해 순위를 유일하게 확정할 수 없는 경우가 있을 수 있고, 정보 자체에 모순이 있어 어떤 순위로도 설명할 수 없는 경우도 있을 수 있다. 이 두 경우도 모두 판별해야 한다.

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 $100$개를 넘지 않는다. 각 테스트 케이스는 다음과 같이 구성된다.

• 팀의 수 $n$이 주어지는 한 줄. ($2 \le n \le 500$)
• $n$개의 정수 $t_1, t_2, \dots, t_n$이 주어지는 한 줄. ($1 \le t_i \le n$) $t_i$는 작년에 $i$등을 한 팀의 번호이며, $1$등이 가장 성적이 좋은 팀이다. 모든 $t_i$는 서로 다르다.
• 상대적인 순위가 바뀐 쌍의 수 $m$이 주어지는 한 줄. ($0 \le m \le 25\,000$)
• 상대적인 순위가 바뀐 두 팀의 번호 $a_i$와 $b_i$가 주어지는 $m$개의 줄. ($1 \le a_i < b_i \le n$) 같은 쌍이 두 번 이상 발표되는 경우는 없다.

각 테스트 케이스마다 다음을 출력한다.

• 올해 순위를 나타내는 $n$개의 정수를, $1$등 팀부터 순서대로 한 줄에 공백으로 구분하여 출력한다. 발표된 정보만으로 순위를 유일하게 확정할 수 없다면 대신 ?를 출력한다. 정보에 모순이 있어 어떤 순위도 정할 수 없다면 대신 IMPOSSIBLE을 출력한다.