Spanning Tree
Description
We generate a spanning tree of $n$ nodes according to the following random process:
Initially, there are no edges connecting the $n$ nodes.
Then process the following $n-1$ operations:
- For the $i$-th operation, two integers $a_i$ and $b_i$ will be input, and it's guaranteed that the two nodes are not connected before.
- Select a node $u_i$ from the connected block where $a_i$ is located with uniform probability, then select a node $v_i$ from the connected block where $b_i$ is located with uniform probability, and then add an edge to connect $u_i$ and $v_i$ .
It can be proved that no matter which two nodes are selected in each operation, after all operations are processed, a spanning tree of $n$ nodes will be formed.
Now given a spanning tree of $n$ nodes. What is the probability that the spanning tree formed by the random process is exactly this spanning tree?
You only need to output the value of the probability modulo $998244353$ .
Please note that the probability could be $0$, which means that you can never generate this spanning tree.
The first line contains a single integer $n\ (1\le n \le 10^6)$ , representing the number of nodes.
For the following $n-1$ lines, each line contains two integers $a_i,b_i\ (1\le a_i,b_i\le n, a_i\not = b_i)$, representing the $i$-th operation, and it's guaranteed that the two nodes are not connected before.
For the following $n-1$ lines, each line contains two integers $c_i,d_i\ (1\le c_i,d_i\le n, c_i\not = d_i)$, representing an edge of the given spanning tree, and it's guaranteed that the given edges forms a spanning tree.
One line containing one integer, representing the value of the probability modulo $998244353$ .
Input
The first line contains a single integer $n\ (1\le n \le 10^6)$ , representing the number of nodes.
For the following $n-1$ lines, each line contains two integers $a_i,b_i\ (1\le a_i,b_i\le n, a_i\not = b_i)$, representing the $i$-th operation, and it's guaranteed that the two nodes are not connected before.
For the following $n-1$ lines, each line contains two integers $c_i,d_i\ (1\le c_i,d_i\le n, c_i\not = d_i)$, representing an edge of the given spanning tree, and it's guaranteed that the given edges forms a spanning tree.
Output
One line containing one integer, representing the value of the probability modulo $998244353$ .
3
1 2
1 3
1 2
1 3
499122177