問題文

$1$ から $N$ までの番号がつけられた $N$ 個の頂点を持つ木があります。 この木の $i$ 番目の辺は頂点 $a_i$ と頂点 $b_i$ を結んでいます。
この木の各辺に、それぞれ白か黒の色を塗ることを考えます。このような塗り方は $2^{N-1}$ 通り考えられますが、そのうち以下の $M$ 個の制約をすべて満たすものの個数を求めてください。

• $i(1 \\leq i \\leq M)$ 番目の制約は、 $2$ つの整数 $u_i$ と $v_i$ によって表される。これは、頂点 $u_i$ と頂点 $v_i$ を結ぶパスに含まれる辺のうち、黒く塗られているものが $1$ つ以上存在しなければならないことを意味する。

制約

• $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$
• 入力はすべて整数である。

---

入力

入力は以下の形式で標準入力から与えられる。

$N$ $a_1$ $b_1$ $:$ $a_{N-1}$ $b_{N-1}$ $M$ $u_1$ $v_1$ $:$ $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

この入力中の木は以下のようなものです。