我们通过以下随机过程生成一个包含 $n$ 个节点的生成树：

初始时，$n$ 个节点之间没有任何边。

随后进行 $n - 1$ 次操作：

• 对于第 $i$ 次操作，输入两个整数 $a_i$ 和 $b_i$，保证这两个节点在操作前不连通。
• 在 $a_i$ 所在的连通块中等概率选择一个节点 $u_i$，在 $b_i$ 所在的连通块中等概率选择一个节点 $v_i$，然后添加一条连接 $u_i$ 和 $v_i$ 的边。

可以证明，无论每次操作中选择了哪两个节点，在所有操作完成后，都会形成一棵包含 $n$ 个节点的生成树。

现在给定一棵包含 $n$ 个节点的生成树。求该随机过程生成这棵特定生成树的概率。

你只需要输出该概率对 $998244353$ 取模后的值。

请注意，概率可能为 $0$，这意味着你永远无法生成这棵生成树。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 10^6$)，表示节点数量。

接下来的 $n - 1$ 行，每行包含两个整数 $a_i, b_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i$)，表示第 $i$ 次操作，保证这两个节点在操作前不连通。

接下来的 $n - 1$ 行，每行包含两个整数 $c_i, d_i$ ($1 \le c_i, d_i \le n, c_i \neq d_i$)，表示给定生成树的一条边，保证给定的边构成一棵生成树。

输出格式

输出一行，包含一个整数，表示该概率对 $998244353$ 取模后的值。

样例

样例输入 1

3
1 2
1 3
1 2
1 3

样例输出 1

499122177