Төөрдөг байшин нь модоор илэрхийлэгдэнэ (хос оройн хооронд яг нэг зам байх чиглэлгүй граф). Төөрдөг байшинд орох орой болон гарах орой нь тодорхой магадлалтайгаар сонгогдоно. Төөрдөг байшингаас гарахад Гүн Эхэнд Хайлтыг ашиглана. Хэрвээ явах боломжтой хэд хэдэн зам байвал ижил магадлалтайгаар сонгогдоно. Дараах псеудо-кодыг авч үзье:

DFS(x)  
    if x == exit vertex then  
        finish search$  
    flag[x] <- TRUE  
    random shuffle the vertices' order in V(x) // here all permutations have equal probability to be chosen  
    for i <- 1 to length[V] do  
        if flag[V[i]] = FALSE then  
            count++;  
            DFS(y);  
    count++;

$V(x)$ бол $x$ оройн хөрш оройнуудын жагсаалт. $flag$ массив анх $FALSE$ утгаар дүүргэгдсэн. $DFS$ нь орох оройн параметртэй эхэлнэ. Хайлт дууссаны дараа $count$ хувьсагч үйлдлийн тоог хадгална.

Таны ажил бол төөрдөг байшингаас гарах үйлдлүүдийн тооны дунджийг олох юм.

Оролт

Эхний мөрөнд графын оройнуудын тоо $n$ ($1 ≤ n ≤ 10^{5}$) байна. Дараагийн $n - 1$ мөрөнд хос бүхэл тоон утга $a_{i}$ ба $b_{i}$ байх ба $a_{i}$ болон $b_{i}$ оройнуудын хоорондох ирмэг буюу гарцыг харуулна. Өгөгдсөн граф нь мод байна.

Дараагийн $n$ мөрөнд эерэг хос тоонууд $x_{i}$ ба $y_{i}$ байх ба харгалзан $i$-р оройн орох болон гарах оройгоор сонгогдох магадлал юм. $i$-р оройг орц эсвэл гарцаар сонгох магадлал харгалзан ба -тай тэнцүү. Бүх $x_{i}$ ба $y_{i}$-н нийлбэр эерэг ба $10^{6}$-с хэтрэхгүй.

Гаралт

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

Эхний жишээн дээр орох орой үргэлж 1 ба гарах нь үргэлж 2 байна.

Хоёр дахь жишээн дээр орох орой үргэлж 1 байх ба гарах орой нь 2/5 магадлалтайгаар 2-р орой мөн 3/5 магадлалтайгаар 3-р орой байна. Гарах орой нь 2 болон 3 байх тохиолдолд дундаж утга нь адилхан байна (ижилхэн тохиолдлууд). Эхний үйлдлийн үед гарах оройруу 0.5 магадлалтайгаар явна эсвэл гарц биш оройруу 0.5 магадлалтайгаар явна. Эхний тохиолдолд үйдлүүдийн тоо 1 байна, хоёр дахь тохиолдолд 3 байна. Нийт дундаж нь $2 / 5 × (1 × 0.5 + 3 × 0.5) + 3 / 5 × (1 × 0.5 + 3 × 0.5)$ гэж тооцогдоно.