题目描述

We have a tree with $N$ vertices numbered $1$ to $N$. The $i$-th edge in this tree connects Vertex $a_i$ and Vertex $b_i$.
Consider painting each of these edges white or black. There are $2^{N-1}$ such ways to paint the edges. Among them, how many satisfy all of the following $M$ restrictions?

• The $i$-th $(1 \leq i \leq M)$ restriction is represented by two integers $u_i$ and $v_i$, which mean that the path connecting Vertex $u_i$ and Vertex $v_i$ must contain at least one edge painted black.

我们有一棵树，树上有 $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$ 的路径必须至少包含一条涂成黑色的边。

输入格式

输入内容按以下格式标准输入：

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

输出格式

打印满足所有 $M$ 条件的边缘涂画方式的数量。

样例 #1

样例输入 #1

3
1 2
2 3
1
1 3

样例输出 #1

3

样例 #2

样例输入 #2

2
1 2
1
1 2

样例输出 #2

1

样例 #3

样例输入 #3

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

样例输出 #3

9

样例 #4

样例输入 #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

说明

数据规模与约定

• $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 \lt v_i \leq N$
• 如果是 $i \not= j$ ，则是 $u_i \not=u_j$ 或 $v_i\not=v_j$ 。
• 输入值均为整数。

样例 $1$ 解释

该输入的树形图如下：

如果边 $1$ 和 $2$ 分别被涂成（白色、黑色）、（黑色、白色）或（黑色、黑色），那么所有的 $M$ 限制都将得到满足，因此答案为 $3$ 。

样例 $2$ 解释

该输入的树形图如下：

只有将边 $1$ 涂成黑色，才能满足所有的 $M$ 限制，因此答案为 $1$ 。

样例 $3$ 解释

该输入的树形图如下所示：

样例 $4$ 解释

该输入的树形图如下所示：