Masala #0174

Xotira 64 MB Vaqt 2000 ms
14
Muallif: Sirojiddin

Massiv

\(n\) ta elementdan iborat \(a\) massiv va \((x, y)\) ko'rinishidagi \(m\) ta juftliklar berilgan. Har bir \(i \space\space (1 ≤ i ≤ m)\) uchun massivni \(x_i\)- va \(y_i\)-elementlarini o'rnini almashtirish mumkin, bunda almashtirishlar soni cheklanmagan.

Sizning vazifangiz, yuqoridagi shartlarni qanoatlantirgan holda, \(a\) massivni leksikografik eng kichik holatga keltirishdan iborat.


Kiruvchi ma'lumotlar:

Birinchi qatorda ikkita butun son \(n\) va \(m\) beriladi \((1 ≤ n, m ≤ 10^5)\). Ikkinchi qatorda \(n\) ta butun son - \(a\) massiv elementlari beriladi \((1 ≤ a_i ≤ 10^9)\). Keyingi \(m\) ta qatorda esa \((x_i, y_i)\) juftliklar beriladi \((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