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.

-----Sample Input-----
3
1 2
2 3
1
1 3

-----Sample Output-----
3

The tree in this input is shown below:





All of the M restrictions will be satisfied if Edge 1 and 2 are respectively painted (white, black), (black, white), or (black, black), so the answer is 3.

Difficulty: interview

Starter code:

Solutions:
from collections import defaultdict


def dfs(s, t):
    visited = 0
    q = [(s, 0)]
    while q:
        v, used = q.pop()
        if v == t:
            return used
        visited |= used
        for lb, u in graph[v]:
            if lb & visited:
                continue
            q.append((u, used | lb))


n = int(input())
graph = [[] for _ in range(n + 1)]
for i in range(n - 1):
    a, b = list(map(int, input().split()))
    lb = 1 << i
    graph[a].append((lb, b))
    graph[b].append((lb, a))

conditions = []
m = int(input())
for i in range(m):
    u, v = list(map(int, input().split()))
    conditions.append(dfs(u, v))

link_conditions = [int(''.join(b), 2) for b in zip(*list(map(('{:0' + str(n - 1) + 'b}').format, conditions)))]

dp = defaultdict(int)
dp[0] = 1
for lc in link_conditions:
    for fulfilled, pattern in list(dp.items()):
        dp[fulfilled | lc] += pattern
print((dp[(1 << m) - 1]))


n = int(input())
adj = [[] for _ in range(n)]
adj_dict = dict()

for i in range(n - 1):
    a, b = [int(x) - 1 for x in input().split()]
    adj[a].append(b)
    adj[b].append(a)
    if a > b:
        adj_dict[(b, a)] = i
    else:
        adj_dict[(a, b)] = i

m = int(input())
uv = []
for _ in range(m):
    uv.append([int(x) - 1 for x in input().split()])

def dfs(p, v, dest):
    if v == dest:
        return [v]
    if p != -1 and len(adj[v]) == 1:
        return False
    for nv in adj[v]:
        if nv == p:
            continue
        ret = dfs(v, nv, dest)
        if ret:
            return ret + [v]
    return False

edgest = [0] * (2 ** m)
for i, (u, v) in enumerate(uv):
    ret = dfs(-1, u, v)
    for uu, vv in zip(ret, ret[1:]):
        if uu > vv:
            uu, vv = vv, uu
        if (uu, vv) in adj_dict:
            edgest[1 << i] |= (1 << adj_dict[(uu, vv)])

for i in range(1, 2 ** m):
    lsb = i & (-i)
    edgest[i] = edgest[i ^ lsb] | edgest[lsb]

dp = [0] * (2 ** m)
dp[0] = 1 << (n - 1)
ans = dp[0]
for i in range(1, 2 ** m):
    lsb = i & (-i)
    lim = bin(edgest[i] ^ edgest[i ^ lsb]).count('1')
    dp[i] = dp[i ^ lsb] >> lim
    if bin(i).count('1') % 2 == 0:
        ans += dp[i]
    else:
        ans -= dp[i]
print(ans)


def main():
    from itertools import combinations
    n = int(input())
    ab = [tuple(sorted(list(map(int, input().split())))) for _ in [0]*(n-1)]
    m = int(input())
    uv = [list(map(int, input().split())) for _ in [0]*m]
    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]

    d = dict()
    for i, (a, b) in enumerate(ab):
        d[(a-1, b-1)] = i

    def tree_path(root, goal):
        d = [-1]*n  # 根からの距離
        d[root] = 0
        q = [root]
        cnt = 0
        while q:  # BFS
            cnt += 1
            qq = []
            while q:
                i = q.pop()
                for j in g[i]:
                    if d[j] == -1:
                        d[j] = cnt
                        qq.append(j)
            q = qq
        now = goal
        path = [goal]
        while True:
            dist = d[now]
            for i in g[now]:
                if d[i] < dist:
                    now = i
                    path.append(i)
                    break
            if dist == 1:
                break
        return path

    seiyaku = [set() for _ in [0]*m]

    for i, (u, v) in enumerate(uv):
        path = tree_path(u-1, v-1)
        for j in range(len(path)-1):
            x, y = min(path[j], path[j+1]), max(path[j], path[j+1])
            seiyaku[i].add(d[(x, y)])

    cnt = 2**(n-1)

    for i in range(1, m+1):
        flag = 1
        if i % 2 == 1:
            flag = -1
        cc = combinations(list(range(m)), i)
        for c in cc:
            s = set()
            for j in c:
                s |= seiyaku[j]
            cnt += (2**(n-1-len(s)))*flag
    print(cnt)


main()


# https://atcoder.jp/contests/abc152/submissions/9619555

import sys
readline = sys.stdin.readline

import numpy as np

N = int(readline())
AB = list(list(map(int, readline().split())) for _ in range(N - 1))
M = int(readline())
UV = list(list(map(int, readline().split())) for _ in range(M))

graph = [[] for _ in range(N + 1)]
for i, (a, b) in enumerate(AB):
    graph[a].append((b, i))
    graph[b].append((a, i))


def get_path(U, V):
    INF = 100
    visited = [False] * (N + 1)
    pred = [None] * (N + 1)
    stack = [U]
    visited[U] = True
    while stack:
        v = stack.pop()
        for w, i in graph[v]:
            if visited[w]:
                continue
            visited[w] = True
            pred[w] = (v, i)
            stack.append(w)
    path = 0
    w = V
    while w != U:
        v, i = pred[w]
        w = v
        path += 1 << i
    return path


condition_path = [get_path(u, v) for u, v in UV]


def popcnt(n):
    c = (n & 0x5555555555555555) + ((n >> 1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c >> 2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c >> 4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c >> 8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c >> 16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c >> 32) & 0x00000000ffffffff)
    return c


sgn = np.where(popcnt(np.arange(1 << M)) % 2, -1, 1)
S = np.zeros(1 << M, np.int64)
for i in range(M):
    S[1 << i:1 << (i + 1)] = S[:1 << i] | condition_path[i]

n_edges = popcnt(S)

x = 1 << (N - 1 - n_edges)
answer = np.sum(x * sgn)
print(answer)


from collections import defaultdict


def dfs(s, t):
    visited = 0
    q = [(s, 0)]
    while q:
        v, used = q.pop()
        if v == t:
            return used
        visited |= used
        for lb, u in graph[v]:
            if lb & visited:
                continue
            q.append((u, used | lb))


n = int(input())
graph = [[] for _ in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    lb = 1 << i
    graph[a].append((lb, b))
    graph[b].append((lb, a))

conditions = []
m = int(input())
for i in range(m):
    u, v = map(int, input().split())
    conditions.append(dfs(u, v))

link_conditions = [int(''.join(i), 2) for i in zip(*[bin(j)[2:].zfill(n - 1) for j in conditions])]

dp = defaultdict(int)
dp[0] = 1
for lc in link_conditions:
    for fulfilled, pattern in list(dp.items()):
        dp[fulfilled | lc] += pattern
print(dp[(1 << m) - 1])

# https://atcoder.jp/contests/abc152/submissions/9619555

import sys
readline = sys.stdin.readline

import numpy as np

N = int(readline())
AB = list(list(map(int, readline().split())) for _ in range(N - 1))
M = int(readline())
UV = list(list(map(int, readline().split())) for _ in range(M))

graph = [[] for _ in range(N + 1)]
for i, (a, b) in enumerate(AB):
    graph[a].append((b, i))
    graph[b].append((a, i))


def get_path(U, V):
    INF = 100
    visited = [False] * (N + 1)
    pred = [None] * (N + 1)
    stack = [U]
    visited[U] = True
    while stack:
        v = stack.pop()
        for w, i in graph[v]:
            if visited[w]:
                continue
            visited[w] = True
            pred[w] = (v, i)
            stack.append(w)
    path = 0
    w = V
    while w != U:
        v, i = pred[w]
        w = v
        path += 1 << i
    return path


condition_path = [get_path(u, v) for u, v in UV]


def popcnt(n):
    c = (n & 0x5555555555555555) + ((n >> 1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c >> 2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c >> 4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c >> 8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c >> 16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c >> 32) & 0x00000000ffffffff)
    return c


sgn = np.where(popcnt(np.arange(1 << M)) % 2, -1, 1)
S = np.zeros(1 << M, np.int64)
for i in range(M):
    S[1 << i:1 << (i + 1)] = S[:1 << i] | condition_path[i]

n_edges = popcnt(S)

x = 1 << (N - 1 - n_edges)
answer = (x * sgn).sum()
print(answer)


n = int(input())
adj = [[] for _ in range(n)]
adj_dict = dict()

for i in range(n - 1):
    a, b = [int(x) - 1 for x in input().split()]
    adj[a].append(b)
    adj[b].append(a)
    if a > b:
        adj_dict[(b, a)] = i
    else:
        adj_dict[(a, b)] = i

m = int(input())
uv = []
for _ in range(m):
    uv.append([int(x) - 1 for x in input().split()])

def dfs(p, v, dest):
    if v == dest:
        return [v]
    if p != -1 and len(adj[v]) == 1:
        return False
    for nv in adj[v]:
        if nv == p:
            continue
        ret = dfs(v, nv, dest)
        if ret:
            return ret + [v]
    return False

edgest = [0] * (2 ** m)
for i, (u, v) in enumerate(uv):
    ret = dfs(-1, u, v)
    for uu, vv in zip(ret, ret[1:]):
        if uu > vv:
            uu, vv = vv, uu
        if (uu, vv) in adj_dict:
            edgest[1 << i] |= (1 << adj_dict[(uu, vv)])

for i in range(1, 2 ** m):
    lsb = i & (-i)
    edgest[i] = edgest[i ^ lsb] | edgest[lsb]

dp = [0] * (2 ** m)
dp[0] = 1 << (n - 1)
ans = dp[0]
for i in range(1, 2 ** m):
    lsb = i & (-i)
    lim = bin(edgest[i] ^ edgest[i ^ lsb]).count('1')
    dp[i] = dp[i ^ lsb] >> lim
    if bin(i).count('1') % 2 == 0:
        ans += dp[i]
    else:
        ans -= dp[i]
print(ans)

from functools import reduce
# https://drken1215.hatenablog.com/entry/2020/01/26/164200
# bit_pathの参考にした
# https://atcoder.jp/contests/abc152/submissions/9619555
# popcnt

def main():
    from collections import namedtuple
    from functools import reduce
    from itertools import combinations
    from operator import or_

    Edge = namedtuple('Edge', 'to edge_id')

    def bit_path(curr, goal, par=-1):
        if curr == goal:
            return 0
        for e in g[curr]:
            if e.to == par: continue
            res = bit_path(curr=e.to, goal=goal, par=curr)
            if ~res:  # -1以外
                return res | (1 << e.edge_id)
        return -1

    def popcnt(n):
        """https://atcoder.jp/contests/abc152/submissions/9619555"""
        c = (n & 0x5555555555555555) + ((n >> 1) & 0x5555555555555555)
        c = (c & 0x3333333333333333) + ((c >> 2) & 0x3333333333333333)
        c = (c & 0x0f0f0f0f0f0f0f0f) + ((c >> 4) & 0x0f0f0f0f0f0f0f0f)
        c = (c & 0x00ff00ff00ff00ff) + ((c >> 8) & 0x00ff00ff00ff00ff)
        c = (c & 0x0000ffff0000ffff) + ((c >> 16) & 0x0000ffff0000ffff)
        c = (c & 0x00000000ffffffff) + ((c >> 32) & 0x00000000ffffffff)
        return c

    N = int(input())

    g = tuple(set() for _ in range(N))
    for edge_id in range(N - 1):
        a, b = (int(x) - 1 for x in input().split())
        g[a].add(Edge(to=b, edge_id=edge_id))
        g[b].add(Edge(to=a, edge_id=edge_id))

    M = int(input())

    cons = []
    for _ in range(M):
        u, v = (int(x) - 1 for x in input().split())
        b = bit_path(u, v)
        cons.append(b)

    ans = 1 << (N - 1)
    for k in range(1, M + 1):
        for comb in combinations(cons, r=k):
            b = reduce(or_, comb)
            ans += ((-1) ** k) * (1 << (N - 1 - popcnt(b)))
    print(ans)


def __starting_point():
    main()

__starting_point()

N = int(input())
AB = [tuple(map(int,input().split())) for i in range(N-1)]
M = int(input())
UV = [tuple(map(int,input().split())) for i in range(M)]

es = [[] for i in range(N)]
for i,(a,b) in enumerate(AB):
    a,b = a-1,b-1
    es[a].append((b,i))
    es[b].append((a,i))

paths = [0] * M
for i,(u,v) in enumerate(UV):
    u,v = u-1,v-1
    stack = [u]
    visited = [0] * N
    visited[u] = 1
    edges = [-1] * N
    while stack:
        s = stack.pop()
        for to,j in es[s]:
            if visited[to]: continue
            visited[to] = 1
            edges[to] = j
            stack.append(to)
            if to == v:
                break
        else:
            continue
        while edges[v] >= 0:
            j = edges[v]
            paths[i] |= (1<<j)
            a,b = AB[j]
            a,b = a-1,b-1
            v = a if a!=v else b
        break

dp = [0] * (1<<M)
for b in range(1,1<<M):
    k = len(bin(b))-3
    dp[b] = dp[b-2**k] | paths[k]

ans = 0
for i,d in enumerate(dp):
    b = N-1 - bin(d).count('1')
    ans += 2**b if bin(i).count('1')%2==0 else -2**b
print(ans)

#!/usr/bin/env python3
import sys
input = sys.stdin.readline
 
n = int(input())
edge = [[] for _ in range(n)]
edge_dict = dict()
 
for i in range(n - 1):
    a, b = [int(item) - 1 for item in input().split()]
    edge[a].append(b)
    edge[b].append(a)
    if a > b:
        edge_dict[(b, a)] = i
    else:
        edge_dict[(a, b)] = i
 
m = int(input())
uv = []
for _ in range(m):
    uv.append([int(item) - 1 for item in input().split()])
 
def dfs(p, v, dest):
    if v == dest:
        return [v]
    if p != -1 and len(edge[v]) == 1:
        return False
    for nv in edge[v]:
        if nv == p:
            continue
        ret = dfs(v, nv, dest)
        if ret:
            return ret + [v]
    return False
 
# edge-bitset of each set of constraints
edgest = [0] * 2**m
for i, (u, v) in enumerate(uv):
    ret = dfs(-1, u, v)
    for uu, vv in zip(ret, ret[1:]):
        if uu > vv:
            uu, vv = vv, uu
        if (uu, vv) in edge_dict:
            edgest[1 << i] |= (1 << edge_dict[(uu, vv)])
for i in range(1, 2**m):
    lsb = i & (-i)
    edgest[i] = edgest[i ^ lsb] | edgest[lsb]
 
# dp[set of constraints]
dp = [0] * 2**m
dp[0] = 1 << (n - 1)
ans = dp[0]
for i in range(1, 2**m):
    lsb = i & (-i)
    limit_num = bin(edgest[i] ^ edgest[i ^ lsb]).count("1")
    dp[i] = dp[i ^ lsb] >> limit_num
    # Inclusion and exclusion
    if bin(i).count("1") % 2 == 0:
        ans += dp[i]
    else:
        ans -= dp[i]
print(ans)

#!/usr/bin/env python3
import sys
input = sys.stdin.readline
 
n = int(input())
edge = [[] for _ in range(n)]
edge_dict = dict()
 
for i in range(n - 1):
    a, b = [int(item) - 1 for item in input().split()]
    edge[a].append(b)
    edge[b].append(a)
    if a > b:
        edge_dict[(b, a)] = i
    else:
        edge_dict[(a, b)] = i
 
m = int(input())
uv = []
for _ in range(m):
    uv.append([int(item) - 1 for item in input().split()])
 
def dfs(p, v, dest):
    if v == dest:
        return [v]
    if p != -1 and len(edge[v]) == 1:
        return False
    for nv in edge[v]:
        if nv == p:
            continue
        ret = dfs(v, nv, dest)
        if ret:
            return ret + [v]
    return False
 
target_edge = [0] * m
for i, (u, v) in enumerate(uv):
    ret = dfs(-1, u, v)
    for uu, vv in zip(ret, ret[1:]):
        if uu > vv:
            uu, vv = vv, uu
        if (uu, vv) in edge_dict:
            target_edge[i] |= (1 << edge_dict[(uu, vv)])

edge_of_state = [0] * 2**m
for i in range(1, 2**m):
    lsb = i & (-i)
    edge_of_state[i] = edge_of_state[i ^ lsb] | target_edge[lsb.bit_length() - 1]
 
# dp[fills uv as st]
dp = [0] * 2**m
dp[0] = pow(2, n-1) 
ans = dp[0]
for i in range(1, 2**m):
    lsb = i & (-i)
    n_edgest = edge_of_state[i]
    p_edgest = edge_of_state[i ^ lsb]
    limit_num = bin(n_edgest ^ p_edgest).count("1")
    dp[i] = dp[i ^ lsb] // pow(2, limit_num)
    if bin(i).count("1") % 2 == 0:
        ans += dp[i]
    else:
        ans -= dp[i]
print(ans)

# https://atcoder.jp/contests/abc152/submissions/9619555

import numpy as np
import sys
readline = sys.stdin.readline

N = int(readline())
graph = [[] for _ in range(N + 1)]
for i in range(N - 1):
    a, b = map(int, readline().split())
    lb = 1 << i
    graph[a].append((lb, b))
    graph[b].append((lb, a))

M = int(readline())


def get_path(U, V):
    visited = 0
    q = [(U, 0)]
    while q:
        v, used = q.pop()
        if v == V:
            return used
        visited |= used
        for lb, u in graph[v]:
            if lb & visited:
                continue
            q.append((u, used | lb))


condition_path = []
for i in range(M):
    u, v = map(int, readline().split())
    condition_path.append(get_path(u, v))


def popcnt(n):
    c = (n & 0x5555555555555555) + ((n >> 1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c >> 2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c >> 4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c >> 8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c >> 16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c >> 32) & 0x00000000ffffffff)
    return c


sgn = np.where(popcnt(np.arange(1 << M)) % 2, -1, 1)
S = np.zeros(1 << M, np.int64)
for i in range(M):
    S[1 << i:1 << (i + 1)] = S[:1 << i] | condition_path[i]


n_edges = popcnt(S)
x = 1 << (N - 1 - n_edges)
answer = np.sum(x * sgn)
print(answer)

from itertools import combinations

n = int(input())
ab = [list(map(int, input().split())) for _ in range(n - 1)]
m = int(input())
uv = [list(map(int, input().split())) for _ in range(m)]

adj = [[] for _ in range(n)]
ids = [[-1] * n for _ in range(n)]
for i, (a, b) in enumerate(ab):
    a -= 1
    b -= 1
    adj[a].append(b)
    adj[b].append(a)
    ids[a][b] = i
    ids[b][a] = i


def dfs(s, g):
    d = [-1] * n
    d[s] = 0
    p = [-1] * n
    stack = [s]

    while stack:
        u = stack.pop()
        for v in adj[u]:
            if d[v] == -1:
                d[v] = d[u] + 1
                p[v] = u
                stack.append(v)

    v = g
    ret = 0
    while v != s:
        i = ids[v][p[v]]
        ret += 1 << i
        v = p[v]

    return ret


def bin_count(tpl):
    sm_or = 0
    for e in tpl:
        sm_or |= e

    return bin(sm_or).count("1")


path = [dfs(u - 1, v - 1) for u, v in uv]
ex = 0
for i in range(1, m + 1):
    for tpl in combinations(path, i):
        ex += pow(2, n - 1 - bin_count(tpl)) * (-1) ** (i % 2 + 1)

ans = pow(2, n - 1) - ex
print(ans)


# 多分TLE
from scipy.sparse.csgraph import dijkstra
from itertools import combinations

N = int(input())
edge_id = {}
D = [[-float('inf')]*N for i in range(N)]
for i in range(N-1):
  a, b = map(int, input().split())
  D[a-1][b-1] = D[b-1][a-1] = 1
  edge_id[(a-1, b-1)] = i
  edge_id[(b-1, a-1)] = i

paths = dijkstra(D, return_predecessors=True)[1]
M = int(input())
edges = [0] * M
for i in range(M):
  u, v = map(int, input().split())
  now, p = paths[u-1][v-1], v-1
  edges[i] += 1 << edge_id[(now, p)]
  while now != u-1:
    now, p = paths[u-1][now], now
    edges[i] += 1 << edge_id[(now, p)]

ans = pow(2, N-1)
coeff = -1
for m in range(1, M+1):
  for comb in combinations(edges, m):
    e = 0
    for c in comb:
      e |= c
    ans +=  coeff* pow(2, N-1-bin(e).count('1'))
  coeff *= -1

print(ans)

N = int(input())
ab = [tuple(map(int,input().split())) for _ in range(N - 1)]
M = int(input())
uv = [tuple(map(int,input().split())) for _ in range(M)]
route = [[] for _ in range(N)]

for i, (a, b) in enumerate(ab):
    a -= 1
    b -= 1
    route[a].append((b, i))
    route[b].append((a, i))

path = [0] * M
for i, (u, v) in enumerate(uv):
    u -= 1
    v -= 1
    stack = [u]
    visited = [0] * N
    visited[u] = 1
    dire = [[] for _ in range(N)]
    while True:
        s = stack.pop()
        for g, j in route[s]:
            if visited[g]:
                continue   
            stack.append(g)
            dire[g].append((s, j))
            visited[g] = 1
        if visited[v]:
            break
    s = v
    while True:
        g, num = dire[s][0]
        path[i] |= (1 << num)
        if g == u:
            break
        s = g

data = [0] * (1 << M)
ans = 2 ** (N - 1)
for i in range(1, 1 << M):
    k = len(bin(i)) - 3
    data[i] = data[i - (2 ** k)] | path[k]
    power = bin(data[i]).count("1")
    judge = bin(i).count("1")
    ans += (-2 ** (N - 1 - power) if judge % 2 else 2 ** (N - 1 - power))
print(ans)


# https://atcoder.jp/contests/abc152/submissions/9619555

import sys
readline = sys.stdin.readline

import numpy as np

N = int(readline())
AB = list(list(map(int, readline().split())) for _ in range(N - 1))
M = int(readline())
UV = list(list(map(int, readline().split())) for _ in range(M))

graph = [[] for _ in range(N + 1)]
for i, (a, b) in enumerate(AB):
    graph[a].append((b, i))
    graph[b].append((a, i))


def get_path(U, V):
    INF = 100
    visited = [False] * (N + 1)
    pred = [None] * (N + 1)
    stack = [U]
    visited[U] = True
    while stack:
        v = stack.pop()
        for w, i in graph[v]:
            if visited[w]:
                continue
            visited[w] = True
            pred[w] = (v, i)
            stack.append(w)
    path = 0
    w = V
    while w != U:
        v, i = pred[w]
        w = v
        path += 1 << i
    return path


condition_path = [get_path(u, v) for u, v in UV]


def popcnt(n):
    c = (n & 0x5555555555555555) + ((n >> 1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c >> 2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c >> 4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c >> 8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c >> 16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c >> 32) & 0x00000000ffffffff)
    return c


S = np.zeros(1 << M, np.int64)
sgn = np.ones(1 << M, np.int64)
for i in range(M):
    S[1 << i:1 << (i + 1)] = S[:1 << i] | condition_path[i]
    sgn[1 << i:1 << (i + 1)] = -sgn[:1 << i]

n_edges = popcnt(S)
x = 1 << (N - 1 - n_edges)
answer = (x * sgn).sum()
print(answer)


# https://atcoder.jp/contests/abc152/submissions/9619555

import numpy as np
import sys
readline = sys.stdin.readline

N = int(readline())
graph = [[] for _ in range(N + 1)]
for i in range(N - 1):
    a, b = list(map(int, readline().split()))
    graph[a].append((b, i))
    graph[b].append((a, i))

M = int(readline())


def get_path(U, V):
    visited = [False] * (N + 1)
    pred = [None] * (N + 1)
    stack = [U]
    visited[U] = True
    while stack:
        v = stack.pop()
        for w, i in graph[v]:
            if visited[w]:
                continue
            visited[w] = True
            pred[w] = (v, i)
            stack.append(w)
    path = 0
    w = V
    while w != U:
        v, i = pred[w]
        w = v
        path += 1 << i
    return path


condition_path = []
for i in range(M):
    u, v = list(map(int, readline().split()))
    condition_path.append(get_path(u, v))


def popcnt(n):
    c = (n & 0x5555555555555555) + ((n >> 1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c >> 2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c >> 4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c >> 8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c >> 16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c >> 32) & 0x00000000ffffffff)
    return c


sgn = np.where(popcnt(np.arange(1 << M)) % 2, -1, 1)
S = np.zeros(1 << M, np.int64)
for i in range(M):
    S[1 << i:1 << (i + 1)] = S[:1 << i] | condition_path[i]


n_edges = popcnt(S)
x = 1 << (N - 1 - n_edges)
answer = np.sum(x * sgn)
print(answer)


from collections import defaultdict


def dfs(s, t, links):
    visited = set()
    q = [(s, 0)]
    while q:
        v, used = q.pop()
        if v == t:
            return used
        visited.add(v)
        for lb, u in links[v]:
            if u in visited:
                continue
            q.append((u, used | lb))


n = int(input())
links = [set() for _ in range(n)]
for i in range(n - 1):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    lb = 1 << i
    links[a].add((lb, b))
    links[b].add((lb, a))
conditions = []
m = int(input())
for i in range(m):
    u, v = list(map(int, input().split()))
    u -= 1
    v -= 1
    conditions.append(dfs(u, v, links))

link_conditions = [int(''.join(b), 2) for b in zip(*list(map(('{:0' + str(n - 1) + 'b}').format, conditions)))]

dp = defaultdict(lambda: 0)
dp[0] = 1
for lc in link_conditions:
    for fulfilled, pattern in list(dp.items()):
        dp[fulfilled | lc] += pattern
print((dp[(1 << m) - 1]))


from collections import defaultdict


def dfs(s, t):
    visited = 0
    q = [(s, 0)]
    while q:
        v, used = q.pop()
        if v == t:
            return used
        visited |= used
        for lb, u in graph[v]:
            if lb & visited:
                continue
            q.append((u, used | lb))


n = int(input())
graph = [[] for _ in range(n + 1)]
for i in range(n - 1):
    a, b = list(map(int, input().split()))
    lb = 1 << i
    graph[a].append((lb, b))
    graph[b].append((lb, a))

conditions = []
m = int(input())
for i in range(m):
    u, v = list(map(int, input().split()))
    conditions.append(dfs(u, v))

link_conditions = [int(''.join(b), 2) for b in zip(*list(map(('{:0' + str(n - 1) + 'b}').format, conditions)))]

dp = defaultdict(lambda: 0)
dp[0] = 1
for lc in link_conditions:
    for fulfilled, pattern in list(dp.items()):
        dp[fulfilled | lc] += pattern
print((dp[(1 << m) - 1]))


from functools import reduce
# https://drken1215.hatenablog.com/entry/2020/01/26/164200
# bit_pathの参考にした

def main():
    from collections import namedtuple
    from functools import reduce
    from itertools import combinations
    from operator import or_

    Edge = namedtuple('Edge', 'to edge_id')

    def bit_path(curr, goal, par=-1):
        if curr == goal:
            return 0
        for e in g[curr]:
            if e.to == par: continue
            res = bit_path(curr=e.to, goal=goal, par=curr)
            if ~res:  # -1以外
                return res | (1 << e.edge_id)
        return -1

    N = int(input())

    g = tuple(set() for _ in range(N))
    for edge_id in range(N - 1):
        a, b = (int(x) - 1 for x in input().split())
        g[a].add(Edge(to=b, edge_id=edge_id))
        g[b].add(Edge(to=a, edge_id=edge_id))

    M = int(input())

    cons = []
    for _ in range(M):
        u, v = (int(x) - 1 for x in input().split())
        b = bit_path(u, v)
        cons.append(b)

    ans = 1 << (N - 1)
    for k in range(1, M + 1):
        for comb in combinations(cons, r=k):
            b = reduce(or_, comb)
            ans += ((-1) ** k) * (1 << (N - 1 - bin(b).count('1')))
    print(ans)


def __starting_point():
    main()

__starting_point()

#!/usr/bin/env python3
import sys
input = sys.stdin.readline
 
n = int(input())
edge = [[] for _ in range(n)]
edge_dict = dict()
 
for i in range(n - 1):
    a, b = [int(item) - 1 for item in input().split()]
    edge[a].append(b)
    edge[b].append(a)
    if a > b:
        edge_dict[(b, a)] = i
    else:
        edge_dict[(a, b)] = i
 
m = int(input())
uv = []
for _ in range(m):
    uv.append([int(item) - 1 for item in input().split()])
 
def dfs(p, v, dest):
    if v == dest:
        return [v]
    if p != -1 and len(edge[v]) == 1:
        return False
    for nv in edge[v]:
        if nv == p:
            continue
        ret = dfs(v, nv, dest)
        if ret:
            return ret + [v]
    return False
 
# edge-bitset of each constraint
target_edge = [0] * m
for i, (u, v) in enumerate(uv):
    ret = dfs(-1, u, v)
    for uu, vv in zip(ret, ret[1:]):
        if uu > vv:
            uu, vv = vv, uu
        if (uu, vv) in edge_dict:
            target_edge[i] |= (1 << edge_dict[(uu, vv)])

# edge-bitset of each set of constraints
edgest = [0] * 2**m
for i in range(1, 2**m):
    lsb = i & (-i)
    edgest[i] = edgest[i ^ lsb] | target_edge[lsb.bit_length() - 1]
 
# dp[set of constraints]
dp = [0] * 2**m
dp[0] = 1 << (n - 1)
ans = dp[0]
for i in range(1, 2**m):
    lsb = i & (-i)
    n_edgest = edgest[i]
    p_edgest = edgest[i ^ lsb]
    limit_num = bin(n_edgest ^ p_edgest).count("1")
    dp[i] = dp[i ^ lsb] >> limit_num
    if bin(i).count("1") % 2 == 0:
        ans += dp[i]
    else:
        ans -= dp[i]
print(ans)