Masala #0174

\(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.

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)\).

Mumkin bo'lgan leksikografik eng kichik massivni chiqaring.