Problem: 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.

Constraints

* 2 \leq N \leq 50
* 1 \leq a_i,b_i \leq N
* The graph given in input is a tree.
* 1 \leq M \leq \min(20,\frac{N(N-1)}{2})
* 1 \leq u_i < v_i \leq N
* If i \not= j, either u_i \not=u_j or v_i\not=v_j
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


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


Output

Print the number of ways to paint the edges that satisfy all of the M conditions.

Examples

Input

3
1 2
2 3
1
1 3


Output

3


Input

2
1 2
1
1 2


Output

1


Input

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


Output

9


Input

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


Output

62

Solution (in CPP):

Solution:
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 50;
const int M = 20;
const int mod = 998244353;
int n,m;
int to[(N << 1) + 5],pre[(N << 1) + 5],first[N + 5];
inline void add(int u,int v)
{
    static int tot = 0;
    to[++tot] = v,pre[tot] = first[u],first[u] = tot;
}
int fa[N + 5],s[N + 5];
int q[N + 5],head,tail;
void bfs()
{
    q[++tail] = 1;
    for(register int p;head < tail;)
    {
        p = q[++head];
        for(register int i = first[p];i;i = pre[i])
            if(to[i] ^ fa[p])
                fa[to[i]] = p,q[++tail] = to[i];
    }
}
int full;
long long f[2][(1 << M) + 5];
int main()
{
    scanf("%d",&n);
    int u,v;
    for(register int i = 2;i <= n;++i)
        scanf("%d%d",&u,&v),add(u,v),add(v,u);
    bfs();
    scanf("%d",&m),full = (1 << m) - 1;
    for(register int i = 1;i <= m;++i)
        scanf("%d%d",&u,&v),s[v] ^= (1 << i - 1),s[u] ^= (1 << i - 1);
    for(register int i = n;i;--i)
        s[fa[q[i]]] ^= s[q[i]];
    f[0][0] = 1;
    for(register int i = 2,cur = 0;i <= n;++i,cur ^= 1)
    {
        memset(f[cur ^ 1],0,sizeof f[cur ^ 1]);
        for(register int j = 0;j <= full;++j)
            f[cur ^ 1][j] += f[cur][j],
            f[cur ^ 1][j | s[i]] += f[cur][j];
    }
    printf("%lld\n",f[(n & 1) ^ 1][full]);
}