Рейтинги#2453

Рейтинги

1 секунда

64 мегабайти

Середня

Є $n$ команд (пронумерованих від $1$ до $n$ ), які щороку беруть участь у змаганні з програмування, і в кінці їх ранжують за заслугами. Відомо результати минулого року.

Цього року журі вирішило зробити захід менш конкурентним і не публікувати повний рейтинг (оскільки команди, які опинилися внизу, можуть бути засмучені). Натомість вони оприлюднять повний список пар команд, для яких порядок у рейтингу змінився порівняно з минулим роком. Наприклад, якщо команда $13$ була вище за команду $6$ минулого року, але цього року команда $6$ опинилася вище за команду $13$ , оголошується пара $(6, 13)$ . Це дозволяє командам відстежувати свій прогрес відносно окремих суперників, але не дає можливості повністю відновити загальний рейтинг.

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

Вхідні дані

Перший рядок містить додатне ціле число: кількість тестових випадків, не більше $100$ . Далі для кожного тесту:

Один рядок з цілим числом $n$ ( $2 \leq n \leq 500$ 2 \le n \le 500): кількість команд.
Один рядок з $n$ цілими числами $t_{i}$ t_i ( $1 \leq t_{i} \leq n$ 1 \le t_i \le n): минулорічний рейтинг від найкращої до найгіршої. $t_{i}$ t_i — команда, яка зайняла позицію $i$ (нумерація з 1) у рейтингу. Всі $t_{i}$ t_i різні.
Один рядок з цілим числом $m$ ( $0 \leq m \leq 25000$ 0 \le m \le 25\ 000): кількість пар, для яких порядок змінився.
$m$ рядків з двома цілими числами $a_{i}$ a_i і $b_{i}$ b_i ( $1 \leq a_{i} < b_{i} \leq n$ 1 \le a_i < b_i \le n): пара команд, для яких порядок у рейтингу змінився. Кожна така пара зустрічається рівно один раз.

Вихідні дані

Для кожного тесту:

Один рядок з $n$ цілими числами: цьогорічний рейтинг від найкращої до найгіршої, де $i$ -те значення (нумерація з 1) — команда, що зайняла $i$ -ше місце. Якщо команду неможливо визначити однозначно, замініть число символом '?'. Якщо дані узгодити неможливо з жодним рейтингом цього року, виведіть рядок "IMPOSSIBLE".

Приклади

Приклад 1