题目描述

我们有一棵有$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$

接下来一共$N-1$行，表示树的边

接下来一个整数$M$

接下来一共$M$个限制，表示$u$到$v$至少有一个黑边

输出

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

输出

3
1 2
2 3
1
1 3

3

2
1 2
1
1 2

1

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

9

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

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\ <\ v_i\ \leq\ N$
• $如果 i\ \not=\ j$ 要么 $u_i\ \not=u_j$ 要么 $v_i\not=v_j$