# F - Tree and Constraints



# Read input



n = int(eval(input()))

adj = {a: [] for a in range(1, n + 1)}

for i in range(n - 1):

    a, b = list(map(int, input().split()))

    adj[a].append(b)

    adj[b].append(a)

m = int(eval(input()))

ranges = []

for i in range(m):

    u, v = list(map(int, input().split()))

    ranges.append((u, v))



# Subroutines



def normalized(u, v):

    return (min(u, v), max(u, v))



def findpath(u, v, visited=None):

    """uからvへの経路 (辺の集合)"""

    if visited is None:

        visited = set()

    if u == v:

        return set()

    if u in visited:

        return None

    visited.add(u)

    for x in adj[u]:

        p = findpath(x, v, visited)

        if p is not None:

            p.add(normalized(u, x))

            return p



def powerset(seq, bag):

    """(seqの部分集合s, bag[e] for e in s の和集合)"""

    if len(seq) <= 1:

        yield ((seq[0],), bag[seq[0]])

        yield ((), set())

    else:

        for s, b in powerset(seq[1:], bag):

            yield ((seq[0],) + s, b | bag[seq[0]])

            yield (s, b)



# Find paths



paths = {}

for u, v in ranges:

    paths[(u, v)] = findpath(u, v)



# いずれかの区間をすべて白にする塗り方の個数

coloring = 0

for s, b in powerset(ranges, paths):

    l = len(s)

    if l <= 0:

        continue

    # b中の辺をすべて白にする塗り方の個数

    c = 2 ** ((n - 1) - len(b))

    # 包除原理

    sign = -1 if l % 2 == 0 else 1    

    coloring += sign * c



# どの区間も黒を含む塗り方の個数

coloring = 2 ** (n - 1) - coloring

print(coloring)

# F - Tree and Constraints



# Read input



n = int(eval(input()))

adj = {a: [] for a in range(1, n + 1)}

for i in range(n - 1):

    a, b = list(map(int, input().split()))

    adj[a].append((b, i))

    adj[b].append((a, i))

m = int(eval(input()))

ranges = [tuple(map(int, input().split())) for i in range(m)]



# Subroutines



def findpath(u, v, parent=None):

    """uからvへの経路 (辺の集合)"""

    if u == v:

        return set()

    for x, i in adj[u]:

        if x == parent:

            continue

        p = findpath(x, v, u)

        if p is not None:

            p.add(i)  # id of edge

            return p

    return None



def powerset(seq, bag):

    """[(seqの部分集合s, bag[e] for e in s の和集合)]"""

    if len(seq) <= 1:

        yield ((seq[0],), bag[seq[0]])

        yield ((), set())

    else:

        for s, b in powerset(seq[1:], bag):

            yield ((seq[0],) + s, b | bag[seq[0]])

            yield (s, b)



# Find paths



paths = [findpath(u, v) for u, v in ranges]



# いずれかの区間をすべて白にする塗り方の個数

white = 0

for s, b in powerset(list(range(m)), paths):

    l = len(s)

    if l <= 0:

        continue

    # b中の辺をすべて白にする塗り方の個数

    w = 2 ** (n - 1 - len(b))

    # 包除原理

    sign = -1 if l % 2 == 0 else 1    

    white += sign * w



# どの区間も黒を含む塗り方の個数

coloring = 2 ** (n - 1) - white

print(coloring)

# F - Tree and Constraints
# Read input
n = int(eval(input()))
adj = {a: [] for a in range(1, n + 1)}
for i in range(n - 1):
    a, b = list(map(int, input().split()))
    adj[a].append(b)
    adj[b].append(a)
m = int(eval(input()))
ranges = []
for i in range(m):
    u, v = list(map(int, input().split()))
    ranges.append((u, v))
# Subroutines
def normalized(u, v):
    return (min(u, v), max(u, v))


def findpath(u, v, visited=None):
    """uからvへの経路 (辺の集合)"""
    if visited is None:
        visited = set()
    if u == v:
        return set()
    if u in visited:
        return None
    visited.add(u)
    for x in adj[u]:
        p = findpath(x, v, visited)
        if p is not None:
            p.add(normalized(u, x))
            return p


def powerset(seq, bag):
    """(seqの部分集合s, bag[e] for e in s の和集合)"""
    if len(seq) <= 1:
        yield ((seq[0],), bag[seq[0]])
        yield ((), set())
    else:
        for s, b in powerset(seq[1:], bag):
            yield ((seq[0],) + s, b | bag[seq[0]])
            yield (s, b)


# Find paths
paths = {}
for u, v in ranges:
    paths[(u, v)] = findpath(u, v)
# いずれかの区間をすべて白にする塗り方の個数
coloring = 0
for s, b in powerset(ranges, paths):
    l = len(s)
    if l <= 0:
        continue
    # b中の辺をすべて白にする塗り方の個数
    c = 2 ** ((n - 1) - len(b))
    # 包除原理
    sign = -1 if l % 2 == 0 else 1
    coloring += sign * c
# どの区間も黒を含む塗り方の個数
coloring = 2 ** (n - 1) - coloring
print(coloring)

# F - Tree and Constraints
# Read input
n = int(eval(input()))
adj = {a: [] for a in range(1, n + 1)}
for i in range(n - 1):
    a, b = list(map(int, input().split()))
    adj[a].append((b, i))
    adj[b].append((a, i))
m = int(eval(input()))
ranges = [tuple(map(int, input().split())) for i in range(m)]
# Subroutines
def findpath(u, v, parent=None):
    """uからvへの経路 (辺の集合)"""
    if u == v:
        return set()
    for x, i in adj[u]:
        if x == parent:
            continue
        p = findpath(x, v, u)
        if p is not None:
            p.add(i)  # id of edge
            return p
    return None


def powerset(seq, bag):
    """[(seqの部分集合s, bag[e] for e in s の和集合)]"""
    if len(seq) <= 1:
        yield ((seq[0],), bag[seq[0]])
        yield ((), set())
    else:
        for s, b in powerset(seq[1:], bag):
            yield ((seq[0],) + s, b | bag[seq[0]])
            yield (s, b)


# Find paths
paths = [findpath(u, v) for u, v in ranges]
# いずれかの区間をすべて白にする塗り方の個数
white = 0
for s, b in powerset(list(range(m)), paths):
    l = len(s)
    if l <= 0:
        continue
    # b中の辺をすべて白にする塗り方の個数
    w = 2 ** (n - 1 - len(b))
    # 包除原理
    sign = -1 if l % 2 == 0 else 1
    white += sign * w
# どの区間も黒を含む塗り方の個数
coloring = 2 ** (n - 1) - white
print(coloring)

-    adj[a].append(b) -    adj[b].append(a) +    adj[a].append((b, i)) +    adj[b].append((a, i)) -ranges = [] -for i in range(m): -    u, v = list(map(int, input().split())) -    ranges.append((u, v)) +ranges = [tuple(map(int, input().split())) for i in range(m)] -def normalized(u, v): -    return (min(u, v), max(u, v)) - - -def findpath(u, v, visited=None): +def findpath(u, v, parent=None): -    if visited is None: -        visited = set() -    if u in visited: -        return None -    visited.add(u) -    for x in adj[u]: -        p = findpath(x, v, visited) +    for x, i in adj[u]: +        if x == parent: +            continue +        p = findpath(x, v, u) -            p.add(normalized(u, x)) +            p.add(i)  # id of edge +    return None -    """(seqの部分集合s, bag[e] for e in s の和集合)""" +    """[(seqの部分集合s, bag[e] for e in s の和集合)]""" -paths = {} -for u, v in ranges: -    paths[(u, v)] = findpath(u, v) +paths = [findpath(u, v) for u, v in ranges] -coloring = 0 -for s, b in powerset(ranges, paths): +white = 0 +for s, b in powerset(list(range(m)), paths): -    c = 2 ** ((n - 1) - len(b)) +    w = 2 ** (n - 1 - len(b)) -    coloring += sign * c +    white += sign * w -coloring = 2 ** (n - 1) - coloring +coloring = 2 ** (n - 1) - white