E. Фамил Доор ба Зам

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

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

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

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

Фамил Доорын хотын газрын зураг мод шиг (жигд бус холбогдсон чиглэлгүй граф) харагддаг ба хүмүүс Трийлэнд гэж нэрлэдэг. Хотод $n - 1$ ширхэг хоёр чиглэлтэй замаар холбогдсон $n$ огтлолцол байгаа.

Уг хотод Фамил Доорын $m$ найз амьдардаг. $i$-р найз нь $u_{i}$ огтлолцолд амьдарч $v_{i}$ огтлолцол дээр ажилладаг. Хотын иргэн бүр баяр хөөргүй байгаа учир нь тэдний гэр болон ажлын хооронд ганц л энгийн зам байдаг.

Фамил Доор яг нэг шинэ зам барихаар төлөвлөсөн ба $n*(n - 1) / 2$ боломжоос нэгийг нь санамсаргүйгээр сонгоно. Тэр аль хэдийн нэг замаар холбогдсон хоёр хотын хооронд ч шинэ замаа барьж магадгүй.

Хэрвээ Фамил Доор замаа барьсаны дараа нэг найз нь ажлаасаа гэр хүртэл, гэрээсээ ажил хүртэл нэг замаар биш өөр өөр замаар явах юм бол тэр найз нь баяртай байх болно гэдгийг мэднэ. $u_{i}$ болон $v_{i}$ хоёуланг нь агуулсан энгийн цигл үүснэ гэсэн үг.

Түүгээр ч барахгүй хэрвээ найз нь баяртай болох юм бол түүний таашаал зам шигээ урт болох юм(үүнийг харахад амархан ба давтагдахгүй). Фамил Доор найз бүрийнхээ хувьд таашаалынх нь дундаж утгыг олохыг хүсч байна. Энэ нь $u_{i}$ болон $v_{i}$ хоёуланг нь агуулсан ганц цикл байна гэж бодоход уг циклийн дундаж урт юм.

Оролт

Оролтын эхний мөрөнд бүхэл тоон утгууд болох $n$ ба $m$ ($2 ≤ n,  m ≤ 100 000$) байх ба Трийлэнд дахь огтлолцолын тоо болон Фамил Доор-н найзуудын тоо юм.

Дараагийн $n - 1$ ширхэг мөр нь хоёр чиглэлтэй замуудыг тодорхойлно. Мөр бүрт хоёр бүхэл тоон утга $a_{i}$ ба $b_{i}$ ($1 ≤ a_{i}, b_{i} ≤ n)$ байх ба $i$-р замаар холбогдсон огтлолцолуудын индексүүд юм.

Сүүлийн $m$ мөрөнд Фамил Доор-н найзуудыг тодорхойлно. Эдгээр мөрүүдийн $i$-р мөр бүр нь хоёр бүхэл тоон утга $u_{i}$ ба $v_{i}$ ($1 ≤ u_{i}, v_{i} ≤ n, u_{i} ≠ v_{i}$) агуулах ба $i$-р найзын амьдардаг болон ажилладаг огтлолцолуудын дугаар юм.

Гаралт

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

Өөрөөр хэлбэл: Таны хариултыг $a$ гэж үзвэл, шалгагчийн хариу $b$. Шалгагч программ таны хариултыг хэрвээ . бол зөв гэж авч үзнэ.

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

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

Оролт
4 3
2 4
4 1
3 2
3 1
2 3
4 1
Гаралт
4.00000000
3.00000000
3.00000000
Оролт
3 3
1 2
1 3
1 2
1 3
2 3
Гаралт
2.50000000
2.50000000
3.00000000

Тэмдэглэл

Хоёр дахь жишээний хувьд авч үзье.

  1. $(1, 2)$ болон $(2, 3)$ хоёр зам байж болох ба дундаж утга нь
  2. $(1, 3)$ ба $(2, 3)$ замууд хоёр дахь найзыг баяртай болгоно. Ингээд дундаж утга нь $1$-р найзтай адил $2.5$
  3. Гурав дахь найзыг баяртай болгох ганц зам бол $(2, 3)$ замыг нэмэх бөгөөд хариулт нь $3$ болно.
Сэтгэгдлүүдийг ачааллаж байна...