AT_abc152_f [ABC152F] Tree and Constraints

[problemUrl]: https://atcoder.jp/contests/abc152/tasks/abc152_f $ 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 $ つ以上存在しなければならないことを意味する。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ a_1 $ $ b_1 $ $ : $ $ a_{N-1} $ $ b_{N-1} $ $ M $ $ u_1 $ $ v_1 $ $ : $ $ u_M $ $ v_M $

$ M $ 個の制約をすべて満たす塗り方の個数を出力せよ。

### 制約 - $ 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\