B. Хүүхэд ба амьтны хүрээлэн

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

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

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

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

Мэдээж хэрэг бидний хүүхэд амьтны хүрээлэнгээр алхах дуртай. Амьтны хүрээлэн $1$-ээс $n$ хүртэл дугаарлагдсан $n$ хэсэгтэй. $i$-р хэсэг нь $a_{i}$ амьтантай. Мөн энэ амьтны хүрээлэн $m$ замтай ба зам бүр нь хоёр ялгаатай хэсгийг холбосон байна. Мэдээж амьтны хүрээлэн холбогдсон ба бусад хэсгээс замыг ашиглан аль нэг хэсэг рүү очиж чадна.

Хүүхэд маань маш ухаалаг. Хүүхэд $p$ хэсгээс $q$ хэсэгрүү явах хүсэлтэй байна гэж төсөөлж үзье. Эхлээд тэр $p$-ээс $q$ хүрэх чиглэлд бүгдийг нь үзсэн. Хүүхэд үзэх замдаа тоо бичдэг, уг тоо нь тухайн хэсгийн амьтдын хамгийн бага тоотой тэнцүү юм. Эдгээрээс хамгийн их бичигдсэн тоог $f(p, q)$ гэж үзье. Эцэст нь тэр $f(p, q)$ бичигдсэн тоонуудаас нэгийг сонгосон.

Дараа нь хүүхэд амьтны хүрээлэнд очоод, асуултын талаар бодсон: Бүх $p, q$ $(p ≠ q)$ хосын $f(p, q)$-ийн дундаж утга ямар байх бол? Та түүнд зөв хариултыг хэлж чадах уу?

Оролт

Эхний мөрөнд $n$ ба $m$ ($2 ≤ n ≤ 10^{5}$; $0 ≤ m ≤ 10^{5}$) хоёр бүхэл тоо байна. Хоёрдугаар мөрөнд $n$ ширхэг бүхэл тоо: $a_{1}, a_{2}, ..., a_{n}$ ($0 ≤ a_{i} ≤ 10^{5}$) байна. Дараа нь $m$ мөр байх ба, мөр бүр хоёр бүхэл $x_{i}$, $y_{i}$ ($1 ≤ x_{i}  y_{i} ≤ n$; $x_{i} ≠ y_{i}$) тоог агуулна. $x_{i}$, $y_{i}$ хэсгүүдийн хоорондох зам.

Бүх зам хоёр чиглэлтэй, хэсэг бүр нь нэгээс илүү замаар холбогдсон

Гаралт

Гаралт нь -ийн утга бодит тоо байна.

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

Орчуулсан: Даариймаа

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

Оролт
4 3
10 20 30 40
1 3
2 3
4 3
Гаралт
16.666667
Оролт
3 3
10 20 30
1 2
2 3
3 1
Гаралт
13.333333
Оролт
7 8
40 20 10 30 20 50 40
1 2
2 3
3 4
4 5
5 6
6 7
1 4
5 7
Гаралт
18.571429

Тэмдэглэл

Эхний жишээ. $12$ үед:

  • $p = 1, q = 3, f(p, q) = 10$.
  • $p = 2, q = 3, f(p, q) = 20$.
  • $p = 4, q = 3, f(p, q) = 30$.
  • $p = 1, q = 2, f(p, q) = 10$.
  • $p = 2, q = 4, f(p, q) = 20$.
  • $p = 4, q = 1, f(p, q) = 10$.

Өөрөөр $6$ үед дээрх нь ижил байна. Дундаж нь .

Хоёр дахь жишээг авч үзье. $6$ боломжит нөхцөл байна:

  • $p = 1, q = 2, f(p, q) = 10$.
  • $p = 2, q = 3, f(p, q) = 20$.
  • $p = 1, q = 3, f(p, q) = 10$.

Өөрөөр $3$ үед тэгш хэмтэй байна. Дундаж нь .

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