It is very easy to get lost in dense jungles, and sometimes the only way to find a way out is to wander. Fortunately, very experienced travelers have visited our jungle and have laid out paths.

There are only $$$n$$$ trees and $$$n-1$$$ paths, each of which connects two trees. Additionally, it is known that between any two trees there is exactly one route along the paths, without passing through the same path twice.

Over the past few days, $$$q$$$ people have independently found themselves in the jungle without a map or other means of navigation. You know from the rescuers' records that the $$$i$$$-th person started his journey at tree $$$s_i$$$ and wandered until he reached tree $$$t_i$$$ for the first time, where he found a note from the rescuers with a way out of the jungle.

Each of these people wandered completely randomly, looking at all possible paths he could take at each step, and choosing any of them with equal probability, reaching the other end of the path and repeating this process. The probability of moving from tree $$$u$$$ to the tree connected by a path $$$v$$$ was $$$\frac{1}{c_u}$$$, where $$$c_u$$$ is the total number of paths at tree $$$u$$$. Each of them never gave up and never stayed at the same tree, constantly walking along the paths and looking for a way out.

However, the records did not indicate how long each of these lost people wandered. To estimate this number, you need to find the expected number of steps required for each person to reach tree $$$t_i$$$ from tree $$$s_i$$$.