C. Фое хосууд

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

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

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

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

Танд $n$ урттай $p$ сэлгэлт өгөгджээ. Мөн танд $m$ фое хосууд $(a_{i}, b_{i})$ ($1 ≤ a_{i}, b_{i} ≤ n, a_{i} ≠ b_{i}$) өгөгдөв.

Таны даалгавар бол ямар ч фое хосууд агуулаагүй байх ялгаатай $(x, y)$ ($1 ≤ x ≤ y ≤ n$) завсруудын тоог тоолох юм. Тиймээс та нэг фое хос дотроо агуулсан байлаа ч $(x, y)$ завсрыг тоолох ёсгүй юм (фое хосын утгуудын байрлал болон дараалал нь чухал биш).

Жишээ авч үзье: $p = [1, 3, 2, 4]$ болон ${(3, 2), (4, 2)}$ фое хосууд байв. $(1, 3)$ завсар нь буруу учир нь уг завсар нь $(3, 2)$ фое хосыг агуулж байна. $(1, 4)$ завсар нь мөн л буруу учир нь уг завсар нь 2 фое хосууд $(3, 2)$ болон $(4, 2)$-г агуулна. Гэхдээ $(1, 2)$ завсар нь зөв учир нь энэ нь ямар ч фое хос агуулаагүй байна.

Оролт

Эхний мөрөнд $p$ сэлгэлтийн урт болон фое хосуудын тоог илэрхийлэх 2 бүхэл тоо $n$ болон $m$ ($1 ≤ n, m ≤ 3*10^{5}$) өгөгдөнө.

2-дахь мөрөнд $p$ сэлгэлтийн элементүүд болох $n$ ширхэг ялгаатай бүхэл тоо $p_{i}$ ($1 ≤ p_{i} ≤ n$)-ууд өгөгдөнө.

Дараагийн $m$ мөрийн мөр болгонд 2 бүхэл тоо $(a_{i}, b_{i})$ ($1 ≤ a_{i}, b_{i} ≤ n, a_{i} ≠ b_{i}$) өгөгдөнө -- энэ нь $i$-дахь фое хосыг илэрхийлнэ. Нэг фое хос нь олон удаа өгөгдөж болохыг анхаарна уу.

Гаралт

Ямар ч фое хосууд агуулаагүй ялгаатай $(x, y)$ завсруудын тоог илэрхийлэх ганц бүхэл тоо $c$ хэвлэнэ.

Хариулт нь хэтэрхий том байж болохыг анхаарна уу, иймд та $64$-битийн бүхэл тоон төрлийг үүнийг хадгалахдаа ашиглах ёстой. $C++$ дээр та $long long$ бүхэл тоон төрлийг $Java$ дээр та $long$ бүхэл тоон төрлийг ашиглаж болно.

Орчуулсан: Баатархүү

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

Оролт
4 2
1 3 2 4
3 2
2 4
Гаралт
5
Оролт
9 5
9 7 2 3 1 4 6 5 8
1 6
4 5
2 7
7 2
2 7
Гаралт
20

Тэмдэглэл

Эхний жишээнд, хариултын завсрууд нь $(1, 1)$, $(1, 2)$, $(2, 2)$, $(3, 3)$ болон $(4, 4)$ байх юм.

Сэтгэгдлүүдийг ачааллаж байна...