题目描述

点击查看pdf

MianKing has a tree with $n$ 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 $x$, let $S$ denote the set of nodes which connect to $x$ directly. Then MainKing will choose a node of $S$ randomly and move the black chess to it.

Let $Len$ denote the number of operations MianKing did, now let $f(S,T)$ denote the expectation of $Len^2$ when the black chess is on node $S$ and the white chess is on node $T$ initially.

Let $Sub(x)$ denote the set of all of the nodes in the subtree of $x$ when the root is node $1$. Now MainKing wants you to answer $Q$ questions, each question formed by two integers $A$,$B$ and you need to answer

It's guaranteed that $Sub(x)\\cap Sub(y)=\\emptyset$ for each questions.

If the answer is irreducible fraction $\\frac{x}{y}$, you need to output an integer $d$ in $[0,998244352]$ which satisfies $d*y~mod~998244353=x$. It's guaranteed that $y~mod~998244353\ eq 0$

输入格式

The first line has two integers $n,Q$.

Then there are $n-1$ lines, each line has two integers $(x,y)$ denotes an edge of the tree.

Then there are $Q$ lines, the i-th line has two integers $(A,B)$ denotes the i-th questions.

$1\\leq n,Q\\leq 10^5$

It's guaranteed that $Sub(A)\\cap Sub(B)=\\emptyset$ for each questions.

输出格式

There are $Q$ lines, thee i-th line has one integer denotes the answer. If the answer is irreducible fraction $\\frac{x}{y}$, you need to output an integer $d$ in $[0,998244352]$ which satisfies $d*y~mod~998244353=x$. It's guaranteed that $y~mod~998244353\ eq 0$

样例

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 

提示

Form 2020ICPC济南站