题目描述

我们有一棵有 $N$ 个顶点的树，编号为 $1$ 到 $N$。这棵树中的第 $i$ 条边连接着顶点 $a_i$ 和顶点 $b_i$。

考虑将这些边每条涂成白色或黑色。有 $2^{N-1}$ 种这样的涂色方式。在其中，有多少种满足以下所有 $M$ 个限制条件的方式呢？

• 第 $i$ 个（$1 \leq i \leq M$）限制条件由两个整数 $u_i$ 和 $v_i$ 表示，表示连接顶点 $u_i$ 和顶点 $v_i$ 的路径至少要包含一条黑色的边。

---

约束条件

• $2 \leq N \leq 50$
• $1 \leq a_i, b_i \leq N$
• 给定的图是一棵树。
• $1 \leq M \leq \min(20, \frac{N(N-1)}{2})$
• $1 \leq u_i < v_i \leq N$
• 如果 $i \neq j$，则要么 $u_i \neq u_j$，要么 $v_i \neq v_j$
• 输入中的所有值都是整数。

---

输入

从标准输入读入数据，格式如下：

$N$ $a_1$ $b_1$ $\vdots$ $a_{N-1}$ $b_{N-1}$ $M$ $u_1$ $v_1$ $\vdots$ $u_M$ $v_M$

---

输出

打印满足所有 $M$ 个条件的涂色方式的数量。

---

示例输入 1

3
1 2
2 3
1
1 3

示例输出 1

3

该输入中的树如下所示：

只有当边 $1$ 和边 $2$ 分别涂成（白色，黑色），（黑色，白色）或者（黑色，黑色）时，所有 $M$ 个限制条件才被满足，所以答案是 $3$。

---

示例输入 2

2
1 2
1
1 2

示例输出 2

1

该输入中的树如下所示：

只有当边 $1$ 涂成黑色时，所有 $M$ 个限制条件才被满足，所以答案是 $1$。

---

示例输入 3

5
1 2
3 2
3 4
5 3
3
1 3
2 4
2 5

示例输出 3

9

该输入中的树如下所示：

---

示例输入 4

8
1 2
2 3
4 3
2 5
6 3
6 7
8 6
5
2 7
3 5
1 6
2 8
7 8

示例输出 4

62

该输入中的树如下所示：