G. Spanning Tree
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

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$$$ .

Example
Input
3
1 2
1 3
1 2
1 3
Output
499122177