E. LeaFall

每个测试的时间限制：$3$ 秒
每个测试的内存限制：$512$ MB

给定一棵有 $n$ 个顶点的树$^{*}$。随时间推移，每个顶点 $i$（$1 \le i \le n$）以概率 $\frac{p_i}{q_i}$ 倒下。
需要计算：在最终得到的森林$^{§}$中，成为叶子$^{‡}$的不同顶点的无序对$^{†}$的数量的期望值，结果对 $998244353$ 取模。

注意：当顶点 $v$ 倒下时，它连同与它相连的所有边一起被移除。但相邻的顶点不受 $v$ 倒下的影响。

---

$^{*}$ 树是没有环的连通图。

$^{†}$ 无序对是指两个元素的集合，其中元素的顺序不重要。例如，无序对 $(1,2)$ 和 $(2,1)$ 被视为相同。

$^{‡}$ 叶子是恰好与一条边相连的顶点。

$^{§}$ 森林是没有环的图。

---

输入格式

每个测试包含多个测试用例。
第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。

每个测试用例的描述如下：

• 第一行包含一个整数 $n$（$1 \le n \le 10^5$）。
• 接下来的 $n$ 行中，第 $i$ 行包含两个整数 $p_i$ 和 $q_i$（$1 \le p_i < q_i < 998244353$）。
• 接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$，$u \neq v$），表示树中的一条边。

保证这些边构成一棵树。
保证所有测试用例的 $n$ 之和不超过 $10^5$。

---

输出格式

对于每个测试用例，输出一个整数 —— 最终森林中成为叶子的不同顶点的无序对数量的期望值，对 $998244353$ 取模。

形式上，设 $M = 998244353$。可以证明答案可以表示为既约分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 是整数且 $q \not\equiv 0 \pmod{M}$。输出整数 $x = p \cdot q^{-1} \bmod M$。换句话说，输出满足 $0 \le x < M$ 且 $x \cdot q \equiv p \pmod{M}$ 的整数 $x$。

---

示例

输入 #1

5
1
1 2
3
1 2
1 2
1 2
1 2
2 3
3
1 3
1 5
1 3
1 2
2 3
1
998244351 998244352
6
10 17
7 13
6 11
2 10
10 19
5 13
4 3
3 6
1 4
3 5
3 2

输出 #1

0
623902721
244015287
0
799215919

输入 #2

1
10
282508078 551568452
894311255 989959022
893400641 913415297
460925436 801908985
94460427 171411253
997964895 998217862
770266391 885105593
591419316 976424827
606447024 863339056
940224886 994244553
9 5
9 6
9 8
8 7
3 6
1 5
7 4
8 10
4 2

输出 #2

486341067

---

说明

• 在第一个测试用例中，树中只有一个顶点，它不是叶子，因此答案为 $0$。

• 在第二个测试用例中，树如下所示。

• 

  未倒下的顶点用粗体表示。考虑以下三种情况：

  • 

  • 以概率 $\left(\frac12\right)^3$ 到达某种配置，其中唯一的不同叶子顶点对是 $(2,3)$。

  • 

  • 以概率 $\left(\frac12\right)^3$ 到达另一种配置，其中唯一的不同叶子顶点对是 $(2,1)$。

  • 

  • 以概率 $\left(\frac12\right)^3$ 到达另一种配置，其中唯一的不同叶子顶点对是 $(1,3)$。
    其余情况不包含任何不同叶子顶点对。因此答案为 $\frac{1+1+1}{8} = \frac38$，对 $998244353$ 取模后等于 $623902721$。