D. Бяцхан заан ба эвдэрсэн эрэмбэлэлт

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Бяцхан заан $1$-c $n$ хүртэлх тоонуудын сэлгэмэлд маш их дуртай. Гэхдээ тэр эдгээрийг эрэмбэлэх дуртай. Сэлгэмэлийг эрэмбэлэхийн тулд бяцхан заан зарим элементүүдийг давталттайгаар байрыг нь солино. Үр дүнд нь тэр $1, 2, 3, ..., n$ сэлгэмэлийг хүлээж авах ёстой.

Энэ удаад бяцхан заанд $p_{1}, p_{2}, ..., p_{n}$ сэлгэмэл байна. Үүнийг эрэмбэлэх програм $m$ үйлдэл хийх шаардлагатай ба $i$-р үйлдлийн үед програм $a_{i}$ ба $b_{i}$ байрлалд байгаа элементүүдийг солино. Гэвч бяцхан зааны эрэмбэлэлтийн програм муудсан ба одоо алхам бүрт програм нэг бол юу ч хийхгүй эсвэл шаардлагатай элементүүдийг солино.

Одоо бяцхан заан програм сэлгэмэлийг эрэмбэлэнэ гэдэгт итгэхгүй байгаа боловч тэр хэрвээ программыг ажиллуулаад нэг сэлгэмэлтэй боллоо гэхэд эрэмбэлэлтийн үр дүн эрэмбэлэгдсэн сэлгэмэлтэй хэр төстэй байх бол гэж бодож байна. Үүний тулд программын бүх үйлдэл дууссаны дараа сэлгэмэлд буруу байрласан хэдэн тоо байхыг бүх тохиолдолд тооцоолж дундаж утгыг олоход нь бяцхан заанд туслана уу.

Бид $p_{1}, p_{2}, ..., p_{n}$ сэлгэмэлд байгаа $i, j$ $(1 ≤ i < j ≤ n)$ хос бүхэл тоонуудыг хэрвээ дараах нөхцөл биелэж байвал энэ хосыг буруу байрласан гэж үзнэ: $p_{i} > p_{j}$.

Оролт

Эхний мөрөнд хоёр бүхэл тоон утга $n$ ба $m$ $(1 ≤ n, m ≤ 1000, n > 1)$ байх ба сэлгэмэлийн хэмжээ ба үйлдлийн тоо байна. Хоёр дахь мөрөнд $n$-с хэтрэхгүй $n$ ялгаатай бүхэл тоон утга байх ба анхны сэлгэмэл байна. Дараагийн $m$ мөр бүрт хоёр бүхэл тоон утга агуулна: $i$-р мөрөнд $a_{i}$ ба $b_{i}$ $(1 ≤ a_{i}, b_{i} ≤ n, a_{i} ≠ b_{i})$ тоонууд байх ба $i$-р үйлдлийн үеэр солигдох элементүүдийн байрлал байна.

Гаралт

Бодлогын хариу болох бодит тоог нэг мөрөнд хэвлэ. Хариултын харьцангуй болон үнэмлэхүй алдаа нь $10^{ - 6}$-с хэтрэхгүй байвал зөвд тооцогдоно.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
2 1
1 2
1 2
Гаралт
0.500000000
Оролт
4 3
1 3 2 4
1 2
2 3
1 4
Гаралт
3.000000000
Сэтгэгдлүүдийг ачааллаж байна...