Reytinqlər
Hər il proqramlaşdırma yarışmasında iştirak edən n komanda (etiketləndirilmiş 1-dən n-ə qədər) var və sonda onlar ləyaqət sırasına görə sıralanırlar. Keçən ilin sıralamaları məlumdur.
Bu il, münsiflər heyəti tədbiri daha az rəqabətli etmək istəyir və belə bir sıralama siyahısını dərc etməməyə qərar verir (çünki aşağıda olan komandalar ruhdan düşə bilər). Bunun əvəzinə, keçən ildən bu ilə nisbətən sıralama sırası dəyişmiş komandaların cütlərinin tam siyahısını hazırlayacaqlar. Məsələn, əgər 13 nömrəli komanda keçən il 6 nömrəli komandanın üstündə yerləşibsə, amma bu il 6 nömrəli komanda 13 nömrəli komandanın üstündə yerləşibsə, (6, 13) cütü elan edilir. Bu, komandaların müəyyən bir rəqib komandaya qarşı irəliləyişlərini izləməyə imkan verəcək, lakin onların ümumi vəziyyətlərini aydın şəkildə anlamalarına imkan verməyəcək.
Əlbəttə ki, bu, sizin komandanızın ümumi sıralama siyahısını müəyyən etməyə çalışmasına mane olmayacaq. Keçən ilin sıralamalarını və nisbətən sıralama sırası dəyişmiş komandaların cütlərinin tam siyahısını nəzərə alaraq, bu ilin sıralamalarını mümkün qədər bərpa edin. Mümkündür ki, münsiflər heyəti səhv etmiş ola bilər, buna görə də verilən məlumat bu ilin hər hansı bir mümkün sıralama siyahısı ilə uyğunsuzdursa, bunu da aşkar etməlisiniz.
Giriş verilənləri
Birinci sətirdə müsbət tam ədəd: test halların sayı, ən çox 100. Bundan sonra hər test halı üçün:
Bir sətirdə tam ədəd n (2 ≤ n ≤ 500): komandaların sayı.
Bir sətirdə n tam ədəd t_i (1 ≤ t_i ≤ n): keçən ilin sıralamaları, ən yaxşı komandadan ən pis komandaya. t_i sıralama siyahısında i mövqeyində olan komandadır (1-indeksli). Bütün t_i fərqli olacaq.
Bir sətirdə tam ədəd m (0 ≤ m ≤ 25 000): nisbətən sıralama sırası dəyişmiş cütlərin sayı.
m sətirdə iki tam ədəd a_i və b_i (1 ≤ a_i < b_i ≤ n): nisbətən sıralama sırası dəyişmiş komandaların cütü. Hər belə cüt dəqiq bir dəfə qeyd olunacaq.
Çıxış verilənləri
Hər test halı üçün:
Bir sətirdə n tam ədəd: bu ilin sıralamaları, ən yaxşıdan ən pisə, burada i-ci termin (1-indeksli) i mövqeyində olan komandadır. Əgər bu komanda dəqiq müəyyən edilə bilmirsə, tam ədəd '?' simvolu ilə əvəz olunmalıdır. Əgər müəyyən bir test halı üçün verilən məlumat bu ilin hər hansı bir mümkün sıralama siyahısı ilə uyğunsuzdursa, sətir "IMPOSSIBLE" ifadəsini ehtiva etməlidir.