配点 : $600$ 点

問題文

$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$ 個の制約をすべて満たす塗り方の個数を出力せよ。

3
1 2
2 3
1
1 3

3

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

辺 $1$ と辺 $2$ をそれぞれ (白,黒), (黒,白), (黒,黒) で塗った場合に、$M$ 個の制約をすべて満たすことができます。 したがって答えは $3$ です。

2
1 2
1
1 2

1

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

辺 $1$ を黒く塗った場合のみ、 $M$ 個の制約をすべて満たすことができます。
したがって答えは $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

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