Masala #0174

Xotira 64 MB Vaqt 2000 ms Qiyinchiligi 30 %
3.8 (Baholar 6)
14
Muallif: Sirojiddin

  

Massiv

nn ta elementdan iborat aa massiv va (x,y)(x, y) ko'rinishidagi mm ta juftliklar berilgan. Har bir i  (1im)i \space\space (1 ≤ i ≤ m) uchun massivni xix_i- va yiy_i-elementlarini o'rnini almashtirish mumkin, bunda almashtirishlar soni cheklanmagan.

Sizning vazifangiz, yuqoridagi shartlarni qanoatlantirgan holda, aa massivni leksikografik eng kichik holatga keltirishdan iborat.


Kiruvchi ma'lumotlar:

Birinchi qatorda ikkita butun son nn va mm beriladi (1n,m105)(1 ≤ n, m ≤ 10^5). Ikkinchi qatorda nn ta butun son - aa massiv elementlari beriladi (1ai109)(1 ≤ a_i ≤ 10^9). Keyingi mm ta qatorda esa (xi,yi)(x_i, y_i) juftliklar beriladi (1xi<yin)(1 ≤ x_i < y_i ≤ n).

 


Chiquvchi ma'lumotlar:

Mumkin bo'lgan leksikografik eng kichik massivni chiqaring.


Misollar
# input.txt output.txt
1
5 2
7 3 5 1 4
1 3
3 4
1 3 5 7 4 
2
4 1
1 2 3 4
1 2
1 2 3 4 
Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin