MianKing has a tree with nodes. And he has one black chess and one white chess, both of the chess are initially on some nodes of the tree.

Now MianKing will do the following operation until the black chess and the white chess are on the same node: If the black chess is on node , let denote the set of nodes which connect to directly. Then MainKing will choose a node of randomly and move the black chess to it.

Let denote the number of operations MianKing did, now let denote the expectation of when the black chess is on node and the white chess is on node initially. 

Let denote the set of all of the nodes in the subtree of   when the root is node . Now MainKing wants you to answer questions, each question formed by two integers , and you need to answer

It's guaranteed that for each questions.

If the answer is irreducible fraction , you need to output an integer in which satisfies . It's guaranteed that

The first line has two integers .

Then there are  lines, each line has two integers  denotes an edge of the tree.

Then there are  lines, the i-th line has two integers  denotes the i-th questions.



It's guaranteed that  for each questions.
 

There are  lines, thee i-th line has one integer denotes the answer. If the answer is irreducible fraction , you need to output an integer  in  which satisfies . It's guaranteed that 

3 1
1 2
1 3
2 3

24

7 4
1 2
1 3
2 4
2 5
3 6
3 7
2 3
4 5
2 7
4 7

6508
408
2833
960