Famil Door và những con đường

Một thành phố có $n$ giao lộ được nối với nhau bởi $n-1$ con đường hai chiều, tạo thành một cây (đồ thị liên thông không có chu trình). Như vậy giữa hai giao lộ bất kỳ luôn có đúng một đường đi đơn.

Thành phố có $m$ cư dân. Cư dân thứ $i$ sống ở giao lộ $u_i$ và làm việc ở giao lộ $v_i$.

Thị trưởng sẽ xây thêm đúng một con đường hai chiều mới, bằng cách chọn ngẫu nhiên đều một trong $\frac{n·(n-1)}{2}$ cặp giao lộ $(a,b)$ với $a\ne b$ (cặp được chọn có thể đã có đường nối sẵn).

Một cư dân trở nên hạnh phúc nếu sau khi xây con đường mới, tồn tại một chu trình đơn chứa cả nhà ($u_i$) lẫn nơi làm việc ($v_i$) của người đó. Khi đó niềm vui của người đó bằng độ dài của chu trình đơn ấy (số cạnh trên chu trình); có thể chứng minh rằng chu trình này là duy nhất.

Với mỗi cư dân, hãy tính kỳ vọng niềm vui của người đó, tức là kỳ vọng độ dài chu trình chứa cả $u_i$ và $v_i$, với điều kiện một chu trình như vậy tồn tại (chỉ xét những trường hợp con đường mới khiến người đó hạnh phúc).

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$ — số giao lộ và số cư dân.
• $n-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a_i$ và $b_i$ — một con đường nối giao lộ $a_i$ và $b_i$.
• $m$ dòng cuối, mỗi dòng chứa hai số nguyên $u_i$ và $v_i$ — nhà và nơi làm việc của cư dân thứ $i$.

Dữ liệu ra

In ra $m$ dòng, dòng thứ $i$ là kỳ vọng niềm vui của cư dân thứ $i$. Đáp án được coi là đúng nếu sai số tuyệt đối hoặc tương đối không vượt quá ${10}^{-6}$.

Ràng buộc

• $2\le n,m\le {10}^5$
• $1\le a_i,b_i\le n$
• $1\le u_i,v_i\le n$, $u_i\ne v_i$

Ví dụ