AtCoder Beginner Contest 152 - Tree and Constraints

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: MEDIUM_HARD

Starter code:

Solutions:
import sys
input = sys.stdin.readline

def main():
	n = int(input())
	Edges = [[] for _ in range(n)]
	for _ in range(n - 1):
		(a, b) = map(int, input().split())
		a -= 1
		b -= 1
		Edges[a].append(b)
		Edges[b].append(a)
	m = int(input())
	C = []
	for _ in range(m):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		C.append((u, v))

	def normalized(u, v):
		return (min(u, v), max(u, v))

	def findpath(u, v, visited=None):
		if visited is None:
			visited = set()
		if u == v:
			return set()
		if u in visited:
			return None
		visited.add(u)
		for x in Edges[u]:
			P = findpath(x, v, visited)
			if P is not None:
				P.add(normalized(u, x))
				return P

	def set_path(Pairs, Paths):
		if len(Pairs) <= 1:
			yield ((Pairs[0],), Paths[Pairs[0]])
			yield ((), set())
		else:
			for (S, P) in set_path(Pairs[1:], Paths):
				yield ((Pairs[0],) + S, P | Paths[Pairs[0]])
				yield (S, P)
	Paths = {}
	for (u, v) in C:
		Paths[u, v] = findpath(u, v)
	ans = pow(2, n - 1)
	for (S, P) in set_path(C, Paths):
		l = len(S)
		if l <= 0:
			continue
		c = pow(2, n - 1 - len(P))
		flag = 1 if l % 2 == 0 else -1
		ans += flag * c
	print(ans)
main()


import sys

def input():
	return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

def main():
	N = int(input())
	repn = [[] for _ in range(N)]
	for i in range(N - 1):
		(a, b) = map(int, input().split())
		repn[a - 1].append((b - 1, i))
		repn[b - 1].append((a - 1, i))
	M = int(input())
	edges = []

	def dfs(v, tv, p=-1):
		if v == tv:
			edges[:] = []
			return True
		for e in repn[v]:
			if e[0] == p:
				continue
			if dfs(e[0], tv, v):
				edges.append(e[1])
				return True
		return False
	edgeset = [0] * M
	for i in range(M):
		(u, v) = map(int, input().split())
		dfs(u - 1, v - 1)
		for id in edges:
			edgeset[i] |= 1 << id
	ans = 0
	for i in range(1 << M):
		mask = 0
		for j in range(M):
			if i >> j & 1:
				mask |= edgeset[j]
		white = bin(mask).count('1')
		val = 1 << N - 1 - white
		if bin(i).count('1') % 2 == 0:
			ans += val
		else:
			ans -= val
	print(ans)
main()


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 = [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)


import sys
input = sys.stdin.readline
import math
from collections import deque
from fractions import gcd
from functools import lru_cache
MOD = 10 ** 9 + 7
INF = float('inf')

def inputI():
	return int(input().strip())

def inputS():
	return input().strip()

def inputIL():
	return list(map(int, input().split()))

def inputSL():
	return list(map(str, input().split()))

def inputILs(n):
	return list((int(input()) for _ in range(n)))

def inputSLs(n):
	return list((input().strip() for _ in range(n)))

def inputILL(n):
	return [list(map(int, input().split())) for _ in range(n)]

def inputSLL(n):
	return [list(map(str, input().split())) for _ in range(n)]

def inv(n):
	return pow(n, MOD - 2, MOD)
kaijo_memo = []

def kaijo(n):
	if len(kaijo_memo) > n:
		return kaijo_memo[n]
	if len(kaijo_memo) == 0:
		kaijo_memo.append(1)
	while len(kaijo_memo) <= n:
		kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
	return kaijo_memo[n]
gyaku_kaijo_memo = []

def gyaku_kaijo(n):
	if len(gyaku_kaijo_memo) > n:
		return gyaku_kaijo_memo[n]
	if len(gyaku_kaijo_memo) == 0:
		gyaku_kaijo_memo.append(1)
	while len(gyaku_kaijo_memo) <= n:
		gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo), MOD - 2, MOD) % MOD)
	return gyaku_kaijo_memo[n]

def nCr(n, r):
	if n == r:
		return 1
	if n < r or r < 0:
		return 0
	ret = 1
	ret = ret * kaijo(n) % MOD
	ret = ret * gyaku_kaijo(r) % MOD
	ret = ret * gyaku_kaijo(n - r) % MOD
	return ret

def factorization(n):
	arr = []
	temp = n
	for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
		if temp % i == 0:
			cnt = 0
			while temp % i == 0:
				cnt += 1
				temp //= i
			arr.append([i, cnt])
	if temp != 1:
		arr.append([temp, 1])
	if arr == []:
		arr.append([n, 1])
	return arr

def lcm(a, b):
	return a * b // gcd(a, b)
N = inputI()
graph = [[] for _ in range(N)]
edges = []
for _ in range(N - 1):
	(a, b) = inputIL()
	edges.append((a - 1, b - 1))
for (a, b) in edges:
	graph[a].append(b)
	graph[b].append(a)
M = inputI()
m = inputILL(M)
prv = [None for i in range(N)]
prv[0] = -1
q = deque([0])
while q:
	u = q.popleft()
	for v in graph[u]:
		if prv[v] == None:
			prv[v] = u
			q.append(v)
to_root = []
for i in range(N):
	s = 0
	now = i
	while now != 0:
		s += pow(2, now)
		now = prv[now]
	to_root.append(s)
ans = 0
for k in range(pow(2, M)):
	J = []
	for i in range(M):
		if k >> i & 1:
			J.append(m[i])
	mask = 0
	for (u, v) in J:
		mask |= to_root[u - 1] ^ to_root[v - 1]
	count = 0
	while mask:
		mask &= mask - 1
		count += 1
	c = 0
	while k:
		k &= k - 1
		c += 1
	sign = 1
	if c % 2 == 1:
		sign = -1
	ans += sign * pow(2, N - 1 - count)
print(ans)


n = int(input())
g = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	g[a - 1].append((b - 1, i))
	g[b - 1].append((a - 1, i))

def path(i, goal, mam=-1):
	if len(g[i][0]) == 1 and g[0] == mam:
		return 0
	else:
		for (j, idx) in g[i]:
			if j == mam:
				continue
			if j == goal:
				return 1 << idx
			p = path(j, goal, i)
			if p > 0:
				return p | 1 << idx
		return 0
m = int(input())
ps = []
for _ in range(m):
	(a, b) = map(int, input().split())
	ps.append(path(a - 1, b - 1))
dp = [0] * (1 << m)
dp[0] = 1
for i in range(n - 1):
	newdp = [0] * (1 << m)
	hit = 0
	for (j, p) in enumerate(ps):
		a = p & 1 << i
		if p & 1 << i:
			hit += 1 << j
	for j in range(1 << m):
		newdp[j | hit] += dp[j]
	for j in range(1 << m):
		dp[j] += newdp[j]
print(dp[-1])


N = int(input())
inf = 10 ** 18
G = [[inf] * N for _ in range(N)]
edges = [[-1] * N for _ in range(N)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	edges[a - 1][b - 1] = i
	edges[b - 1][a - 1] = i
use = [-1] * N
que = [0]
use[0] = 0
while que:
	v = que.pop()
	u = use[v]
	for nv in range(N):
		if edges[v][nv] == -1 or use[nv] != -1:
			continue
		i = edges[v][nv]
		use[nv] = u ^ 1 << i
		que.append(nv)
M = int(input())
uv = [list(map(int, input().split())) for _ in range(M)]
used = [0] * (1 << M)
cnt = [0] * (1 << M)
ans = 0
for s in range(1, 1 << M):
	for i in range(M):
		if s >> i & 1:
			(u, v) = uv[i]
			(u, v) = (u - 1, v - 1)
			p = s ^ 1 << i
			used[s] = used[p] | use[u] ^ use[v]
			cnt[s] = cnt[p] ^ 1
			break
	res = 0
	for i in range(N - 1):
		if used[s] & 1 << i:
			res += 1
	ans += (-1) ** cnt[s] * pow(2, N - 1 - res)
print(pow(2, N - 1) + ans)


n = int(input())
ab = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(n - 1)]
m = int(input())
uv = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(m)]
e = [[] for _ in range(n)]
i = 0
for (a, b) in ab:
	e[a].append([b, i])
	e[b].append([a, i])
	i += 1

def func(x, g, p):
	if len(e[x]) == 1 and p != -1:
		return -1
	for edge in e[x]:
		if edge[0] == p:
			continue
		elif edge[0] == g:
			return 1 << edge[1]
		temp = func(edge[0], g, x)
		if temp >= 0:
			return temp + (1 << edge[1])
	return -1
p = []
for (u, v) in uv:
	p.append(func(u, v, -1))
flag = -1
ans = 2 ** (n - 1)
base = 2 ** (n - 1)
for i in range(1, 1 << m):
	temp = list(reversed(list(str(bin(i)))[2:]))
	c = 0
	for (j, x) in enumerate(temp):
		if x == '1':
			c = c | p[j]
	hoge = str(bin(base + c)).count('0') - 1
	if temp.count('1') % 2 == 0:
		flag = 1
	else:
		flag = -1
	ans += flag * 2 ** hoge
print(ans)


def popcnt(n):
	c = (n & 6148914691236517205) + (n >> 1 & 6148914691236517205)
	c = (c & 3689348814741910323) + (c >> 2 & 3689348814741910323)
	c = (c & 1085102592571150095) + (c >> 4 & 1085102592571150095)
	c = (c & 71777214294589695) + (c >> 8 & 71777214294589695)
	c = (c & 281470681808895) + (c >> 16 & 281470681808895)
	c = (c & 4294967295) + (c >> 32 & 4294967295)
	return c

def dfs(g, root, w):
	parent = [-1] * n
	enum = [-1] * n
	q = [root]
	while q:
		v = q.pop()
		for (c, i) in g[v]:
			if c != parent[v]:
				parent[c] = v
				enum[c] = i
				q.append(c)
	a = 0
	while w != root:
		a |= 1 << enum[w]
		w = parent[w]
	return a
import sys
sys.setrecursionlimit(10 ** 6)
readline = sys.stdin.readline
read = sys.stdin.read
MOD = 10 ** 9 + 7
n = int(input())
g = [[] for _ in range(n)]
for i in range(n - 1):
	(a, b) = [int(i) - 1 for i in readline().split()]
	g[a].append((b, i))
	g[b].append((a, i))
m = int(input())
res = [0] * m
for i in range(m):
	(v, w) = [int(i) - 1 for i in readline().split()]
	res[i] = dfs(g, v, w)
ans = 1 << n - 1
M = 1 << m
for mask in range(1, M):
	r = 0
	for j in range(m):
		if mask & 1 << j:
			r |= res[j]
	r = popcnt(r)
	c = popcnt(mask)
	if c % 2:
		ans -= 1 << n - 1 - r
	else:
		ans += 1 << n - 1 - r
print(ans)


import sys
input = sys.stdin.readline
N = int(input())
G = [[] for _ in range(N + 1)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	G[a].append((b, i))
	G[b].append((a, i))

def get_path(u, v):
	stack = [u]
	prev = [None] * (N + 1)
	visited = [False] * (N + 1)
	visited[u] = True
	while stack:
		node = stack.pop()
		for (next, i) in G[node]:
			if not visited[next]:
				visited[next] = True
				prev[next] = (node, i)
				stack.append(next)
	path = 0
	node = v
	while node != u:
		(p, i) = prev[node]
		node = p
		path += 1 << i
	return path

def count(bits, N):
	cnt = 0
	for i in range(N):
		if bits >> i & 1 == 1:
			cnt += 1
	return cnt
M = int(input())
uv = [tuple(map(int, input().split())) for _ in range(M)]
paths = [get_path(u, v) for (u, v) in uv]
ans = 2 ** (N - 1)
for bit in range(1, 1 << M):
	cnt = 0
	tmp = 0
	for i in range(M):
		if bit >> i & 1 == 1:
			cnt += 1
			tmp |= paths[i]
	ans += (-1) ** cnt * 2 ** (N - 1 - count(tmp, N - 1))
print(ans)


from itertools import product
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)]

class Node:

	def __init__(self, nodeid, parent=None):
		self.nodeid = nodeid
		self.parent = parent
		self.children = []

	def add_child(self, nodeid, edgeid):
		child = Node(nodeid, parent=self)
		self.children.append((child, edgeid))

	def parents(self):
		if self.parent == None:
			return [self.nodeid]
		else:
			return [self.nodeid] + self.parent.parents()

	def path(self, to):
		if to == self.nodeid:
			return []
		for (child, edgeid) in self.children:
			try:
				ret = [edgeid] + child.path(to)
				return ret
			except ValueError:
				pass
		raise ValueError
root = Node(1)
nodes = {1: root}
leef = [root]
while len(leef) > 0:
	node = leef.pop()
	parentid = node.parent and node.parent.nodeid
	for (i, (a, b)) in enumerate(ab):
		if a == node.nodeid and b != parentid:
			node.add_child(b, i)
			leef.append(node.children[-1][0])
			nodes[b] = node.children[-1][0]
		elif b == node.nodeid and a != parentid:
			node.add_child(a, i)
			leef.append(node.children[-1][0])
			nodes[a] = node.children[-1][0]
constraints = [0] * M
for (i, (u, v)) in enumerate(uv):
	parents_u = nodes[u].parents()
	for p in nodes[v].parents():
		if p in parents_u:
			break
	for j in nodes[p].path(u):
		constraints[i] += pow(2, j)
	for j in nodes[p].path(v):
		constraints[i] += pow(2, j)
ans = 0
for idx in product([True, False], repeat=M):
	sumidx = sum(idx)
	constraint = 0
	for (i, flg) in enumerate(idx):
		if flg:
			constraint = constraint | constraints[i]
	C = bin(constraint)[2:].count('1')
	ans += pow(2, N - 1 - C) * (-1) ** (sumidx % 2)
print(ans)


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(b), 2) for b in zip(*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])


from collections import deque
N = int(input())
dic = {}
for i in range(N - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	c = N + i
	if a not in dic:
		dic[a] = []
	if b not in dic:
		dic[b] = []
	dic[c] = []
	dic[a].append(c)
	dic[b].append(c)
	dic[c].append(a)
	dic[c].append(b)
M = int(input())
bitlis = []
for loop in range(M):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	bits = [0] * N + [2 ** i for i in range(N - 1)]
	dis = [float('inf')] * (2 * N - 1)
	dis[u] = 0
	q = deque([u])
	while len(q) > 0:
		now = q.popleft()
		for nex in dic[now]:
			if dis[nex] > dis[now] + 1:
				dis[nex] = dis[now] + 1
				bits[nex] += bits[now]
				q.append(nex)
	bitlis.append(bits[v])
uselis = [0] * (M + 1)
for use in range(2 ** M):
	white = 0
	usenum = 0
	for i in range(M):
		if use & 2 ** i > 0:
			white |= bitlis[i]
			usenum += 1
	able = N - 1
	ws = format(white, 'b')
	for i in ws:
		if i == '1':
			able -= 1
	uselis[usenum] += 2 ** able
ans = 2 ** (N - 1)
for i in range(M):
	i += 1
	if i % 2 == 1:
		ans -= uselis[i]
	else:
		ans += uselis[i]
print(ans)


import sys
input = sys.stdin.buffer.readline
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)]

def popcnt(n):
	c = (n & 6148914691236517205) + (n >> 1 & 6148914691236517205)
	c = (c & 3689348814741910323) + (c >> 2 & 3689348814741910323)
	c = (c & 1085102592571150095) + (c >> 4 & 1085102592571150095)
	c = (c & 71777214294589695) + (c >> 8 & 71777214294589695)
	c = (c & 281470681808895) + (c >> 16 & 281470681808895)
	c = (c & 4294967295) + (c >> 32 & 4294967295)
	return c
graph = [[] for _ in range(N + 1)]
for (a, b) in AB:
	graph[a].append(b)
	graph[b].append(a)

def make_tree(graph, root) -> (list, list):
	INF = 10 ** 15
	dist = [INF] * len(graph)
	parent = [-1] * len(graph)
	stack = [root]
	dist[root] = 0
	parent[root] = root
	while stack:
		s = stack.pop()
		for g in graph[s]:
			if dist[g] > dist[s] + 1:
				dist[g] = dist[s] + 1
				parent[g] = s
				stack.append(g)
	return (dist, parent)

def lca(u, v, dist, parent):
	(distu, distv) = (dist[u], dist[v])
	if distu > distv:
		for _ in range(distu - distv):
			u = parent[u]
	if distv > distu:
		for _ in range(distv - distu):
			v = parent[v]
	while u != v:
		(u, v) = (parent[u], parent[v])
	return u
(dist, parent) = make_tree(graph, 1)
tree_lca = []
for i in range(M):
	tmp = 0
	(u, v) = UV[i]
	l = lca(u, v, dist, parent)
	while u != l:
		tmp |= 1 << u
		u = parent[u]
	while v != l:
		tmp |= 1 << v
		v = parent[v]
	tree_lca.append(tmp)
answer = 2 ** (N - 1)
for i in range(1, 2 ** M):
	tmp = 0
	for j in range(M):
		if i >> j & 1:
			tmp |= tree_lca[j]
	cnt = popcnt(tmp)
	if popcnt(i) % 2 == 1:
		answer -= 2 ** (N - 1 - cnt)
	else:
		answer += 2 ** (N - 1 - cnt)
print(answer)


from functools import reduce

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:
				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()


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10 ** 9))
write = lambda x: sys.stdout.write(x + '\n')
from collections import defaultdict
from queue import deque
import itertools
import functools

def find(start, goal):
	q = deque([start])
	seen = [None] * n
	seen[start] = -1
	while q:
		u = q.pop()
		d = seen[u]
		if u == goal:
			break
		for v in ns[u]:
			if seen[v] is None:
				seen[v] = u
				q.appendleft(v)
	u = goal
	es = []
	while True:
		t = (min(u, seen[u]), max(u, seen[u]))
		es.append(t)
		if seen[u] == start:
			break
		u = seen[u]
	return set(es)
n = int(input())
ns = defaultdict(set)
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	ns[u - 1].add(v - 1)
	ns[v - 1].add(u - 1)
ans = 0
m = int(input())
paths = [None] * m
for i in range(m):
	(u, v) = map(int, input().split())
	paths[i] = find(u - 1, v - 1)
ans = 0

def dfs(ind, s, ans):
	if len(ind) == m:
		if True in ind:
			ans += 2 ** (n - 1 - len(s)) * (-1) ** ((sum(ind) + 1) % 2)
		return ans
	ans = dfs(ind + [True], s | paths[len(ind)], ans)
	ans = dfs(ind + [False], s, ans)
	return ans
ans = dfs([], set(), 0)
print(2 ** (n - 1) - ans)


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10 ** 9))
write = lambda x: sys.stdout.write(x + '\n')
from collections import defaultdict
from queue import deque
import itertools
import functools

def find(start, goal):
	q = deque([start])
	seen = [None] * n
	seen[start] = -1
	while q:
		u = q.pop()
		d = seen[u]
		if u == goal:
			break
		for v in ns[u]:
			if seen[v] is None:
				seen[v] = u
				q.appendleft(v)
	u = goal
	es = 0
	while True:
		t = (min(u, seen[u]), max(u, seen[u]))
		es |= 1 << uv2e[u, seen[u]]
		if seen[u] == start:
			break
		u = seen[u]
	return es
n = int(input())
ns = defaultdict(set)
uv2e = {}
for i in range(n - 1):
	(u, v) = map(int, input().split())
	ns[u - 1].add(v - 1)
	ns[v - 1].add(u - 1)
	uv2e[u - 1, v - 1] = i
	uv2e[v - 1, u - 1] = i
ans = 0
m = int(input())
paths = [None] * m
for i in range(m):
	(u, v) = map(int, input().split())
	paths[i] = find(u - 1, v - 1)
ans = 0

def bitlen(b):
	tmp = 0
	for i in range(n - 1):
		tmp += b & 1 << i > 0
	return tmp
for ind in itertools.product(*[(False, True) for _ in range(m)]):
	num = sum(ind) + 1
	if num == 1:
		continue
	c = 2 ** (n - 1 - bitlen(functools.reduce(lambda x, y: x | y, (paths[i] for i in range(m) if ind[i]), 0)))
	ans += (-1) ** num * c
print(2 ** (n - 1) - ans)


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) = 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) = map(int, input().split())
	u -= 1
	v -= 1
	conditions.append(dfs(u, v, links))
ans = 0
for i in range(1 << m):
	cnd_cnt = bin(i).count('1')
	bit = 0
	k = i
	while k:
		b = k & -k
		j = b.bit_length() - 1
		bit |= conditions[j]
		k ^= b
	free_link_cnt = n - 1 - bin(bit).count('1')
	val = 2 ** free_link_cnt
	if cnd_cnt % 2:
		ans -= val
	else:
		ans += val
print(ans)


n = int(input())
info = [list(map(int, input().split())) for i in range(n - 1)]
m = int(input())
path = [list(map(int, input().split())) for i in range(m)]
tree = [[] for i in range(n)]
memo = {}
for i in range(n - 1):
	(a, b) = info[i]
	a -= 1
	b -= 1
	tree[a].append(b)
	tree[b].append(a)
	memo[min(a, b), max(a, b)] = i

def dfs(par, pos, goal):
	if pos == goal:
		return True
	for child in tree[pos]:
		if child == par:
			continue
		if dfs(pos, child, goal):
			res.append((min(pos, child), max(pos, child)))
			return True
	return False
li_path = [0] * m
for i in range(m):
	res = []
	(s, g) = path[i]
	s -= 1
	g -= 1
	dfs(-1, s, g)
	tmp = 0
	for j in res:
		tmp += 1 << memo[j]
	li_path[i] = tmp
ans = 0
for bit_state in range(1 << m):
	mask = 0
	cnt = 0
	for i in range(m):
		if bit_state & 1 << i:
			cnt += 1
			mask |= li_path[i]
	num_n = bin(mask).count('1')
	if cnt % 2 == 0:
		ans += 2 ** (n - 1 - num_n)
	else:
		ans -= 2 ** (n - 1 - num_n)
print(ans)


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)


import sys

def main():
	input = sys.stdin.readline
	N = int(input())
	E = [[] for _ in range(N)]
	for i in range(N - 1):
		(a, b) = map(int, input().split())
		(a, b) = (a - 1, b - 1)
		E[a].append((b, i))
		E[b].append((a, i))

	def dfs(s, g):
		par = [(-1, -1)] * N
		par[s] = (s, -1)
		stack = [s]
		while stack:
			v = stack.pop()
			for (to, i) in E[v]:
				if par[to][0] >= 0:
					continue
				par[to] = (v, i)
				if to == g:
					break
				stack.append(to)
		r = 0
		v = g
		while v != s:
			(v, i) = par[v]
			r |= 1 << i
		return r
	M = int(input())
	path = [0] * M
	for i in range(M):
		(u, v) = map(int, input().split())
		(u, v) = (u - 1, v - 1)
		path[i] = dfs(u, v)

	def calc(s):
		return 1 << N - 1 - bin(s).count('1')
	i_ans = 0
	for p in range(1, 1 << M):
		is_odd = 0
		s = 0
		for i in range(M):
			if p & 1:
				s |= path[i]
				is_odd ^= 1
			p >>= 1
		if is_odd:
			i_ans += calc(s)
		else:
			i_ans -= calc(s)
	print((1 << N - 1) - i_ans)
main()


import sys
sys.setrecursionlimit(2147483647)
INF = float('inf')
MOD = 10 ** 9 + 7
input = lambda : sys.stdin.readline().rstrip()

def resolve():
	n = int(input())
	E = [[] for _ in range(n)]
	edge_to_idx = {}
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		E[u].append(v)
		E[v].append(u)
		edge_to_idx[u, v] = edge_to_idx[v, u] = i

	def path(source, target):
		par = [-1] * n
		stack = [(source, -1)]
		while stack:
			(v, p) = stack.pop()
			for nv in E[v]:
				if nv == p:
					continue
				par[nv] = v
				stack.append((nv, v))
		res = 0
		while target != source:
			res |= 1 << edge_to_idx[target, par[target]]
			target = par[target]
		return res
	m = int(input())
	constraints = [None] * m
	for i in range(m):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		constraints[i] = path(u, v)
	res = 1 << n - 1
	for U in range(1, 1 << m):
		coef = 1 if bin(U).count('1') & 1 else -1
		binary = 0
		for i in range(m):
			if U >> i & 1:
				binary |= constraints[i]
		cnt = n - 1 - bin(binary).count('1')
		res -= coef * (1 << cnt)
	print(res)
resolve()


N = int(input())
edge = {i: [] for i in range(1, N + 1)}
for i in range(0, N - 1):
	(a, b) = map(int, input().split())
	edge[a].append((b, i))
	edge[b].append((a, i))
parent = {i: -1 for i in range(1, N + 1)}
depth = {i: -1 for i in range(1, N + 1)}
parent[1] = (0, -1)
depth[1] = 0
q = set([1])
sub = set([])
while q:
	while q:
		x = q.pop()
		for (b, i) in edge[x]:
			if parent[b] == -1:
				parent[b] = (x, i)
				depth[b] = depth[x] + 1
				sub.add(b)
		if not q:
			q = sub
			sub = set([])
			break
M = int(input())
condition = [[] for i in range(0, M)]
for i in range(0, M):
	(u, v) = map(int, input().split())
	ans = set([])
	while depth[u] != depth[v]:
		if depth[u] > depth[v]:
			(U, j) = parent[u]
			ans.add(j)
			u = U
		else:
			(V, j) = parent[v]
			ans.add(j)
			v = V
	while u != v:
		(U, j) = parent[u]
		ans.add(j)
		u = U
		(V, j) = parent[v]
		ans.add(j)
		v = V
	con = 0
	for j in ans:
		con += 2 ** j
	condition[i] = con
ans = 2 ** (N - 1)
ban = 0
for i in range(1, 2 ** M):
	num = bin(i).count('1')
	s = 0
	for j in range(0, M):
		if i >> j & 1 == 1:
			s = s | condition[j]
	n = bin(s).count('1')
	if num % 2 == 1:
		ban += 2 ** (N - 1 - n)
	else:
		ban -= 2 ** (N - 1 - n)
print(ans - ban)


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:
				return res | 1 << e.edge_id
		return -1

	def popcnt(n):
		c = (n & 6148914691236517205) + (n >> 1 & 6148914691236517205)
		c = (c & 3689348814741910323) + (c >> 2 & 3689348814741910323)
		c = (c & 1085102592571150095) + (c >> 4 & 1085102592571150095)
		c = (c & 71777214294589695) + (c >> 8 & 71777214294589695)
		c = (c & 281470681808895) + (c >> 16 & 281470681808895)
		c = (c & 4294967295) + (c >> 32 & 4294967295)
		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)
main()


n = int(input())
g = [[] for _ in range(n)]
edge = {}
for i in range(n - 1):
	(a, b) = map(int, input().split())
	g[a - 1].append(b - 1)
	g[b - 1].append(a - 1)
	edge[a - 1, b - 1] = i
	edge[b - 1, a - 1] = i
m = int(input())

def dfs(u, v):
	visited = [False] * n
	visited[u] = True
	stack = [u]
	prev = [-1] * n
	while stack:
		uu = stack.pop()
		for vv in g[uu]:
			if not visited[vv]:
				visited[vv] = True
				prev[vv] = uu
				stack.append(vv)
		if prev[v] != -1:
			break
	bin_edge = 0
	head = v
	while head != u:
		bin_edge += 1 << edge[head, prev[head]]
		head = prev[head]
	return bin_edge
intv = [0] * m
for i in range(m):
	(u, v) = map(int, input().split())
	intv[i] = dfs(u - 1, v - 1)
mm = 1 << m
ans = 0
for i in range(mm):
	a = 0
	cnt = 0
	for j in range(m):
		if i >> j & 1:
			cnt += 1
			a = a | intv[j]
	white = str(bin(a)).count('1')
	ans += (-1) ** cnt * 2 ** (n - 1 - white)
print(abs(ans))


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 & 6148914691236517205) + (n >> 1 & 6148914691236517205)
	c = (c & 3689348814741910323) + (c >> 2 & 3689348814741910323)
	c = (c & 1085102592571150095) + (c >> 4 & 1085102592571150095)
	c = (c & 71777214294589695) + (c >> 8 & 71777214294589695)
	c = (c & 281470681808895) + (c >> 16 & 281470681808895)
	c = (c & 4294967295) + (c >> 32 & 4294967295)
	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)


from collections import defaultdict, deque
import sys, heapq, bisect, math, itertools, string, queue, copy, time
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
mod = 10 ** 9 + 7
eps = 10 ** (-7)

def inp():
	return int(sys.stdin.readline())

def inpl():
	return list(map(int, sys.stdin.readline().split()))

def inpl_str():
	return list(sys.stdin.readline().split())
N = inp()
lines = [[] for _ in range(N)]
for i in range(N - 1):
	(a, b) = inpl()
	a -= 1
	b -= 1
	lines[a].append((b, i))
	lines[b].append((a, i))

def dfs(s, b, v):
	if s == v:
		return set()
	else:
		for (t, i) in lines[s]:
			if t == b:
				continue
			ret = dfs(t, s, v)
			if ret is not None:
				ret.add(i)
				return ret
		return None
M = inp()
mm = []
for m in range(M):
	(u, v) = inpl()
	u -= 1
	v -= 1
	mm.append(dfs(u, -1, v))
dp = [0] * (1 << M)
dp[0] = 1
for i in range(N - 1):
	tmp = 0
	for (b, m) in enumerate(mm):
		if i in m:
			tmp += 1 << b
	for b in reversed(range(1 << M)):
		dp[b | tmp] += dp[b]
print(dp[-1])


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)]
from collections import deque
links = [[] for _ in range(n + 1)]
for (ind, val) in enumerate(ab):
	(a, b) = val
	links[a].append((ind, b))
	links[b].append((ind, a))

def bfs(start, end):
	parent = [[-1, -1] for _ in range(n + 1)]
	d = deque()
	d.append(start)
	done = set()
	while d:
		tmp = d.popleft()
		done.add(tmp)
		for i in links[tmp]:
			(link_ind, j) = i
			if not j in done:
				parent[j] = [tmp, link_ind]
				d.append(j)
	route = []
	while True:
		route.append(parent[end][1])
		end = parent[end][0]
		if end == start:
			break
	return route[::-1]
links_key = [0] * (n - 1)
for (i, se) in enumerate(uv):
	(start, end) = se
	route = bfs(start, end)
	for j in route:
		links_key[j] = links_key[j] | 1 << i
dp = [[0] * 2 ** m for _ in range(n)]
dp[0][0] = 1
for i in range(n - 1):
	for j in range(2 ** m):
		dp[i + 1][j] += dp[i][j]
		dp[i + 1][j | links_key[i]] += dp[i][j]
print(dp[-1][-1])


from collections import deque
n = int(input())
Graph = [[] for _ in range(n)]
edge = {}
for i in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	Graph[a].append(b)
	Graph[b].append(a)
	edge[1000 * a + b] = i
	edge[1000 * b + a] = i
data = []

def f(u, v):
	prev = [u] * n
	used = [False] * n
	que = deque([u])
	while que:
		now = que.popleft()
		for nex_v in Graph[now]:
			if used[nex_v]:
				continue
			prev[nex_v] = now
			used[nex_v] = True
			que.append(nex_v)
			if nex_v == v:
				break
	path = [v]
	path_edge = []
	t = v
	while prev[t] != u:
		path.append(prev[t])
		path_edge.append(edge[1000 * t + prev[t]])
		t = prev[t]
	path_edge.append(edge[1000 * t + prev[t]])
	path.append(u)
	return path_edge
m = int(input())
for i in range(m):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	path = f(u, v)
	data.append(path[::-1])
ans = 2 ** (n - 1)
for i in range(1, 1 << m):
	now = []
	for j in range(m):
		if i >> j & 1:
			now.append(j)
	this = [True] * (n - 1)
	for j in now:
		for k in data[j]:
			this[k] = False
	ponta = 1
	q = 0
	for j in range(n - 1):
		if this[j]:
			ponta *= 2
			q += 1
	if len(now) % 2 == 0:
		ans += ponta
	else:
		ans -= ponta
print(ans)


from collections import deque
N = int(input())
adj = [[] for i in range(N + 1)]
ve = {}
for i in range(1, N):
	(a, b) = map(int, input().split())
	adj[a].append(b)
	adj[b].append(a)
	ve[a, b] = ve[b, a] = i
l = [[set() for j in range(N + 1)] for i in range(N + 1)]
q = deque()
for i in range(1, N + 1):
	r = [False] * (N + 1)
	q.append(i)
	r[i] = True
	while q:
		u = q.popleft()
		for v in adj[u]:
			if r[v]:
				continue
			l[i][v].update(l[i][u])
			l[i][v].add(ve[u, v])
			q.append(v)
			r[v] = True
M = int(input())
c = [set()]
for i in range(1, M + 1):
	(u, v) = map(int, input().split())
	c.append((u, v))
ans = 2 ** (N - 1)
for k in range(1, 1 << M):
	V = set()
	d = 0
	for i in range(1, M + 1):
		if k >> i - 1 & 1:
			d += 1
			(u, v) = c[i]
			V |= l[u][v]
	temp = 2 ** (N - 1 - len(V))
	if d % 2 == 1:
		ans -= temp
	elif d % 2 == 0:
		ans += temp
print(ans)


from collections import deque

def solve(s, t):
	par = {}
	par[s] = -1
	q = deque([s])
	while q:
		v = q.pop()
		for nxt_v in tree[v]:
			if nxt_v in par:
				continue
			else:
				q.append(nxt_v)
				par[nxt_v] = v
	res = []
	while True:
		if par[t] != -1:
			res.append(edge[min(t, par[t]), max(t, par[t])])
			t = par[t]
		else:
			return res
n = int(input())
info = [list(map(int, input().split())) for i in range(n - 1)]
m = int(input())
const = [list(map(int, input().split())) for i in range(m)]
tree = [[] for i in range(n)]
edge = {}
for i in range(n - 1):
	(a, b) = info[i]
	a -= 1
	b -= 1
	edge[min(a, b), max(a, b)] = i
	tree[a].append(b)
	tree[b].append(a)
bit_v = [0] * m
for i in range(m):
	(s, t) = const[i]
	s -= 1
	t -= 1
	bit_state = 0
	for mask in solve(s, t):
		bit_state |= 1 << mask
	bit_v[i] = bit_state
ans = 0
for bit_state in range(1, 1 << m):
	bit_cnt = bin(bit_state).count('1')
	mask = 0
	for i in range(m):
		if bit_state & 1 << i:
			mask |= bit_v[i]
	if bit_cnt % 2 == 0:
		ans -= 2 ** (n - 1 - bin(mask).count('1'))
	else:
		ans += 2 ** (n - 1 - bin(mask).count('1'))
print(2 ** (n - 1) - ans)


N = int(input())
X = [[] for i in range(N)]
for i in range(N - 1):
	(x, y) = map(int, input().split())
	X[x - 1].append(y - 1)
	X[y - 1].append(x - 1)
P = [-1] * N
DE = [0] * N
Q = [0]
while Q:
	i = Q.pop()
	for a in X[i][::-1]:
		if a != P[i]:
			P[a] = i
			DE[a] = DE[i] + 1
			X[a].remove(i)
			Q.append(a)

def lp(u, v):
	t = 0
	while u != v:
		if DE[u] > DE[v]:
			t += 1 << u - 1
			u = P[u]
		elif DE[u] < DE[v]:
			t += 1 << v - 1
			v = P[v]
		else:
			t += 1 << u - 1
			t += 1 << v - 1
			u = P[u]
			v = P[v]
	return t
Y = []
M = int(input())
for _ in range(M):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	Y.append(lp(a, b))

def popcnt(n):
	return bin(n).count('1')
D = {1 << i: i for i in range(50)}
Z = [0] * (1 << M)
ans = 0
CC = [0] * N
for m in range(1 << M):
	a = m & -m
	if a == m:
		if a == 0:
			Z[m] = 0
		else:
			Z[m] = Y[D[a]]
	else:
		Z[m] = Z[m ^ a] | Y[D[a]]
	CC[N - 1 - popcnt(Z[m])] += 1 if popcnt(m) & 1 == 0 else -1
print(sum([2 ** i * CC[i] for i in range(N)]))


N = int(input())
E = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	E[a - 1].append(b - 1)
	E[b - 1].append(a - 1)
parent = [None] * N
depth = [0] * N
d = 0
queue = [0]
while queue:
	d += 1
	queue_new = []
	for q in queue:
		for e in E[q]:
			if e == parent[q]:
				continue
			parent[e] = q
			depth[e] = d
			queue_new.append(e)
	queue = queue_new
ancestor = [[None] * N for _ in range(N)]
for a in range(N):
	for b in range(a, N):
		_a = a
		_b = b
		while _a != _b:
			if depth[_a] < depth[_b]:
				_b = parent[_b]
			else:
				_a = parent[_a]
		ancestor[a][b] = ancestor[b][a] = _a
M = int(input())
P = []
for _ in range(M):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	w = ancestor[u][v]
	path = set()
	while u != w:
		_u = parent[u]
		path.add(u * N + _u)
		u = _u
	while v != w:
		_v = parent[v]
		path.add(v * N + _v)
		v = _v
	P.append(path)
ans = 0
n1 = N - 1
for k in range(2 ** M):
	path = set()
	n = 0
	for (i, p) in enumerate(P):
		if k >> i & 1:
			path |= p
			n += 1
	if n == 0:
		continue
	sign = +1 if n & 1 else -1
	ans += sign * pow(2, n1 - len(path))
print(pow(2, N - 1) - ans)


from itertools import combinations
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
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 dfs(s, g):
	kouho = 0
	par = [(0, 0)] * (n + 1)
	stack = []
	stack.append(s)
	while stack:
		v = stack.pop()
		if v == g:
			break
		for (u, i) in graph[v]:
			if u == par[v][0]:
				continue
			par[u] = (v, i)
			stack.append(u)
	p = g
	(q, i) = par[p]
	while q > 0:
		kouho |= 1 << i
		p = q
		(q, i) = par[q]
	return kouho

def popcnt(n):
	c = (n & 6148914691236517205) + (n >> 1 & 6148914691236517205)
	c = (c & 3689348814741910323) + (c >> 2 & 3689348814741910323)
	c = (c & 1085102592571150095) + (c >> 4 & 1085102592571150095)
	c = (c & 71777214294589695) + (c >> 8 & 71777214294589695)
	c = (c & 281470681808895) + (c >> 16 & 281470681808895)
	c = (c & 4294967295) + (c >> 32 & 4294967295)
	return c
sets = [0 for _ in range(m)]
for (idx, (u, v)) in enumerate(UV):
	sets[idx] = dfs(u, v)
ans = 0
for i in range(1, m + 1):
	kumiawase = list(combinations(range(m), i))
	for kumi in kumiawase:
		temp = 0
		for j in range(i):
			temp |= sets[kumi[j]]
		num = popcnt(temp)
		ans += (-1) ** (i + 1) * (pow(2, n - 1) - pow(2, n - 1 - num))
print(ans)


def main():
	import sys
	input = sys.stdin.readline
	N = int(input())
	E = [[] for _ in range(N)]
	for i in range(N - 1):
		(a, b) = map(int, input().split())
		a -= 1
		b -= 1
		E[a].append((b, i))
		E[b].append((a, i))
	EG = []

	def dfs(u, v, p):
		if u == v:
			return True
		for (t, i) in E[u]:
			if t == p:
				continue
			if dfs(t, v, u):
				EG.append(i)
				return True
		return False
	M = int(input())
	EM = []
	for i in range(M):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		EM.append((u, v))
	ES = []
	for i in range(M):
		(u, v) = EM[i]
		EG = []
		dfs(u, v, -1)
		ES.append((u, v, EG))
	ans = 0
	for i in range(1 << M):
		EG2 = []
		bc = 0
		for j in range(M):
			if i >> j & 1 == 1:
				bc += 1
				EG2 += ES[j][2]
		p = len(set(EG2))
		if bc % 2 == 0:
			ans += 2 ** (N - 1 - p)
		else:
			ans -= 2 ** (N - 1 - p)
	print(ans)
main()


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 & 6148914691236517205) + (n >> 1 & 6148914691236517205)
	c = (c & 3689348814741910323) + (c >> 2 & 3689348814741910323)
	c = (c & 1085102592571150095) + (c >> 4 & 1085102592571150095)
	c = (c & 71777214294589695) + (c >> 8 & 71777214294589695)
	c = (c & 281470681808895) + (c >> 16 & 281470681808895)
	c = (c & 4294967295) + (c >> 32 & 4294967295)
	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)


(N,) = map(int, input().split())
G = [set() for _ in range(N + 1)]
d = dict()
for i in range(N - 1):
	(a, b) = map(int, input().split())
	G[a].add(b)
	G[b].add(a)
	d[a, b] = i
	d[b, a] = i
ps = []
(M,) = map(int, input().split())
for _ in range(M):
	(a, b) = map(int, input().split())
	stack = [a]
	path = []
	vs = set([a])
	while stack:
		v = stack.pop()
		if v > 0:
			path.append(v)
			if v == b:
				break
			vs.add(v)
			for u in G[v]:
				if u in vs:
					continue
				vs.add(u)
				stack += [-v, u]
		else:
			path.pop()
	es = 0
	for i in range(len(path) - 1):
		es += 1 << d[path[i], path[i + 1]]
	ps.append(es)
r = 0
for i in range(2 ** M):
	p = m = j = 0
	x = 0
	while i:
		if i % 2:
			x = x | ps[j]
			p += 1
		i >>= 1
		j += 1
	r += (-1 if p % 2 else 1) * (1 << N - 1 - bin(x).count('1'))
print(r)


from collections import deque
N = int(input())
edge = [[] for _ in range(N)]
for n in range(N - 1):
	(a, b) = map(int, input().split())
	edge[a - 1].append([b - 1, n])
	edge[b - 1].append([a - 1, n])

def bfs(s: int, g: int):
	in_edge = [-1] * N
	par = [-1] * N
	flag = False
	que = deque([s])
	while que:
		v = que.popleft()
		for (w, n) in edge[v]:
			if w == par[v]:
				continue
			in_edge[w] = n
			par[w] = v
			if w == g:
				flag = True
				break
			que.append(w)
		if flag:
			break
	path = 0
	cur = g
	while in_edge[cur] >= 0:
		path |= 1 << in_edge[cur]
		cur = par[cur]
	return path
M = int(input())
path = [0] * M
for i in range(M):
	(u, v) = map(int, input().split())
	path[i] = bfs(u - 1, v - 1)
ans = 0
for bit in range(1 << M):
	val = 0
	for i in range(M):
		if bit >> i & 1:
			val |= path[i]
	if bin(bit).count('1') % 2 == 0:
		ans += 1 << N - 1 - bin(val).count('1')
	else:
		ans -= 1 << N - 1 - bin(val).count('1')
print(ans)


import sys
sys.setrecursionlimit(10 ** 7)
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right
from collections import deque
from collections import Counter
from itertools import accumulate, combinations, permutations
from heapq import heapify, heappop, heappush
from functools import lru_cache
from decimal import Decimal

def input():
	x = sys.stdin.readline()
	return x[:-1] if x[-1] == '\n' else x

def printl(li):
	_ = print(*li, sep='\n') if li else None

def argsort(s, return_sorted=False):
	inds = sorted(range(len(s)), key=lambda k: s[k])
	if return_sorted:
		return (inds, [s[i] for i in inds])
	return inds

def alp2num(c, cap=False):
	return ord(c) - 97 if not cap else ord(c) - 65

def num2alp(i, cap=False):
	return chr(i + 97) if not cap else chr(i + 65)

def matmat(A, B):
	(K, N, M) = (len(B), len(A), len(B[0]))
	return [[sum([A[i][k] * B[k][j] for k in range(K)]) for j in range(M)] for i in range(N)]

def matvec(M, v):
	(N, size) = (len(v), len(M))
	return [sum([M[i][j] * v[j] for j in range(N)]) for i in range(size)]

def T(M):
	(n, m) = (len(M), len(M[0]))
	return [[M[j][i] for j in range(n)] for i in range(m)]

def main():
	mod = 1000000007
	N = int(input())

	def tree_init(N):
		edgelist = [[] for _ in range(N)]
		for (i, (a, b)) in enumerate([map(int, input().split()) for i in range(N - 1)]):
			edgelist[a - 1].append((b - 1, i))
			edgelist[b - 1].append((a - 1, i))
		return edgelist
	edge = tree_init(N)
	M = int(input())
	ms = tuple((tuple(map(int, input().split())) for i in range(M)))
	ways = []
	for (u, v) in ms:
		u -= 1
		v -= 1
		q = deque([(u, [])])
		visited = [False] * N
		while q:
			x = q.pop()
			(e, way) = x
			if visited[e]:
				continue
			if e == v:
				ways.append(set(way))
			visited[e] = True
			for (ne, j) in edge[e]:
				nw = copy(way)
				nw.append(j)
				q.append((ne, nw))
	tot = pow(2, N - 1)
	for i in range(1, M + 1):
		for ws in combinations(ways, i):
			ts = set()
			for w in ws:
				ts |= w
			tot += (-1) ** i * pow(2, N - 1 - len(ts))
	print(tot)
main()


N = int(input())
AB = [list(map(int, input().split())) for _ in [0] * (N - 1)]
M = int(input())
UV = [list(map(int, input().split())) for _ in [0] * M]
E = [[] for _ in [0] * N]
for (a, b) in AB:
	a -= 1
	b -= 1
	E[a].append(b)
	E[b].append(a)
P = [-1] * N
P[0] = 0
q = [0]
while q:
	i = q.pop()
	for j in E[i]:
		if P[j] != -1:
			continue
		P[j] = i
		q.append(j)
P[0] = -1

def dist_bfs(N, E, start):
	d = [-1] * N
	d[start] = 0
	q = [start]
	while q:
		qq = []
		for i in q:
			di = d[i]
			for j in E[i]:
				if d[j] != -1:
					continue
				d[j] = di + 1
				q.append(j)
		q = qq
	return d
path = []
for (u, v) in UV:
	u -= 1
	v -= 1
	tmp = []
	d = dist_bfs(N, E, u)
	q = [v]
	while q:
		i = q.pop()
		di = d[i]
		for j in E[i]:
			if d[j] == di - 1:
				q.append(j)
				if P[i] == j:
					tmp.append(i)
				else:
					tmp.append(j)
	path.append(set(tmp))
ans = 2 ** (N - 1)
for i in range(1, 2 ** M):
	tmp = set(range(1, N))
	cnt = 0
	for j in range(M):
		if i >> j & 1 == 0:
			continue
		cnt += 1
		tmp -= path[j]
	ans += (-1) ** cnt * 2 ** len(tmp)
print(ans)


import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline
n = int(input())
edge = [[] for _ in range(n)]
edge_dict = dict()
edges = []
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
		edges.append((b, a))
	else:
		edge_dict[a, b] = i
		edges.append((a, b))
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
state = [set() for _ in range(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:
			state[i].add(edge_dict[uu, vv])
dp = [[0] * 2 ** m for _ in range(n - 1)]
dp[0][0] = 1
(a, b) = edges[0]
status = 0
for (i, st) in enumerate(state):
	if 0 in st:
		status |= 1 << i
dp[0][status] += 1
for (i, (a, b)) in enumerate(edges):
	if i == 0:
		continue
	status = 0
	for (j, st) in enumerate(state):
		if i in st:
			status |= 1 << j
	for k in range(2 ** m):
		dp[i][k | status] += dp[i - 1][k]
		dp[i][k] += dp[i - 1][k]
print(dp[-1][-1])


from collections import deque
N = int(input())
G = [[] for i in range(N)]
a = [0 for i in range(N - 1)]
b = [0 for i in range(N - 1)]
edges = dict()
for i in range(N - 1):
	(a[i], b[i]) = map(int, input().split())
	a[i] -= 1
	b[i] -= 1
	G[a[i]].append(b[i])
	G[b[i]].append(a[i])
	edges[min(a[i], b[i]), max(a[i], b[i])] = i
M = int(input())
u = [0 for i in range(M)]
v = [0 for i in range(M)]
for i in range(M):
	(u[i], v[i]) = map(int, input().split())
	u[i] -= 1
	v[i] -= 1
root = [0 for i in range(M)]
for i in range(M):
	q = deque([u[i]])
	parents = [-1 for i in range(N)]
	reached = [0 for i in range(N)]
	while len(q) > 0:
		r = q.popleft()
		reached[r] = 1
		for p in G[r]:
			if reached[p] == 1:
				continue
			parents[p] = r
			q.append(p)
	x = v[i]
	while 1:
		if parents[x] == -1:
			break
		s = min(x, parents[x])
		t = max(x, parents[x])
		root[i] += 2 ** edges[s, t]
		x = parents[x]
ans = 0

def cnt(x):
	ans = 0
	for i in range(M):
		if x | 2 ** i == x:
			ans += 1
	return ans
q = deque([])
q.append(0)
S = [0 for i in range(2 ** M)]
reached = [0 for i in range(2 ** M)]
while len(q) > 0:
	i = q.popleft()
	for j in range(M):
		if i & 2 ** j == 0:
			S[i | 2 ** j] = S[i] | root[j]
			if reached[i | 2 ** j] == 0:
				q.append(i | 2 ** j)
				reached[i | 2 ** j] = 1
	ans += (-1) ** cnt(i) * 2 ** (N - bin(S[i]).count('1') - 1)
print(ans)


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)


import sys
sys.setrecursionlimit(10 ** 7)

def dfs(G, p, pre, t, edge, x):
	for nxt in G[p]:
		if nxt == pre:
			continue
		(a, b) = (p, nxt)
		if b < a:
			(a, b) = (b, a)
		if nxt == t:
			edge[a, b] += x
			return True
		if dfs(G, nxt, p, t, edge, x):
			edge[a, b] += x
			return True
	return False

def main():
	n = int(input())
	G = [[] for _ in range(n)]
	edge = {}
	for _ in range(n - 1):
		(a, b) = map(int, input().split())
		(a, b) = (a - 1, b - 1)
		G[a].append(b)
		G[b].append(a)
		if b < a:
			(a, b) = (b, a)
		edge[a, b] = 0
	m = int(input())
	for i in range(m):
		(u, v) = map(int, input().split())
		(u, v) = (u - 1, v - 1)
		x = 1 << i
		dfs(G, u, -1, v, edge, x)
	ans = 2 ** (n - 1)
	for i in range(1, 2 ** m):
		bit_cnt = 0
		for j in range(m):
			if i & 1 << j != 0:
				bit_cnt += 1
		cnt = 0
		for v in edge.values():
			if v & i != 0:
				cnt += 1
		x = 2 ** (n - 1 - cnt)
		if bit_cnt % 2 == 0:
			ans += x
		else:
			ans -= x
	print(ans)
main()


from collections import deque

def dfs(start, goal, tree):
	q = deque([start])
	visited = {}
	visited[start] = -1
	while True:
		pos = q.pop()
		if pos == goal:
			break
		for child in tree[pos]:
			if child in visited:
				continue
			visited[child] = pos
			q.append(child)
	res = []
	pos = goal
	while True:
		par = visited[pos]
		if par == -1:
			break
		res.append((min(par, pos), max(par, pos)))
		pos = par
	return res
n = int(input())
info = [list(map(int, input().split())) for i in range(n - 1)]
m = int(input())
path = [list(map(int, input().split())) for i in range(m)]
tree = [[] for i in range(n)]
memo = {}
for i in range(n - 1):
	(a, b) = info[i]
	a -= 1
	b -= 1
	tree[a].append(b)
	tree[b].append(a)
	memo[min(a, b), max(a, b)] = i
li_path = [0] * m
for i in range(m):
	(s, g) = path[i]
	s -= 1
	g -= 1
	res = dfs(s, g, tree)
	tmp = 0
	for j in res:
		tmp += 1 << memo[j]
	li_path[i] = tmp
ans = 0
for bit_state in range(1 << m):
	mask = 0
	cnt = 0
	for i in range(m):
		if bit_state & 1 << i:
			cnt += 1
			mask |= li_path[i]
	num_n = bin(mask).count('1')
	if cnt % 2 == 0:
		ans += 2 ** (n - 1 - num_n)
	else:
		ans -= 2 ** (n - 1 - num_n)
print(ans)


N = int(input())
E = [tuple(sorted(map(int, input().split()))) for i in range(N - 1)]
DICT = {x: ind for (ind, x) in enumerate(E)}
EDGE = [[] for i in range(N + 1)]
for (x, y) in E:
	EDGE[x].append(y)
	EDGE[y].append(x)
M = int(input())
Q = [tuple(map(int, input().split())) for i in range(M)]

def dfs(x, y):
	USE = [-1] * (N + 1)
	USE[x] = 0
	NOW = [x]
	while NOW:
		n = NOW.pop()
		for to in EDGE[n]:
			if USE[to] == -1:
				USE[to] = n
				NOW.append(to)
	ANS = [y]
	while y != x:
		y = USE[y]
		ANS.append(y)
	RET = []
	for i in range(1, len(ANS)):
		RET.append(DICT[tuple(sorted([ANS[i - 1], ANS[i]]))])
	return set(RET)
Q2 = [dfs(x, y) for (x, y) in Q]
DP = [0] * (1 << M)
DP[0] = 1
for i in range(N - 1):
	B = 0
	for k in range(M):
		if i in Q2[k]:
			B += 1 << k
	for j in range((1 << M) - 1, -1, -1):
		DP[j | B] += DP[j]
print(DP[-1])


import sys
sys.setrecursionlimit(10 ** 7)

def main(n, ki, uv):
	S = []
	F = [0] * n
	depth = [0] * n

	def dfs(v, pare, d):
		F[v] = len(S)
		depth[v] = d
		S.append(v)
		for (i, w) in ki[v]:
			if w == pare:
				continue
			dfs(w, v, d + 1)
			S.append(v)
	dfs(0, -1, 0)
	INF = (n, None)
	M = 2 * n
	M0 = 2 ** (M - 1).bit_length()
	data = [INF] * (2 * M0)
	for (i, v) in enumerate(S):
		data[M0 - 1 + i] = (depth[v], i)
	for i in range(M0 - 2, -1, -1):
		data[i] = min(data[2 * i + 1], data[2 * i + 2])

	def _query(a, b):
		yield INF
		a += M0
		b += M0
		while a < b:
			if b & 1:
				b -= 1
				yield data[b - 1]
			if a & 1:
				yield data[a - 1]
				a += 1
			a >>= 1
			b >>= 1

	def query(u, v):
		fu = F[u]
		fv = F[v]
		if fu > fv:
			(fu, fv) = (fv, fu)
		return S[min(_query(fu, fv + 1))[1]]
	todo = [[0, []]]
	path = [[]] * n
	mi = [1] * n
	while todo:
		(v, ary) = todo.pop()
		path[v] = ary
		mi[v] = 0
		for (i, nv) in ki[v]:
			if mi[nv] == 1:
				todo.append([nv, ary + [i]])
				mi[nv] = 1
	for i in range(n):
		path[i] = set(path[i])
	memo = {}
	ans = 0
	for i in range(2 ** m):
		chk = set(())
		for j in range(m):
			if i >> j & 1:
				chk.add(j)
		must_w = set(())
		for c in chk:
			if c in memo:
				tmp = memo[c]
			else:
				(u, v) = uv[c]
				dd = query(u, v)
				tmp = path[u].union(path[v])
				tmp = tmp - path[dd]
				memo[c] = tmp
			must_w = must_w.union(tmp)
		t = n - 1 - len(must_w)
		if len(chk) % 2 == 1:
			ans -= pow(2, t)
		else:
			ans += pow(2, t)
	print(ans)
n = int(input())
ki = [[] for _ in range(n)]
for i in range(n - 1):
	(u, v) = map(int, input().split())
	(u, v) = (u - 1, v - 1)
	ki[u].append([i, v])
	ki[v].append([i, u])
m = int(input())
uv = []
for _ in range(m):
	(u, v) = map(int, input().split())
	(u, v) = (u - 1, v - 1)
	uv.append([u, v])
main(n, ki, uv)


from collections import *

def popcnt(n):
	c = (n & 6148914691236517205) + (n >> 1 & 6148914691236517205)
	c = (c & 3689348814741910323) + (c >> 2 & 3689348814741910323)
	c = (c & 1085102592571150095) + (c >> 4 & 1085102592571150095)
	c = (c & 71777214294589695) + (c >> 8 & 71777214294589695)
	c = (c & 281470681808895) + (c >> 16 & 281470681808895)
	c = (c & 4294967295) + (c >> 32 & 4294967295)
	return c
N = int(input())
edges = [[] for i in range(N)]
edge_id = defaultdict(lambda : -1)
for i in range(N - 1):
	(a, b) = map(lambda x: int(x) - 1, input().split())
	edges[a].append(b)
	edges[b].append(a)
	edge_id[a, b] = edge_id[b, a] = i
path = defaultdict(lambda : -1)

def set_path(r, v, path_):
	visited[v] = 1
	path[r, v] = path_
	for u in edges[v]:
		if visited[u] == 0:
			set_path(r, u, path_ | 1 << edge_id[v, u])
for i in range(N):
	visited = [0] * N
	set_path(i, i, 0)
M = int(input())
uv = [list(map(lambda x: int(x) - 1, input().split())) for i in range(M)]
ans = pow(2, N - 1)
for i in range(1, 1 << M):
	all_path = 0
	for (j, (u, v)) in enumerate(uv):
		if i & 1 << j:
			all_path |= path[u, v]
	if popcnt(i) & 1:
		ans -= pow(2, N - 1 - popcnt(all_path))
	else:
		ans += pow(2, N - 1 - popcnt(all_path))
print(ans)


N = int(input())
es = []
adj = [[] for _ in range(N)]
e_index = dict()
for i in range(N - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	es.append((a, b))
	es.append((b, a))
	adj[a].append(b)
	adj[b].append(a)
	e_index[a, b] = i
	e_index[b, a] = i
M = int(input())
uvs = [tuple(map(int, input().split())) for _ in range(M)]
edges = [0] * (N - 1)
for (i, (u, v)) in enumerate(uvs):
	u -= 1
	v -= 1
	parent = [-1] * N
	stack = [u]
	while stack:
		node = stack.pop()
		if node == v:
			break
		for next_node in adj[node]:
			if parent[node] != next_node:
				parent[next_node] = node
				stack.append(next_node)
	node = v
	while node != u:
		next_node = parent[node]
		index = e_index[node, next_node]
		edges[index] |= 1 << i
		node = next_node
dp = [0] * (1 << M)
dp[0] = 1
for e in edges:
	for i in range((1 << M) - 1, -1, -1):
		dp[i | e] += dp[i]
print(dp[-1])


from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 13

def LI():
	return list(map(int, sys.stdin.buffer.readline().split()))

def I():
	return int(sys.stdin.buffer.readline())

def LS():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

def S():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8')

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]

def SRL(n):
	return [list(S()) for i in range(n)]

def MSRL(n):
	return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007
import sys
readline = sys.stdin.readline
n = I()
G = [[] for _ in range(n)]
for i in range(n - 1):
	(u, v) = LI()
	G[u - 1] += [(i, v - 1)]
	G[v - 1] += [(i, u - 1)]

def dfs(root):
	q = [root]
	path_bit = [-1] * n
	path_bit[root] = 0
	while q:
		u = q.pop()
		for (i, v) in G[u]:
			if path_bit[v] != -1:
				continue
			path_bit[v] = path_bit[u] | 1 << i
			q += [v]
	return path_bit

def popcnt(n):
	c = (n & 6148914691236517205) + (n >> 1 & 6148914691236517205)
	c = (c & 3689348814741910323) + (c >> 2 & 3689348814741910323)
	c = (c & 1085102592571150095) + (c >> 4 & 1085102592571150095)
	c = (c & 71777214294589695) + (c >> 8 & 71777214294589695)
	c = (c & 281470681808895) + (c >> 16 & 281470681808895)
	c = (c & 4294967295) + (c >> 32 & 4294967295)
	return c
m = I()
cond = LIR(m)
path_bit = dfs(0)
cond_bit = [0] * m
for (j, (u, v)) in enumerate(cond):
	cond_bit[j] = path_bit[u - 1] ^ path_bit[v - 1]
L = [0] * 2 ** m
C = [0] * n
for i in range(2 ** m):
	if i != 0:
		L[i] = L[i ^ i & -i] | cond_bit[(i & -i).bit_length() - 1]
	cond_cnt = popcnt(i)
	if cond_cnt % 2:
		C[n - 1 - popcnt(L[i])] -= 1
	else:
		C[n - 1 - popcnt(L[i])] += 1
ans = 0
for i in range(n):
	ans += 2 ** i * C[i]
print(ans)


def DFS(graph, root, parent):
	dist = [-1] * (n + 1)
	dist[root] = 0
	stack = [root]
	while stack:
		x = stack.pop()
		for y in graph[x]:
			if dist[y] == -1:
				parent[y] = x
				dist[y] = dist[x] + 1
				stack.append(y)
	return dist

class Doubling:

	def __init__(self, graph, root):
		self.root = root
		n = len(graph) - 1
		self.ancestor_ls = [[0] * (n + 1)]
		self.distance = DFS(graph, root, self.ancestor_ls[0])
		self.bitn = n.bit_length()
		for i in range(1, self.bitn + 1):
			ancestor_ls_app = [0] * (n + 1)
			for j in range(1, n + 1):
				ancestor_ls_app[j] = self.ancestor_ls[i - 1][self.ancestor_ls[i - 1][j]]
			self.ancestor_ls.append(ancestor_ls_app)

	def dist(self):
		return self.distance

	def parent(self):
		return self.ancestor_ls[0]

	def ancestor(self, v, depth):
		if depth == 0:
			return v
		if n < depth:
			return self.root
		ret = v
		for i in range(self.bitn):
			if depth & 1 << i:
				ret = self.ancestor_ls[i][ret]
		return ret

	def LCA(self, u, v):
		if self.distance[u] < self.distance[v]:
			(u, v) = (v, u)
		dif = self.distance[u] - self.distance[v]
		w = self.ancestor(u, dif)
		if w == v:
			return v
		for i in range(self.bitn, -1, -1):
			if self.ancestor_ls[i][w] != self.ancestor_ls[i][v]:
				(w, v) = (self.ancestor_ls[i][w], self.ancestor_ls[i][v])
		return self.ancestor_ls[0][v]
import sys
input = sys.stdin.readline
n = int(input())
ab = [list(map(int, input().split())) for i in range(n - 1)]
graph = [[] for i in range(n + 1)]
for (a, b) in ab:
	graph[a].append(b)
	graph[b].append(a)
sol = Doubling(graph, 1)
pls = sol.parent()
m = int(input())
cons = [0 for i in range(m)]
for i in range(m):
	(u, v) = map(int, input().split())
	lca = sol.LCA(u, v)
	while u != lca:
		cons[i] |= 1 << u
		u = pls[u]
	while v != lca:
		cons[i] |= 1 << v
		v = pls[v]
ans = 0
for i in range(2 ** m):
	x = 0
	for j in range(m):
		if i & 1 << j:
			x |= cons[j]
	bcnt = 0
	for j in range(n + 1):
		if x & 1 << j:
			bcnt += 1
	if bin(i).count('1') % 2 == 1:
		ans -= 2 ** (n - 1 - bcnt)
	else:
		ans += 2 ** (n - 1 - bcnt)
print(ans)


import sys
stdin = sys.stdin
ni = lambda : int(ns())
na = lambda : list(map(int, stdin.readline().split()))
ns = lambda : stdin.readline().rstrip()
n = ni()
g = [[] for _ in range(n)]
for i in range(n - 1):
	(a, b) = na()
	g[a - 1].append(b - 1)
	g[b - 1].append(a - 1)

def dfs(cur, pre, g, par, od):
	par[cur] = pre
	od.append(cur)
	for e in g[cur]:
		if e == pre:
			continue
		dfs(e, cur, g, par, od)
par = [-1] * n
od = []
dfs(0, -1, g, par, od)

def lca(a, b, par):
	ps = set()
	q = a
	while q != -1:
		ps.add(q)
		q = par[q]
	while b != -1:
		if b in ps:
			return b
		b = par[b]
	raise
m = ni()
cons = [0] * n
for i in range(m):
	(u, v) = na()
	u -= 1
	v -= 1
	lc = lca(u, v, par)
	while u != lc:
		cons[u] |= 1 << i
		u = par[u]
	while v != lc:
		cons[v] |= 1 << i
		v = par[v]

def st(b, m):
	for i in range(m):
		for j in range(1 << m):
			if j >> i & 1 == 0:
				b[j | 1 << i] += b[j]
	return b

def ist(b, m):
	for i in range(m):
		for j in range(1 << m):
			if j >> i & 1 == 0:
				b[j | 1 << i] -= b[j]
	return b
dp = [1] * (1 << m)
for cur in range(1, n):
	for i in range(1 << m):
		if i & cons[cur] == cons[cur]:
			dp[i] *= 2
dp = ist(dp, m)
print(dp[(1 << m) - 1])


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:
			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()


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)

def solve():
	N = int(input())
	adjL = [[] for _ in range(N)]
	edges = []
	for _ in range(N - 1):
		(a, b) = map(int, input().split())
		(a, b) = (a - 1, b - 1)
		adjL[a].append(b)
		adjL[b].append(a)
		edges.append((a, b))
	M = int(input())
	uvs = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(M)]
	e2Roots = [set() for _ in range(N)]

	def dfs(vNow, vPar):
		for v2 in adjL[vNow]:
			if v2 == vPar:
				continue
			e2Roots[v2] |= e2Roots[vNow]
			e2Roots[v2].add((vNow, v2))
			dfs(v2, vNow)
	dfs(0, -1)
	ePaths = [set() for _ in range(M)]
	for (i, (u, v)) in enumerate(uvs):
		ePaths[i] = e2Roots[u] ^ e2Roots[v]
	numEs = [0] * (1 << M)
	for (a, b) in edges:
		ptn = 0
		for (iC, ePath) in enumerate(ePaths):
			if (a, b) in ePath or (b, a) in ePath:
				ptn |= 1 << iC
		for S in range(1 << M):
			if S & ptn:
				numEs[S] += 1

	def getPows(base, n):
		pows = [1] * (n + 1)
		for x in range(1, n + 1):
			pows[x] = pows[x - 1] * base
		return pows
	pows = getPows(2, N)

	def getNum1s(N):
		num1s = [0]
		for _ in range(N):
			num12s = [num1 + 1 for num1 in num1s]
			num1s += num12s
		return num1s
	num1s = getNum1s(M)
	ans = pows[N - 1]
	for S in range(1, 1 << M):
		num = pows[N - 1 - numEs[S]]
		if num1s[S] % 2:
			ans -= num
		else:
			ans += num
	print(ans)
solve()


def main():
	import sys

	def I():
		return int(sys.stdin.readline().rstrip())

	def MI():
		return map(int, sys.stdin.readline().rstrip().split())
	N = I()
	dist = [[100] * (N + 1) for _ in range(N + 1)]
	edges = {}
	for i in range(N - 1):
		(a, b) = MI()
		dist[a][b] = 1
		dist[b][a] = 1
		edges[a, b] = i
		edges[b, a] = i
	for i in range(1, N + 1):
		dist[i][i] = 0
	for k in range(1, N + 1):
		for i in range(1, N + 1):
			for j in range(1, N + 1):
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
	M = I()
	A = []
	for _ in range(M):
		(u, v) = MI()
		B = set()
		while True:
			if dist[u][v] == 1:
				B.add(edges[u, v])
				break
			else:
				for i in range(1, N + 1):
					if dist[u][i] == dist[u][v] - 1 and dist[i][v] == 1:
						B.add(edges[i, v])
						v = i
						break
		A.append(B)
	ans = 0
	for i in range(2 ** M):
		C = set()
		a = 0
		for j in range(M):
			if i >> j & 1:
				C |= A[j]
				a += 1
		l = len(C)
		a %= 2
		ans += (-1) ** a * 2 ** (N - 1 - l)
	print(ans)
main()


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque, defaultdict

def all_bit_count(n):
	c = (n & 6148914691236517205) + (n >> 1 & 6148914691236517205)
	c = (c & 3689348814741910323) + (c >> 2 & 3689348814741910323)
	c = (c & 1085102592571150095) + (c >> 4 & 1085102592571150095)
	c = (c & 71777214294589695) + (c >> 8 & 71777214294589695)
	c = (c & 281470681808895) + (c >> 16 & 281470681808895)
	c = (c & 4294967295) + (c >> 32 & 4294967295)
	return c
n = int(readline())
d = defaultdict(int)
cnt = 1
g = [[] * n for i in range(n)]
for i in range(n - 1):
	(u, v) = map(int, readline().split())
	u -= 1
	v -= 1
	g[u].append(v)
	g[v].append(u)
m = int(readline())
c = []
for i in range(m):
	(u, v) = map(int, readline().split())
	u -= 1
	v -= 1
	que = deque()
	que.append((u, 0))
	chk = [False] * n
	chk[u] = True
	while que:
		(now, L) = que.popleft()
		if now == v:
			c.append(L)
			break
		for i in g[now]:
			if not chk[i]:
				chk[i] = True
				mi = min(now, i)
				ma = max(now, i)
				mm = mi * 100 + ma
				if d[mm] == 0:
					d[mm] = cnt
					cnt += 1
				que.append((i, L | 1 << d[mm]))
import itertools
ans = 1 << n - 1
for i in range(1, m + 1):
	for j in itertools.combinations(c, i):
		K = 0
		for k in j:
			K |= k
		l = all_bit_count(K)
		ans += pow(-1, i) * pow(2, n - 1 - l)
print(ans)


def dfs(tree, v, tv, p, es):
	if v == tv:
		return True
	for e in tree[v]:
		if e[0] == p:
			continue
		if dfs(tree, e[0], tv, v, es):
			es.append(e[1])
			return True
	return False

def main():
	n = int(input())
	tree = [[] for i in range(n)]
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		a -= 1
		b -= 1
		tree[a].append((b, i))
		tree[b].append((a, i))
	m = int(input())
	eset = [0] * m
	for i in range(m):
		(u, v) = map(int, input().split())
		es = []
		dfs(tree, u - 1, v - 1, -1, es)
		for e in es:
			eset[i] |= 1 << e
	ans = 0
	for i in range(1 << m):
		mask = 0
		for j in range(m):
			if i >> j & 1:
				mask |= eset[j]
		white = bin(mask).count('1')
		now = 1 << n - 1 - white
		if bin(i).count('1') % 2 == 0:
			ans += now
		else:
			ans -= now
	print(ans)
main()


N = int(input())
ab = [list(map(int, input().split())) for i in range(N - 1)]
M = int(input())
uv = [list(map(int, input().split())) for i in range(M)]
data = [[] for i in range(N + 1)]
for (a, b) in ab:
	data[a].append(b)
	data[b].append(a)
node = [[-1] * (N + 1) for i in range(N - 1)]
for i in range(N - 1):
	(a, b) = ab[i]
	flag = [0] * (N + 1)
	flag[a] = 1
	flag[b] = 1
	node[i][a] = 0
	que = [a]
	while que:
		u = que.pop()
		for v in data[u]:
			if flag[v] == 0:
				flag[v] = 1
				node[i][v] = 0
				que.append(v)
	node[i][b] = 1
	que = [b]
	while que:
		u = que.pop()
		for v in data[u]:
			if flag[v] == 0:
				flag[v] = 1
				node[i][v] = 1
				que.append(v)
dp = [[0] * 2 ** M for i in range(N)]
dp[0][0] = 1
for i in range(N - 1):
	h = node[i]
	num = 0
	for j in range(M):
		(u, v) = uv[j]
		if h[u] == h[v]:
			continue
		else:
			num += 2 ** j
	dp[i + 1] = dp[i][:]
	for j in range(2 ** M):
		dp[i + 1][j | num] += dp[i][j]
print(dp[-1][-1])


n = int(input())
peer = [[] for _ in range(n)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	peer[a].append(b)
	peer[b].append(a)
edge = [0 for _ in range(n)]
seen = [0 for _ in range(n)]
seen[0] = 1
now = [0]
while now:
	last = now
	now = []
	for x in last:
		for y in peer[x]:
			if seen[y] == 0:
				edge[y] = edge[x] + 2 ** (y - 1)
				seen[y] = 1
				now.append(y)

def count1(x):
	y = bin(x)
	z = 0
	l = len(y)
	for li in range(l):
		if y[li] == '1':
			z += 1
	return z

def count2(x):
	z = 0
	l = len(x)
	for li in range(l):
		if x[li] == '1':
			z += 1
	return z
m = int(input())
restr = []
for _ in range(m):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	restr.append(edge[u] ^ edge[v])
ans = 0
for i in range(2 ** m):
	b = bin(i)[2:]
	time = '0' * (m - len(b)) + b
	tmp = 0
	for j in range(m):
		if time[j] == '1':
			tmp |= restr[j]
	if count2(time) % 2 == 0:
		ans += 2 ** (n - 1 - count1(tmp))
	else:
		ans -= 2 ** (n - 1 - count1(tmp))
print(ans)


N = int(input())
from collections import defaultdict
G = defaultdict(list)
EdaNum = {}
Ki = [[float('inf')] * (N + 1) for i in range(N + 1)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	G[a].append(b)
	G[b].append(a)
	EdaNum[min(a, b), max(a, b)] = i
	Ki[a][b] = 1
	Ki[b][a] = 1
Next = [[-1] * (N + 1) for i in range(N + 1)]
for i in range(1, N + 1):
	for j in range(1, N + 1):
		Next[i][j] = j
for k in range(1, N + 1):
	for i in range(1, N + 1):
		for j in range(1, N + 1):
			if Ki[i][k] + Ki[k][j] < Ki[i][j]:
				Ki[i][j] = Ki[i][k] + Ki[k][j]
				Next[i][j] = Next[i][k]
M = int(input())
MM = [set() for i in range(M)]
for i in range(M):
	(u, v) = map(int, input().split())
	now = u
	while now != v:
		nex = Next[now][v]
		MM[i].add(EdaNum[min(now, nex), max(now, nex)])
		now = nex
import itertools
zero1 = [0, 1]
ans = 0
for i in itertools.product(zero1, repeat=M):
	count = 0
	root = set()
	for j in range(M):
		if i[j] == 0:
			count += 1
		else:
			root |= MM[j]
	if (M - count) % 2 == 0:
		ans += pow(2, N - 1 - len(root))
	else:
		ans -= pow(2, N - 1 - len(root))
print(ans)


def popcount(x):
	x = x - (x >> 1 & 6148914691236517205)
	x = (x & 3689348814741910323) + (x >> 2 & 3689348814741910323)
	x = x + (x >> 4) & 1085102592571150095
	x = x + (x >> 8)
	x = x + (x >> 16)
	x = x + (x >> 32)
	return x & 127

def main():
	import collections
	N = int(input())
	G = [[-1] * N for i in range(N)]
	ans = 2 ** (N - 1)
	for i in range(N - 1):
		(a, b) = map(int, input().split())
		a -= 1
		b -= 1
		G[a][b] = i
		G[b][a] = i
	ans = 0
	g = [[0] * N for i in range(N)]
	for i in range(N):
		q = collections.deque()
		q.append((i, 0))
		r = [True] * N
		r[i] = False
		while q:
			(x, s) = q.popleft()
			for y in range(N):
				if G[x][y] >= 0 and r[y]:
					g[i][y] = s | 1 << G[x][y]
					q.append((y, g[i][y]))
					r[y] = False
	M = int(input())
	s = [0 for i in range(M)]
	for i in range(M):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		s[i] = g[u][v]
	for i in range(2 ** M):
		tmp = 2 ** (N - 1) - 1
		c = 0
		for j in range(M):
			if (i >> j) % 2 == 1:
				tmp &= ~s[j]
				c += 1
		ans += (-1) ** c * (1 << popcount(tmp))
	print(ans)
main()


from copy import copy
n = int(input())
G = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	G[a].append(b)
	G[b].append(a)
edge_set = [set() for i in range(n)]
edge_id = 0

def dfs(p, v, se):
	global edge_id
	edge_set[v] = se
	for to in G[v]:
		if to != p:
			nset = copy(se)
			nset.add(edge_id)
			edge_id += 1
			dfs(v, to, nset)
dfs(-1, 0, set())
m = int(input())
edge_set2 = []
for i in range(m):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	edge_set2.append(edge_set[a] ^ edge_set[b])
from itertools import combinations
ans = 0
for i in range(m):
	op = -1 if i % 2 else 1
	for c in combinations(range(m), i + 1):
		s = set()
		for j in c:
			s |= edge_set2[j]
		rem = n - 1 - len(s)
		ans += op * (1 << rem)
ans = 2 ** (n - 1) - ans
print(ans)


from collections import deque

def solve(n, edge_list, m, cond_list):
	g = [[] for _ in range(n)]
	for (a, b) in edge_list:
		g[a - 1].append(b - 1)
		g[b - 1].append(a - 1)
	cond_mat = [[0] * m for _ in range(n - 1)]
	for i in range(m):
		(u, v) = cond_list[i]
		parent_list = [-1] * n
		p = u - 1
		parent_list[p] = p
		queue = deque([p])
		while len(queue) > 0:
			p = queue.popleft()
			for q in g[p]:
				if parent_list[q] == -1:
					parent_list[q] = p
					queue.append(q)
		q = v - 1
		p = parent_list[q]
		while q != u - 1:
			if (p + 1, q + 1) in edge_list:
				k = edge_list.index((p + 1, q + 1))
			else:
				k = edge_list.index((q + 1, p + 1))
			cond_mat[k][i] = 1
			(p, q) = (parent_list[p], parent_list[q])
	cond_vec = [0] * (n - 1)
	for k in range(n - 1):
		for i in range(m):
			cond_vec[k] += cond_mat[k][i] * 2 ** i
	dp = [[0] * 2 ** m for _ in range(n)]
	dp[0][0] = 1
	for k in range(n - 1):
		for i in range(2 ** m):
			dp[k + 1][i] += dp[k][i]
			dp[k + 1][i | cond_vec[k]] += dp[k][i]
	return dp[-1][-1]

def main():
	n = int(input())
	edge_list = []
	for _ in range(n - 1):
		(a, b) = map(int, input().split())
		edge_list.append((a, b))
	m = int(input())
	cond_list = []
	for _ in range(m):
		(u, v) = map(int, input().split())
		cond_list.append((u, v))
	res = solve(n, edge_list, m, cond_list)
	print(res)

def test():
	assert solve(3, [(1, 2), (2, 3)], 1, [(1, 3)]) == 3
	assert solve(2, [(1, 2)], 1, [(1, 2)]) == 1
	assert solve(5, [(1, 2), (3, 2), (3, 4), (5, 3)], 3, [(1, 3), (2, 4), (2, 5)]) == 9
test()
main()


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)


import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
N = int(input())
edge = [[] for _ in range(N + 1)]
for _ in range(N - 1):
	(x, y) = map(int, input().split())
	edge[x].append(y)
	edge[y].append(x)
M = int(input())
AB = tuple((tuple(map(int, input().split())) for _ in range(M)))
parent = [-1] * (N + 1)
node = [1]
while node:
	s = node.pop()
	for t in edge[s]:
		if t == parent[s]:
			continue
		parent[t] = s
		node.append(t)
pair = [-1] * M
for (i, (a, b)) in enumerate(AB):
	pa = set()
	pb = set()
	while a != 1:
		pa.add(a - 1)
		a = parent[a]
	while b != 1:
		pb.add(b - 1)
		b = parent[b]
	pair[i] = pa ^ pb
ans = pow(2, N - 1)
whole = set(range(1, N))
for bit in range(1, 1 << M):
	popcnt = 0
	inter = set()
	for i in range(M):
		if bit >> i & 1:
			popcnt += 1
			inter |= pair[i]
	x = N - len(inter) - 1
	if popcnt % 2 == 1:
		ans -= 2 ** x
	else:
		ans += 2 ** x
print(ans)


import sys
readline = sys.stdin.readline
popcntsum = (1 << 64) - 1
Fa = [0] + [popcntsum // ((1 << (1 << i - 1)) + 1) for i in range(1, 7)]
Fb = [0] + [Fa[i] << (1 << i - 1) for i in range(1, 7)]
fila1 = Fa[1]
filb1 = Fb[1]
fila2 = Fa[2]
filb2 = Fb[2]
fila3 = Fa[3]
filb3 = Fb[3]
fila4 = Fa[4]
filb4 = Fb[4]
fila5 = Fa[5]
filb5 = Fb[5]
fila6 = Fa[6]
filb6 = Fb[6]

def popcount(x):
	x = (x & fila1) + ((x & filb1) >> 1)
	x = (x & fila2) + ((x & filb2) >> 2)
	x = (x & fila3) + ((x & filb3) >> 4)
	x = (x & fila4) + ((x & filb4) >> 8)
	x = (x & fila5) + ((x & filb5) >> 16)
	x = (x & fila6) + ((x & filb6) >> 32)
	return x

def parorder(Edge, p):
	N = len(Edge)
	par = [0] * N
	par[p] = -1
	stack = [p]
	order = []
	Enum = [None] * N
	visited = set([p])
	ast = stack.append
	apo = order.append
	while stack:
		vn = stack.pop()
		apo(vn)
		for (vf, num) in Edge[vn]:
			if vf in visited:
				continue
			visited.add(vf)
			par[vf] = vn
			Enum[vf] = num
			ast(vf)
	return (par, order, Enum)

def getcld(p):
	res = [[] for _ in range(len(p))]
	for (i, v) in enumerate(p[1:], 1):
		res[v].append(i)
	return res
N = int(readline())
Edge = [[] for _ in range(N)]
for i in range(N - 1):
	(a, b) = map(int, readline().split())
	a -= 1
	b -= 1
	Edge[a].append((b, i))
	Edge[b].append((a, i))
root = 0
(P, L, Enum) = parorder(Edge, root)
M = int(readline())
Q = [tuple(map(int, readline().split())) for _ in range(M)]
dp = [0] * (1 << M)
ans = pow(2, N - 1)
for S in range(1, 1 << M):
	pc = popcount(S)
	if pc == 1:
		i = (-S & S).bit_length() - 1
		table = [False] * (N - 1)
		(u, v) = Q[i]
		u -= 1
		v -= 1
		while u != root:
			table[Enum[u]] = not table[Enum[u]]
			u = P[u]
		while v != root:
			table[Enum[v]] = not table[Enum[v]]
			v = P[v]
		res = 0
		for t in table:
			res <<= 1
			res |= t
		dp[S] = res
	else:
		dp[S] = dp[S ^ -S & S] | dp[-S & S]
	ans += (-1) ** (pc % 2) * pow(2, N - 1 - popcount(dp[S]))
print(ans)


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10 ** 9))
write = lambda x: sys.stdout.write(x + '\n')
from collections import defaultdict
n = int(input())
ns = defaultdict(set)
uv2e = {}
for i in range(n - 1):
	(u, v) = map(int, input().split())
	ns[u - 1].add(v - 1)
	ns[v - 1].add(u - 1)
	uv2e[u - 1, v - 1] = i
	uv2e[v - 1, u - 1] = i
m = int(input())
uvs = [None] * m
for i in range(m):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	uvs[i] = (u, v)
from queue import deque

def bfs(start):
	q = deque([start])
	seen = [None] * n
	seen[start] = 0
	while q:
		u = q.pop()
		d = seen[u]
		for v in ns[u]:
			if seen[v] is None:
				seen[v] = u
				q.appendleft(v)
	return seen
paths = [None] * m
for (i, (u, v)) in enumerate(uvs):
	seen = bfs(u)
	ss = set()
	z = v
	while z != u:
		z1 = seen[z]
		ss.add(uv2e[z, z1])
		z = z1
	paths[i] = ss
ans = 0

def dfs(l, s):
	if len(l) == m:
		global ans
		val = pow(2, n - 1 - len(s)) * pow(-1, sum(l))
		ans += val
		return
	dfs(l + [0], s)
	i = len(l)
	p = paths[i]
	dfs(l + [1], s | p)
dfs([], set())
print(ans)


from collections import defaultdict
from heapq import heappop, heappush

class Graph(object):

	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, From, To, cost=1):
		self.graph[From].append((To, cost))

	def get_nodes(self):
		return self.graph.keys()

class Dijkstra(object):

	def __init__(self, graph, start):
		self.g = graph.graph
		self.dist = defaultdict(lambda : float('inf'))
		self.dist[start] = 0
		self.prev = defaultdict(lambda : None)
		self.Q = []
		heappush(self.Q, (self.dist[start], start))
		while self.Q:
			(dist_u, u) = heappop(self.Q)
			if self.dist[u] < dist_u:
				continue
			for (v, cost) in self.g[u]:
				alt = dist_u + cost
				if self.dist[v] > alt:
					self.dist[v] = alt
					self.prev[v] = u
					heappush(self.Q, (alt, v))

	def shortest_distance(self, goal):
		return self.dist[goal]

	def shortest_path(self, goal):
		path = []
		node = goal
		while node is not None:
			path.append(node)
			node = self.prev[node]
		return path[::-1]
N = int(input())
g = Graph()
d = {}
for i in range(N - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	d[min(a, b), max(a, b)] = i
	g.add_edge(a, b)
	g.add_edge(b, a)
M = int(input())
l = [0] * M
for i in range(M):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	dij = Dijkstra(g, u)
	path = dij.shortest_path(v)
	for j in range(len(path) - 1):
		(a, b) = (path[j], path[j + 1])
		l[i] += 2 ** d[min(a, b), max(a, b)]
c = [0] * (M + 1)
p2 = [2 ** i for i in range(50)]
for n in range(2 ** M):
	cnt = 0
	x = 0
	for i in range(M):
		if n & p2[i] == p2[i]:
			cnt += 1
			x |= l[i]
	y = 0
	for i in range(N - 1):
		if x & p2[i] == p2[i]:
			y += 1
	c[cnt] += p2[N - 1 - y]
ans = 0
for i in range(M + 1):
	if i % 2 == 0:
		ans += c[i]
	else:
		ans -= c[i]
print(ans)


n = int(input())
adj = {a: [] for a in range(1, n + 1)}
for i in range(n - 1):
	(a, b) = map(int, input().split())
	adj[a].append(b)
	adj[b].append(a)
m = int(input())
ranges = []
for i in range(m):
	(u, v) = map(int, input().split())
	ranges.append((u, v))

def normalized(u, v):
	return (min(u, v), max(u, v))

def findpath(u, v, visited=None):
	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):
	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)
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
	c = 2 ** (n - 1 - len(b))
	sign = -1 if l % 2 == 0 else 1
	coloring += sign * c
coloring = 2 ** (n - 1) - coloring
print(coloring)


import sys

def main():
	input = sys.stdin.readline
	N = int(input())
	E = [[] for _ in range(N)]
	for i in range(N - 1):
		(a, b) = map(int, input().split())
		(a, b) = (a - 1, b - 1)
		E[a].append((b, i))
		E[b].append((a, i))

	def dfs(s, g):
		par = [(-1, -1)] * N
		par[s] = (s, -1)
		stack = [s]
		while stack:
			v = stack.pop()
			for (to, i) in E[v]:
				if par[to][0] >= 0:
					continue
				par[to] = (v, i)
				if to == g:
					break
				stack.append(to)
		r = 0
		v = g
		while v != s:
			(v, i) = par[v]
			r |= 1 << i
		return r
	M = int(input())
	path = [0] * M
	for i in range(M):
		(u, v) = map(int, input().split())
		(u, v) = (u - 1, v - 1)
		path[i] = dfs(u, v)

	def calc(s):
		return 1 << N - 1 - popcount(s)
	i_ans = 0
	for p in range(1, 1 << M):
		is_odd = 0
		s = 0
		for i in range(M):
			if p & 1:
				s |= path[i]
				is_odd ^= 1
			p >>= 1
		if is_odd:
			i_ans += calc(s)
		else:
			i_ans -= calc(s)
	print((1 << N - 1) - i_ans)

def popcount(x):
	x = (x & 6148914691236517205) + (x >> 1 & 6148914691236517205)
	x = (x & 3689348814741910323) + (x >> 2 & 3689348814741910323)
	x = x + (x >> 4) & 1085102592571150095
	x += x >> 8
	x += x >> 16
	x += x >> 32
	return x & 127
main()


from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10 ** 5)
input = sys.stdin.readline
sqrt = math.sqrt

def LI():
	return list(map(int, input().split()))

def LF():
	return list(map(float, input().split()))

def LI_():
	return list(map(lambda x: int(x) - 1, input().split()))

def II():
	return int(input())

def IF():
	return float(input())

def LS():
	return list(map(list, input().split()))

def S():
	return list(input().rstrip())

def IR(n):
	return [II() for _ in range(n)]

def LIR(n):
	return [LI() for _ in range(n)]

def FR(n):
	return [IF() for _ in range(n)]

def LFR(n):
	return [LI() for _ in range(n)]

def LIR_(n):
	return [LI_() for _ in range(n)]

def SR(n):
	return [S() for _ in range(n)]

def LSR(n):
	return [LS() for _ in range(n)]
mod = 1000000007
inf = 10000000000.0

def solve():

	def dfs(p, g, pre=-1):
		for e in edg[p]:
			if e == pre:
				continue
			if e == g:
				return [d[p, e]]
			tmp = dfs(e, g, p)
			if tmp:
				return tmp + [d[p, e]]
		return False
	n = II()
	edg = [[] for i in range(n)]
	t = 0
	ab = defaultdict(int)
	d = defaultdict(int)
	for _ in range(n - 1):
		(a, b) = LI_()
		edg[a].append(b)
		edg[b].append(a)
		d[a, b] = t
		d[b, a] = t
		t += 1
	m = II()
	path = [0] * m
	uv = LIR_(m)
	for (i, uvi) in enumerate(uv):
		(u, v) = uvi
		pat = dfs(u, v)
		for p in pat:
			path[i] |= 1 << p
	ans = 1 << n - 1
	for mask in range(1, 1 << m):
		tmp = 0
		t = 0
		for i in range(m):
			if mask & 1 << i:
				t += 1
				tmp = tmp | path[i]
		x = 0
		while tmp:
			x += tmp & 1
			tmp >>= 1
		ans += (1 << n - x - 1) * (-1) ** t
	print(ans)
	return
solve()


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)]

class Tree:
	(C, RL) = ({}, {})
	(R, N, D, S, P) = (None, None, None, None, None)

	def __init__(s, num):
		s.N = num

	def set(s, a, b):
		if a in s.C:
			s.C[a].append(b)
		else:
			s.C[a] = [b]
		if b in s.C:
			s.C[b].append(a)
		else:
			s.C[b] = [a]

	def dfs(s, x, y, r):
		if x == y:
			return [x]
		for i in s.C[x]:
			if i != r:
				t = s.dfs(i, y, x)
				if t != False:
					return [x] + t
		return False
T = Tree(N)
for (a, b) in ab:
	a -= 1
	b -= 1
	T.set(a, b)
D = [[-1] * N for _ in range(N)]
for i in range(N - 1):
	(a, b) = (ab[i][0] - 1, ab[i][1] - 1)
	(a, b) = (min(a, b), max(a, b))
	D[a][b] = i
NL = [[] for _ in range(M)]
for i in range(M):
	(x, y, r) = (uv[i][0] - 1, uv[i][1] - 1, uv[i][0] - 1)
	L = T.dfs(x, y, r)
	n = L[0]
	t = 0
	for j in range(1, len(L)):
		m = L[j]
		(x, y) = (min(n, m), max(n, m))
		t = t | 1 << D[x][y]
		n = m
	NL[i] = t
ans = 1 << N - 1
c = 0
for i in range(1, 1 << M):
	t = i
	f = 0
	k = 0
	for j in range(M):
		if t & 1:
			f += 1
			k = k | NL[j]
		t >>= 1
	cnt = bin(k).count('1')
	if f % 2 == 1:
		c += pow(2, N - 1 - cnt)
	else:
		c -= pow(2, N - 1 - cnt)
print(ans - c)


from collections import deque

def getPath(adj, start, goal):
	q = deque()
	q.appendleft((start, 0))
	while len(q):
		(cur, p) = q.pop()
		if cur == goal:
			return p
		for (nxt, nhop) in adj[cur]:
			if 2 ** nhop & p:
				continue
			npath = p | 2 ** nhop
			q.appendleft((nxt, npath))

def bitcount(x):
	return bin(x).count('1')

def main():
	N = int(input())
	adj = [set() for _ in range(N)]
	for i in range(N - 1):
		(a, b) = map(int, input().split())
		adj[a - 1].add((b - 1, i))
		adj[b - 1].add((a - 1, i))
	M = int(input())
	dp = [0] * 2 ** M
	for i in range(M):
		(u, v) = map(int, input().split())
		path = getPath(adj, u - 1, v - 1)
		for j in range(2 ** i):
			dp[j + 2 ** i] = dp[j] | path
	ans = 0
	for i in range(2 ** M):
		ans += (-1) ** bitcount(i) * 2 ** (N - bitcount(dp[i]) - 1)
	print(ans)
main()


N = int(input())
E = [[int(l) for l in input().split()] for _ in range(N - 1)]
M = int(input())
L = [[int(l) for l in input().split()] for _ in range(M)]

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.root = [-1] * (n + 1)
		self.rnk = [0] * (n + 1)

	def find_root(self, x):
		if self.root[x] < 0:
			return x
		else:
			self.root[x] = self.find_root(self.root[x])
			return self.root[x]

	def unite(self, x, y):
		x = self.find_root(x)
		y = self.find_root(y)
		if x == y:
			return
		elif self.rnk[x] > self.rnk[y]:
			self.root[x] += self.root[y]
			self.root[y] = x
		else:
			self.root[y] += self.root[x]
			self.root[x] = y
			if self.rnk[x] == self.rnk[y]:
				self.rnk[y] += 1

	def isSameGroup(self, x, y):
		return self.find_root(x) == self.find_root(y)
C = [0] * M
for i in range(N - 1):
	uf = UnionFind(N)
	for e in E:
		if e == E[i]:
			continue
		uf.unite(e[0], e[1])
	for l in range(M):
		if uf.isSameGroup(L[l][0], L[l][1]):
			continue
		C[l] |= 1 << i
import itertools
ans = 0
L = [int(i) for i in range(M)]
for m in range(M + 1):
	for P in itertools.combinations(L, m):
		white = 0
		for j in P:
			white |= C[j]
		if m % 2:
			ans -= 1 << N - 1 - bin(white).count('1')
		else:
			ans += 1 << N - 1 - bin(white).count('1')
print(ans)


def resolve():

	def dfs(u, v, parent):
		if u == v:
			return True
		for (to, idx) in G[u]:
			if to == parent:
				continue
			if dfs(to, v, u):
				path.append(idx)
				return True
		return False
	N = int(input())
	G = [[] for _ in range(N)]
	for i in range(N - 1):
		(a, b) = map(lambda x: int(x) - 1, input().split())
		G[a].append((b, i))
		G[b].append((a, i))
	path = []
	M = int(input())
	cons = [0] * M
	for i in range(M):
		(u, v) = map(lambda x: int(x) - 1, input().split())
		path = []
		dfs(u, v, -1)
		for idx in path:
			cons[i] |= 1 << idx
	ans = 0
	for bit in range(1 << M):
		eset = 0
		for i in range(M):
			if bit >> i & 1:
				eset |= cons[i]
		white = bin(eset).count('1')
		num = 1 << N - 1 - white
		if bin(bit).count('1') % 2 == 0:
			ans += num
		else:
			ans -= num
	print(ans)
resolve()


N = int(input())
ab = [[] for _ in range(N)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	ab[a - 1].append((b - 1, i))
	ab[b - 1].append((a - 1, i))
M = int(input())
uv = [[int(i) for i in input().split()] for _ in range(M)]
dp = [0] * M

def dfs(cur, pre, t, i):
	if cur == t:
		return True
	for (nex, j) in ab[cur]:
		if nex == pre:
			continue
		if dfs(nex, cur, t, i):
			dp[i] |= 1 << j
			return True
	return False
for (i, (u, v)) in enumerate(uv):
	dfs(u - 1, -1, v - 1, i)
ret = 1 << N - 1
for i in range(1, 1 << M):
	sgn = 1
	s = 0
	for j in range(M):
		if i & 1 << j:
			s |= dp[j]
			sgn *= -1
	ret += sgn * (1 << N - 1 - bin(s).count('1'))
print(ret)


from copy import deepcopy
from itertools import product

class EulerTour:

	def __init__(self, N):
		self.N = N
		self.G = [[] for _ in range(N)]

	def add_edge(self, a, b):
		self.G[a].append(b)
		self.G[b].append(a)

	def from_graph(self, G, copy=False):
		if copy:
			self.G = deepcopy(G)
		else:
			self.G = G

	def build(self, root=0, lca=True):
		self.root = root
		self._dfs(root)
		self.In = [0] * self.N
		self.Out = [0] * self.N
		for (i, v) in enumerate(self.node_list):
			if self.In[v] == 0:
				self.In[v] = i
			self.Out[v] = i
		if lca:
			self.seg = SegTree(len(self.node_list))
			self.seg.build([self.d[self.node_list[i]] for i in range(len(self.node_list))])

	def lca(self, a, b):
		if self.root in (a, b):
			return self.root
		(a_out, b_in) = (self.Out[a], self.In[b])
		if a_out > b_in:
			(a_out, b_in) = (self.Out[b], self.In[a])
		if a_out > b_in:
			(a_out, b_in) = (self.Out[b], self.Out[a])
		if a_out > b_in:
			(a_out, b_in) = (self.Out[a], self.Out[b])
		idx = self.seg.find(a_out, b_in + 1)
		return self.node_list[idx]

	def _dfs(self, root=0):
		self.idx2edge = {}
		self.edge2idx = {}
		self.node_list = []
		self.edge_list = []
		seen = [0] * len(self.G)
		prev = [0] * len(self.G)
		self.d = [-1] * len(self.G)
		todo = [~root, root]
		count = 0
		while todo:
			a = todo.pop()
			if a >= 0:
				seen[a] = 1
				self.d[a] = self.d[prev[a]] + 1
				edge = (prev[a], a)
				self.idx2edge[count] = edge
				self.edge2idx[edge] = count
				self.edge_list.append(count)
				self.node_list.append(a)
				count += 1
				for b in reversed(self.G[a]):
					if seen[b]:
						continue
					todo.append(~b)
					todo.append(b)
					prev[b] = a
			else:
				edge = (prev[~a], ~a)
				idx = self.edge2idx[edge]
				self.edge_list.append(-idx)
				if ~a != root:
					self.node_list.append(prev[~a])

class SegTree:

	def __init__(self, N, data_f=min, data_unit=1 << 30):
		self.N = N
		self.data_f = data_f
		self.data_unit = data_unit
		self.data = [self.data_unit] * (N + N)

	def build(self, raw_data):
		data = self.data
		f = self.data_f
		N = self.N
		data[N:] = raw_data[:]
		for i in range(N - 1, 0, -1):
			data[i] = f(data[i << 1], data[i << 1 | 1])

	def set_val(self, i, x):
		data = self.data
		f = self.data_f
		i += self.N
		data[i] = x
		while i > 1:
			data[i >> 1] = f(data[i], data[i ^ 1])
			i >>= 1

	def fold(self, L, R):
		vL = vR = self.data_unit
		data = self.data
		f = self.data_f
		L += self.N
		R += self.N
		while L < R:
			if L & 1:
				vL = f(vL, data[L])
				L += 1
			if R & 1:
				R -= 1
				vR = f(data[R], vR)
			L >>= 1
			R >>= 1
		return f(vL, vR)

	def find(self, L, R):
		x = self.fold(L, R)
		while R - L > 1:
			M = (R + L) // 2
			if self.fold(L, M) == x:
				R = M
			else:
				L = M
		return L
from collections import deque

def bfs(G, s, edge2idx):
	seen = [0] * N
	todo = deque()
	seen[s] = 1
	todo.append(s)
	cumedge = [set() for _ in range(N)]
	while len(todo):
		a = todo.popleft()
		for b in G[a]:
			if seen[b] == 0:
				seen[b] = 1
				todo.append(b)
				cumedge[b] = deepcopy(cumedge[a])
				idx = edge2idx[a, b]
				cumedge[b].add(idx)
	return cumedge
N = int(input())
et = EulerTour(N)
for i in range(N - 1):
	(a, b) = map(int, input().split())
	et.add_edge(a - 1, b - 1)
et.build(0)
cumedge = bfs(et.G, 0, et.edge2idx)
M = int(input())
path_list = [0] * M
for i in range(M):
	(u, v) = map(int, input().split())
	(u, v) = (u - 1, v - 1)
	w = et.lca(u, v)
	path_list[i] = cumedge[u] - cumedge[w] | cumedge[v] - cumedge[w]
ans = 2 ** (N - 1)
for (i, p) in enumerate(product(range(2), repeat=M)):
	if i == 0:
		continue
	union = set.union(*[path_list[i] for i in range(M) if p[i]])
	ans += (-1) ** sum(p) * 2 ** (N - 1 - len(union))
print(ans)


from itertools import combinations
N = int(input())
adj = [list() for _ in range(N)]
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	adj[a - 1].append(b - 1)
	adj[b - 1].append(a - 1)
parent = [None] * N
visited = [False] * N
visited[0] = True

def rec(u):
	for v in adj[u]:
		if not visited[v]:
			parent[v] = u
			visited[v] = True
			rec(v)
rec(0)
del adj
M = int(input())
tasks = []
for q in range(M):
	(u, v) = map(int, input().split())
	(u, v) = (u - 1, v - 1)
	u2r = []
	v2r = []
	while u is not None:
		u2r.append(u)
		u = parent[u]
	while v is not None:
		v2r.append(v)
		v = parent[v]
	for (i, (a, b)) in enumerate(zip(reversed(u2r), reversed(v2r))):
		if a != b:
			break
	else:
		i += 1
	tasks.append(u2r[:-i] + v2r[:-i])
cnt = 0
sign = 1
for n in range(1, M + 1):
	sub = 0
	for p in combinations(range(M), n):
		sub += 2 ** (N - 1 - len(set().union(*(tasks[i] for i in p))))
	cnt += sign * sub
	sign *= -1
print(2 ** (N - 1) - cnt)


n = int(input())
TE = [[] for _ in range(n)]
TE2 = []
for i in range(n - 1):
	(ai, bi) = map(int, input().split())
	ai -= 1
	bi -= 1
	TE[ai].append(bi)
	TE[bi].append(ai)
	TE2.append((ai, bi))
m = int(input())
D = []
for i in range(m):
	(ai, bi) = map(int, input().split())
	ai -= 1
	bi -= 1
	D.append((ai, bi))
bit = 1 << m
P = [0] * n
C = [[] for _ in range(n)]
from collections import deque
Q = deque()
Q.append(0)
V = [0] * n
V[0] = 1
while Q:
	v = Q.popleft()
	for u in TE[v]:
		if not V[u]:
			V[u] = 1
			Q.append(u)
			P[u] = v
			C[v].append(u)

def path(u, v):
	u_p = set()
	tmp1 = u
	while tmp1:
		u_p.add(tmp1)
		tmp1 = P[tmp1]
	u_p.add(tmp1)
	tmp2 = v
	while tmp2 not in u_p:
		tmp2 = P[tmp2]
	pth = 0
	tmp3 = u
	tmp4 = v
	while tmp3 != tmp2:
		for t in range(n - 1):
			if TE2[t] == (tmp3, P[tmp3]) or TE2[t] == (P[tmp3], tmp3):
				pth |= 1 << t
		tmp3 = P[tmp3]
	while tmp4 != tmp2:
		for t in range(n - 1):
			if TE2[t] == (tmp4, P[tmp4]) or TE2[t] == (P[tmp4], tmp4):
				pth |= 1 << t
		tmp4 = P[tmp4]
	return pth
D2 = [path(D[i][0], D[i][1]) for i in range(m)]
ans = 2 ** (n - 1)
for i in range(1, bit):
	cnt = 0
	paths = 0
	for j in range(m):
		if i >> j & 1:
			paths |= D2[j]
			cnt += 1
	cnt2 = 0
	for j in range(n - 1):
		cnt2 += paths >> j & 1
	ans += (-1) ** cnt * 2 ** (n - 1 - cnt2)
print(ans)


n = int(input())
g = [[] for _ in range(n)]
e = []
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	(a, b) = (min(a, b), max(a, b))
	g[a - 1].append(b - 1)
	g[b - 1].append(a - 1)
	e.append((a - 1, b - 1))
m = int(input())
l = [set() for _ in range(m)]
for i in range(m):
	(u, v) = map(int, input().split())
	s = [u - 1]
	dist = [-1] * n
	dist[u - 1] = 0
	r = [-1] * n
	while s:
		d = s.pop()
		for node in g[d]:
			if dist[node] == -1:
				s.append(node)
				dist[node] = dist[d] + 1
				r[node] = d
	d = v - 1
	while r[d] != -1:
		(a, b) = (min(d, r[d]), max(d, r[d]))
		l[i].add(e.index((a, b)))
		d = r[d]
ans = 0
for i in range(2 ** m):
	cnt = 0
	s = set()
	for j in range(m):
		if i >> j & 1:
			cnt += 1
			s |= l[j]
	if cnt % 2:
		ans -= 2 ** (n - len(s) - 1)
	else:
		ans += 2 ** (n - len(s) - 1)
print(ans)


import sys

def I():
	return int(sys.stdin.readline().rstrip())

def MI():
	return map(int, sys.stdin.readline().rstrip().split())
N = I()
dist = [[100] * (N + 1) for _ in range(N + 1)]
edges = {}
for i in range(N - 1):
	(a, b) = MI()
	dist[a][b] = 1
	dist[b][a] = 1
	edges[a, b] = i
	edges[b, a] = i
for i in range(1, N + 1):
	dist[i][i] = 0
for k in range(1, N + 1):
	for i in range(1, N + 1):
		for j in range(1, N + 1):
			dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
M = I()
A = []
for _ in range(M):
	(u, v) = MI()
	B = set()
	while True:
		if dist[u][v] == 1:
			B.add(edges[u, v])
			break
		else:
			for i in range(1, N + 1):
				if dist[u][i] == dist[u][v] - 1 and dist[i][v] == 1:
					B.add(edges[i, v])
					v = i
					break
	A.append(B)

def popcount(n):
	c = (n & 6148914691236517205) + (n >> 1 & 6148914691236517205)
	c = (c & 3689348814741910323) + (c >> 2 & 3689348814741910323)
	c = (c & 1085102592571150095) + (c >> 4 & 1085102592571150095)
	c = (c & 71777214294589695) + (c >> 8 & 71777214294589695)
	c = (c & 281470681808895) + (c >> 16 & 281470681808895)
	c = (c & 4294967295) + (c >> 32 & 4294967295)
	return c
ans = 0
for i in range(2 ** M):
	C = set()
	for j in range(M):
		if i >> j & 1:
			C |= A[j]
	l = len(C)
	a = popcount(i)
	a %= 2
	ans += (-1) ** a * 2 ** (N - 1 - l)
print(ans)


import sys
input = sys.stdin.readline
n = int(input())
Edge = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	Edge[a - 1].append((b - 1, i))
	Edge[b - 1].append((a - 1, i))
m = int(input())
M = []
for i in range(m):
	M.append(tuple(map(int, input().split())))
inf = float('inf')
path = [-1] * n
path[0] = 0
stack = [0]
while stack:
	cur = stack.pop()
	for (next, num) in Edge[cur]:
		if path[next] == -1:
			path[next] = path[cur] | 1 << num
			stack.append(next)

def popcount(x):
	x = x - (x >> 1 & 6148914691236517205)
	x = (x & 3689348814741910323) + (x >> 2 & 3689348814741910323)
	x = x + (x >> 4) & 1085102592571150095
	x = x + (x >> 8)
	x = x + (x >> 16)
	x = x + (x >> 32)
	return x & 127
passing = []
for (u, v) in M:
	passing.append(path[u - 1] ^ path[v - 1])
ans = 2 ** (n - 1)
Cond = [0] * 2 ** m
for i in range(1, 2 ** m):
	i_ct = popcount(i)
	Cond[i] = Cond[i ^ i & -i] | passing[len(bin(i & -i)) - 3]
	cond_ct = popcount(Cond[i])
	ans += pow(-1, i_ct) * pow(2, n - 1 - cond_ct)
print(ans)


from collections import deque
n = int(input())
ls = [list(map(lambda x: int(x) - 1, input().split())) for i in range(n - 1)]
m = int(input())
cond = [list(map(lambda x: int(x) - 1, input().split())) for i in range(m)]
ans = 0
graph = [[0] * n for _ in range(n)]
for i in range(n - 1):
	graph[ls[i][0]][ls[i][1]] += 1 << i
	graph[ls[i][1]][ls[i][0]] += 1 << i
eset = []
for cns in cond:
	d = deque()
	d.append([cns[0], 0])
	while d:
		(s, es) = d.pop()
		for i in range(n):
			if graph[s][i] and (not es & graph[s][i]):
				es2 = es | graph[s][i]
				if i == cns[1]:
					eset.append(es2)
					break
				d.append([i, es2])
for i in range(1 << m):
	mask = 0
	for j in range(m):
		if i & 1 << j:
			mask |= eset[j]
	white = bin(mask).count('1')
	if bin(i).count('1') % 2:
		ans -= 1 << n - 1 - white
	else:
		ans += 1 << n - 1 - white
print(ans)


class Tree:

	def __init__(self, n, l):
		self.n = n
		self.w = {}
		for i in range(n - 1):
			(a, b, path) = l[i]
			if a in self.w:
				self.w[a].append((b, path))
			else:
				self.w[a] = [(b, path)]
			if b in self.w:
				self.w[b].append((a, path))
			else:
				self.w[b] = [(a, path)]

	def make_parents_list(self, root):
		self.parents = {}
		que = []
		seen = {}
		for i in range(1, n + 1):
			seen[i] = 0
		self.parents[root] = (None, None)
		seen[root] = 1
		que.append(root)
		while len(que) != 0:
			node = que.pop()
			for k in range(len(self.w[node])):
				(node_2, path_2) = self.w[node][k]
				if seen[node_2] == 0:
					seen[node_2] = 1
					que.append(node_2)
					self.parents[node_2] = (node, path_2)
				else:
					continue
		return self.parents

	def lca(self, root, u, v):
		ancestors = set()
		if self.parents is None:
			parents = self.make_parents_list(root)
		else:
			parents = self.parents
		parent = u
		while parent is not None:
			ancestors.add(parent)
			parent = parents[parent][0]
		node = v
		while node not in ancestors:
			node = parents[node][0]
		return node
n = int(input())
l = []
for i in range(n - 1):
	(a, b) = [int(_) for _ in input().split()]
	l.append((a, b, i))
tree = Tree(n, l)
seiyaku = []
parents = tree.make_parents_list(1)
m = int(input())
for i in range(m):
	(u, v) = [int(_) for _ in input().split()]
	parent_node = tree.lca(1, u, v)
	s = set()
	node = u
	while node != parent_node:
		s.add(parents[node][1])
		node = parents[node][0]
	node = v
	while node != parent_node:
		s.add(parents[node][1])
		node = parents[node][0]
	seiyaku.append(s)
ans = 2 ** (n - 1)
for i in range(1, 2 ** m):
	i_bin = format(i, '0' + str(m) + 'b')
	k = 0
	q = []
	for j in range(m):
		if i_bin[j] == '1':
			q.append(j)
			k += 1
		else:
			continue
	s = set()
	for x in q:
		s |= seiyaku[x]
	ans += (-1) ** k * 2 ** (n - 1 - len(s))
print(ans)


import sys
sys.setrecursionlimit(10 ** 9)

def solve():
	N = int(input())
	adjL = [[] for _ in range(N)]
	edges = []
	for _ in range(N - 1):
		(a, b) = map(int, input().split())
		(a, b) = (a - 1, b - 1)
		adjL[a].append(b)
		adjL[b].append(a)
		if a > b:
			(a, b) = (b, a)
		edges.append((a, b))
	M = int(input())
	uvs = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(M)]

	def getPath(vSt, vEn):

		def dfs(vNow, vPar):
			if vNow == vEn:
				path.append(vNow)
				return True
			for v2 in adjL[vNow]:
				if v2 != vPar:
					if dfs(v2, vNow):
						path.append(vNow)
						return True
		path = []
		dfs(vSt, -1)
		return path
	edgeConstraints = []
	for (u, v) in uvs:
		path = getPath(u, v)
		setEdge = set()
		for j in range(len(path) - 1):
			(a, b) = (path[j], path[j + 1])
			if a > b:
				(a, b) = (b, a)
			setEdge.add((a, b))
		edge = 0
		for (j, (a, b)) in enumerate(edges):
			if (a, b) in setEdge:
				edge |= 1 << j
		edgeConstraints.append(edge)
	numEs = []
	for S in range(1 << M):
		edge = 0
		for (i, edgeConstraint) in enumerate(edgeConstraints):
			if S >> i & 1:
				edge |= edgeConstraint
		numE = bin(edge).count('1')
		numEs.append(numE)
	pow2s = [1]
	for i in range(N):
		pow2s.append(pow2s[-1] * 2)
	ans = 0
	for (S, numE) in enumerate(numEs[1:], 1):
		num1 = bin(S).count('1')
		if num1 % 2:
			ans += pow2s[N - 1 - numE]
		else:
			ans -= pow2s[N - 1 - numE]
	print(pow2s[N - 1] - ans)
solve()


import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline
n = int(input())
graph = [[] for _ in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	graph[a].append((b, i))
	graph[b].append((a, i))

def dfs(v, v_p, target):
	if v == target:
		return (True, 0)
	for (v_next, edge_idx) in graph[v]:
		if v_next == v_p:
			continue
		(is_target, path) = dfs(v_next, v, target)
		if is_target:
			return (is_target, path | 1 << edge_idx)
	return (False, 0)
m = int(input())
cond = []
for _ in range(m):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	(_, path) = dfs(u, -1, v)
	cond.append((u, v, path))
ans = 1 << n - 1
for bit in range(1, 1 << m):
	l = 0
	path = 0
	for (i, (u, v, path_i)) in enumerate(cond):
		if bit >> i & 1:
			l += 1
			path = path | path_i
	c = n - 1 - bin(path).count('1')
	ans += (-1) ** (l % 2) * (1 << c)
print(ans)


import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
from math import floor, sqrt, factorial, hypot, log
from heapq import heappop, heappush, heappushpop
from collections import Counter, defaultdict, deque
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint

def ceil(a, b):
	return (a + b - 1) // b
inf = float('inf')
mod = 10 ** 9 + 7

def pprint(*A):
	for a in A:
		print(*a, sep='\n')

def INT_(n):
	return int(n) - 1

def MI():
	return map(int, input().split())

def MF():
	return map(float, input().split())

def MI_():
	return map(INT_, input().split())

def LI():
	return list(MI())

def LI_():
	return [int(x) - 1 for x in input().split()]

def LF():
	return list(MF())

def LIN(n: int):
	return [I() for _ in range(n)]

def LLIN(n: int):
	return [LI() for _ in range(n)]

def LLIN_(n: int):
	return [LI_() for _ in range(n)]

def LLI():
	return [list(map(int, l.split())) for l in input()]

def I():
	return int(input())

def F():
	return float(input())

def ST():
	return input().replace('\n', '')

def main():
	N = I()
	edge = [[] for _ in range(N)]
	for i in range(N - 1):
		(a, b) = MI_()
		edge[a].append(b)
		edge[b].append(a)
	root = 0
	q = []
	q.append(root)
	pre = [-1] * N
	visited = [False] * N
	while q:
		v = q.pop()
		visited[v] = True
		for to in edge[v]:
			if visited[to]:
				continue
			pre[to] = v
			q.append(to)
	path = []
	constraint = []
	M = I()
	for i in range(M):
		(a, b) = MI_()
		constraint.append((a, b))
		root_path_a = 1 << a
		root_path_b = 1 << b
		while a != root:
			root_path_a |= 1 << pre[a]
			a = pre[a]
		while b != root:
			root_path_b |= 1 << pre[b]
			b = pre[b]
		path.append(root_path_a ^ root_path_b)
		if not path[-1] >> a & 1:
			path[-1] |= 1 << a
		if not path[-1] >> b & 1:
			path[-1] |= 1 << b
	ans = 0
	for mask in range(1 << M):
		builtin_count = 0
		U = 0
		for i in range(M):
			if mask >> i & 1:
				builtin_count += 1
				U |= path[i]
		edge_cnt = max(0, bin(U).count('1') - 1)
		if builtin_count & 1:
			ans -= 1 << N - 1 - edge_cnt
		else:
			ans += 1 << N - 1 - edge_cnt
	print(ans)
main()


N = int(input())
X = [[] for i in range(N)]
for i in range(N - 1):
	(x, y) = map(int, input().split())
	X[x - 1].append(y - 1)
	X[y - 1].append(x - 1)
P = [-1] * N
DE = [0] * N
Q = [0]
while Q:
	i = Q.pop()
	for a in X[i][::-1]:
		if a != P[i]:
			P[a] = i
			DE[a] = DE[i] + 1
			X[a].remove(i)
			Q.append(a)

def lp(u, v):
	t = 0
	while u != v:
		if DE[u] > DE[v]:
			t += 1 << u - 1
			u = P[u]
		elif DE[u] < DE[v]:
			t += 1 << v - 1
			v = P[v]
		else:
			t += 1 << u - 1
			t += 1 << v - 1
			u = P[u]
			v = P[v]
	return t
Y = []
M = int(input())
for _ in range(M):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	Y.append(lp(a, b))

def popcnt(n):
	c = (n & 6148914691236517205) + (n >> 1 & 6148914691236517205)
	c = (c & 3689348814741910323) + (c >> 2 & 3689348814741910323)
	c = (c & 1085102592571150095) + (c >> 4 & 1085102592571150095)
	c = (c & 71777214294589695) + (c >> 8 & 71777214294589695)
	c = (c & 281470681808895) + (c >> 16 & 281470681808895)
	c = (c & 4294967295) + (c >> 32 & 4294967295)
	return c
D = {1 << i: i for i in range(50)}
Z = [0] * (1 << M)
ans = 0
CC = [0] * N
for m in range(1 << M):
	a = m & -m
	if a == m:
		if a == 0:
			Z[m] = 0
		else:
			Z[m] = Y[D[a]]
	else:
		Z[m] = Z[m ^ a] | Y[D[a]]
	CC[N - 1 - popcnt(Z[m])] += 1 if popcnt(m) & 1 == 0 else -1
print(sum([2 ** i * CC[i] for i in range(N)]))


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque
n = int(readline())
g = [[] * n for i in range(n)]
for i in range(n - 1):
	(u, v) = map(int, readline().split())
	u -= 1
	v -= 1
	g[u].append(v)
	g[v].append(u)
m = int(readline())
c = []
for i in range(m):
	(u, v) = map(int, readline().split())
	u -= 1
	v -= 1
	que = deque()
	que.append((u, set()))
	chk = [False] * n
	chk[u] = True
	while que:
		(now, L) = que.popleft()
		if now == v:
			c.append(L)
			break
		for i in g[now]:
			if not chk[i]:
				chk[i] = True
				mi = min(now, i)
				ma = max(now, i)
				que.append((i, L | {mi * 100 + ma}))
import itertools
ans = 1 << n - 1
for i in range(1, m + 1):
	for j in itertools.combinations(c, i):
		K = set()
		for k in j:
			K |= k
		l = len(K)
		ans += pow(-1, i) * pow(2, n - 1 - l)
print(ans)


class Node:

	def __init__(self, num):
		self.num = num
		self.depth = 0
		self.parent = (None, None)
LI = lambda : list(map(int, input().split()))
N = int(input())
AB = [LI() for _ in range(N - 1)]
M = int(input())
UV = [LI() for _ in range(M)]
links = [[] for _ in range(N)]
nodes = [Node(i) for i in range(N)]
w = []
p2 = [2 ** i for i in range(51)]

def create_links():
	for i in range(N - 1):
		(a, b) = (AB[i][0] - 1, AB[i][1] - 1)
		links[a].append((b, i))
		links[b].append((a, i))

def create_tree(v, p=-1):
	for (u, i) in links[v]:
		if u == p:
			continue
		nodes[u].parent = (nodes[v], i)
		nodes[u].depth = nodes[v].depth + 1
		create_tree(u, v)

def between_links(s, t):
	x = nodes[s]
	y = nodes[t]
	if x.depth > y.depth:
		(x, y) = (y, x)
	s = set()
	while x.depth < y.depth:
		(y, i) = y.parent
		s.add(i)
	while x is not y:
		(x, i) = x.parent
		(y, j) = y.parent
		s.add(i)
		s.add(j)
	return s

def create_between_links():
	for (u, v) in UV:
		s = between_links(u - 1, v - 1)
		w.append(s)

def main():
	create_links()
	create_tree(0)
	create_between_links()
	ans = 0
	n = p2[M]
	for i in range(n):
		f = 0
		s = set()
		for j in range(M):
			if i >> j & 1:
				f += 1
				s |= w[j]
		v = p2[N - 1 - len(s)]
		if f % 2 == 0:
			ans += v
		else:
			ans -= v
	print(ans)
main()


import sys

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def popcount(i):
	return bin(i).count('1')

def dfs(i, N, nodes, src, dest):
	dist = [INF] * N

	def rec(u, prev, c):
		if u == dest:
			return True
		dist[u] = c
		for v in nodes[u]:
			if v != prev:
				if rec(v, u, c + 1):
					A[i] |= 1 << edges[u, v]
					return True
		return False
	rec(src, -1, 0)
N = INT()
nodes = [[] for i in range(N)]
edges = {}
for i in range(N - 1):
	(a, b) = MAP()
	a -= 1
	b -= 1
	nodes[a].append(b)
	nodes[b].append(a)
	edges[a, b] = i
	edges[b, a] = i
M = INT()
A = [0] * M
for i in range(M):
	(u, v) = MAP()
	u -= 1
	v -= 1
	dfs(i, N, nodes, u, v)
ans = 2 ** (N - 1)
for S in range(1, 1 << M):
	S2 = 0
	for i in range(M):
		if S & 1 << i:
			S2 |= A[i]
	edgecnt = popcount(S2)
	cnt = 2 ** (N - 1 - edgecnt)
	if popcount(S) % 2 == 1:
		ans -= cnt
	else:
		ans += cnt
print(ans)


from copy import copy

def dfs(x, v, s):
	for (y, i) in tree[x]:
		if parent[x] != y:
			parent[y] = x
			s.add(i)
			dfs(y, v, s)
			s.remove(i)
	if x == v:
		cons.append(s.copy())
N = int(input())
tree = [[] for _ in range(N + 1)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	tree[a].append((b, i))
	tree[b].append((a, i))
M = int(input())
uv = []
cons = []
for i in range(M):
	(u, v) = map(int, input().split())
	uv.append((u, v))
	parent = [-1] * (N + 1)
	dfs(u, v, set())
bit = [0] * (N - 1)
for i in range(N):
	for j in range(M):
		if i in cons[j]:
			bit[i] += 1 << j
dp = [0] * (1 << M)
dp[0] = 1
for i in range(N - 1):
	for j in range(1 << M)[::-1]:
		dp[j | bit[i]] += dp[j]
print(dp[-1])


import sys
input = sys.stdin.readline

class LCA(object):

	def __init__(self, n, root, edges, decrement=True):
		self.n = n
		self.decrement = decrement
		self.root = root - self.decrement
		self.edges = [set() for _ in range(self.n)]
		i = 0
		for (x, y) in edges:
			self.add_edge(x, y, i)
			i += 1
		self.k_max = (self.n - 1).bit_length()
		self.depth = [-1 if i != self.root else 0 for i in range(self.n)]
		self.doubling = [[-1] * self.n for _ in range(self.k_max)]
		self.path_bit = [-1] * self.n
		self.dfs()
		for i in range(1, self.k_max):
			for k in range(self.n):
				if self.doubling[i - 1][k] != -1:
					self.doubling[i][k] = self.doubling[i - 1][self.doubling[i - 1][k]]

	def add_edge(self, x, y, i):
		if self.decrement:
			x -= 1
			y -= 1
		self.edges[x].add((y, i))
		self.edges[y].add((x, i))

	def dfs(self):
		next_set = [self.root]
		self.path_bit[self.root] = 0
		while next_set:
			p = next_set.pop()
			for (q, i) in self.edges[p]:
				if self.depth[q] == -1:
					self.depth[q] = self.depth[p] + 1
					self.path_bit[q] = self.path_bit[p] | 1 << i
					self.doubling[0][q] = p
					next_set += [q]

	def get_list(self, u, v):
		if self.decrement:
			u -= 1
			v -= 1
		return self.path_bit[u] ^ self.path_bit[v]

	def draw(self):
		import matplotlib.pyplot as plt
		import networkx as nx
		G = nx.Graph()
		for x in range(self.n):
			for y in self.edges[x]:
				G.add_edge(x + self.decrement, y + self.decrement)
		pos = nx.spring_layout(G)
		nx.draw_networkx(G, pos)
		plt.axis('off')
		plt.show()
from itertools import combinations

def popcnt(n):
	c = (n & 6148914691236517205) + (n >> 1 & 6148914691236517205)
	c = (c & 3689348814741910323) + (c >> 2 & 3689348814741910323)
	c = (c & 1085102592571150095) + (c >> 4 & 1085102592571150095)
	c = (c & 71777214294589695) + (c >> 8 & 71777214294589695)
	c = (c & 281470681808895) + (c >> 16 & 281470681808895)
	c = (c & 4294967295) + (c >> 32 & 4294967295)
	return c
N = int(input())
edges = []
for _ in range(N - 1):
	(x, y) = map(int, input().split())
	edges.append((x, y))
lca = LCA(N, 1, edges, decrement=True)
M = int(input())
edges2 = []
for _ in range(M):
	(x, y) = map(int, input().split())
	edges2.append((x, y))
res = pow(2, N - 1)
for m in range(1, M + 1):
	for a in combinations(edges2, m):
		temp = 0
		for b in a:
			temp |= lca.get_list(*b)
		res += (1 - 2 * (m % 2)) * pow(2, N - 1 - popcnt(temp))
print(res)


import math
import os
import sys
if os.getenv('LOCAL'):
	sys.stdin = open('_in.txt', 'r')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
IINF = 10 ** 18
MOD = 10 ** 9 + 7

class DoublingLCA:

	def __init__(self, graph, max_v, root):
		self.graph = graph
		self.size = max_v + 1
		self.root = root
		self.MAX_LOG_V = math.floor(math.log(self.size, 2)) + 1
		self.depths = [-1] * self.size
		self.parents = [[-1] * self.size for _ in range(self.MAX_LOG_V)]
		self._init()

	def _init(self):
		seen = [False] * self.size
		stack = [(self.root, 0, -1)]
		while stack:
			(v, d, par) = stack.pop()
			self.parents[0][v] = par
			self.depths[v] = d
			seen[v] = True
			for u in self.graph[v]:
				if not seen[u]:
					stack.append((u, d + 1, v))
		for k in range(self.MAX_LOG_V - 1):
			for v in range(self.size):
				if self.parents[k][v] < 0:
					self.parents[k + 1][v] = -1
				else:
					self.parents[k + 1][v] = self.parents[k][self.parents[k][v]]

	def lca(self, u, v):
		if self.depths[u] > self.depths[v]:
			(u, v) = (v, u)
		for k in range(self.MAX_LOG_V):
			if self.depths[v] - self.depths[u] >> k & 1:
				v = self.parents[k][v]
		if v == u:
			return v
		for k in reversed(range(self.MAX_LOG_V)):
			if self.parents[k][u] != self.parents[k][v]:
				u = self.parents[k][u]
				v = self.parents[k][v]
		return self.parents[0][u]

	def distance(self, u, v):
		lca = self.lca(u, v)
		return self.depths[u] + self.depths[v] - self.depths[lca] * 2
N = int(sys.stdin.buffer.readline())
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N - 1)]
M = int(sys.stdin.buffer.readline())
VU = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]
graph = [[] for _ in range(N)]
edges_i = {}
for (i, (a, b)) in enumerate(AB):
	a -= 1
	b -= 1
	graph[a].append(b)
	graph[b].append(a)
	edges_i[a, b] = i
	edges_i[b, a] = i
root = 0
parents = [None] * N
stack = [(root, None)]
while stack:
	(v, p) = stack.pop()
	parents[v] = p
	for u in graph[v]:
		if u == p:
			continue
		stack.append((u, v))
lca = DoublingLCA(graph=graph, max_v=N - 1, root=root)
constraints = [0] * M
for (i, (v, u)) in enumerate(VU):
	v -= 1
	u -= 1
	ancestor = lca.lca(v, u)
	while v != ancestor:
		constraints[i] |= 1 << edges_i[v, parents[v]]
		v = parents[v]
	while u != ancestor:
		constraints[i] |= 1 << edges_i[u, parents[u]]
		u = parents[u]

def count(edges_bin):
	cnt = 0
	while edges_bin > 0:
		cnt += edges_bin & 1
		edges_bin >>= 1
	return pow(2, N - 1 - cnt)
ans = 0
for choice in range(1, 1 << M):
	cnt = 0
	edges = 0
	for i in range(choice.bit_length()):
		if choice >> i & 1:
			cnt += 1
			edges |= constraints[i]
	ans += count(edges) * (-1) ** (cnt - 1)
print(2 ** (N - 1) - ans)


from collections import defaultdict

def get_path(from_node, to_node, adj, nodes2edge):

	def dfs(node, parent, edges):
		if node == to_node:
			return edges
		min_path = None
		for child in adj[node]:
			if child == parent:
				continue
			path = dfs(child, node, edges + [nodes2edge[node, child]])
			if path is None:
				continue
			if min_path is None or len(min_path) > len(path):
				min_path = path
		return min_path
	return dfs(from_node, None, list())

def count_bits(n):
	return len([i for i in range(len('{:b}'.format(n))) if n >> i & 1 == 1])

def main():
	N = int(input())
	adj = defaultdict(list)
	nodes2edge = defaultdict(lambda : -1)
	for i in range(N - 1):
		(a, b) = list(map(lambda x: int(x) - 1, input().split(' ')))
		adj[a].append(b)
		adj[b].append(a)
		nodes2edge[a, b] = i
		nodes2edge[b, a] = i
	M = int(input())
	constraints = [list(map(lambda x: int(x) - 1, input().split(' '))) for _ in range(M)]
	base = [0] * M
	for (m, constraint) in enumerate(constraints):
		(u, v) = constraint
		path = get_path(u, v, adj, nodes2edge)
		v = sum([2 ** e for e in path])
		base[m] = v
	dp = [0] * 2 ** M
	ans = 2 ** (N - 1)
	for S in range(1, 2 ** M):
		lenbit_s = len('{:b}'.format(S))
		dp[S] = dp[S - (1 << lenbit_s - 1)] | base[lenbit_s - 1]
		cnt_s = count_bits(S)
		cnt_dp = count_bits(dp[S])
		ans += (-1) ** (cnt_s % 2) * 2 ** (N - 1 - cnt_dp)
	print(ans)
main()


from collections import deque

def bfs():
	q = deque([0])
	bit = [-1] * N
	bit[0] = 0
	serial = 0
	while q:
		v = q.popleft()
		for nv in adj_list[v]:
			if bit[nv] != -1:
				continue
			bit[nv] = bit[v] | 1 << serial
			serial += 1
			q.append(nv)
	return bit
N = int(input())
adj_list = [[] for _ in range(N)]
for _ in range(N - 1):
	(ai, bi) = map(int, input().split())
	adj_list[ai - 1].append(bi - 1)
	adj_list[bi - 1].append(ai - 1)
bit = bfs()
M = int(input())
uv = []
path_bit = []
for _ in range(M):
	(ui, vi) = map(int, input().split())
	uv.append((ui - 1, vi - 1))
	path_bit.append(bit[ui - 1] ^ bit[vi - 1])
houzyo = 0
for i in range(1, 2 ** M):
	covered = 0
	c = 0
	for j in range(M):
		if i >> j & 1:
			covered |= path_bit[j]
			c += 1
	no_covered = 0
	for j in range(N - 1):
		if not covered >> j & 1:
			no_covered += 1
	if c % 2 == 1:
		houzyo += 2 ** no_covered
	else:
		houzyo -= 2 ** no_covered
print(2 ** (N - 1) - houzyo)


import sys
input = sys.stdin.buffer.readline
from collections import defaultdict
import queue
con = 10 ** 9 + 7
INF = float('inf')

class Graph(object):

	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

class BFS(object):

	def __init__(self, graph, s, N):
		self.g = graph.graph
		self.Q = queue.Queue()
		self.Q.put(s)
		self.visit = ['No'] * N
		self.visit[s] = 'Yes'
		self.prev = [None] * N
		while not self.Q.empty():
			v = self.Q.get()
			for i in self.g[v]:
				if self.visit[i] == 'No':
					self.prev[i] = v
					self.Q.put(i)
					self.visit[i] = 'Yes'

def getlist():
	return list(map(int, input().split()))

def main():
	N = int(input())
	G = Graph()
	D = defaultdict(int)
	for i in range(N - 1):
		(a, b) = sorted(getlist())
		a -= 1
		b -= 1
		G.add_edge(a, b)
		G.add_edge(b, a)
		D[10000 * a + b] = i
	M = int(input())
	MbitTable = [0] * (N - 1)
	for i in range(M):
		(u, v) = getlist()
		u -= 1
		v -= 1
		BF = BFS(G, u, N)
		prev = BF.prev
		node = v
		edge = []
		while prev[node] != None:
			(a, b) = sorted([node, prev[node]])
			edgenum = D[10000 * a + b]
			edge.append(edgenum)
			node = prev[node]
		for j in edge:
			MbitTable[j] += 2 ** i
	DP = [[0] * 2 ** M for i in range(N)]
	DP[0][0] = 1
	for i in range(N - 1):
		for j in range(2 ** M):
			DP[i + 1][j] += DP[i][j]
			DP[i + 1][j | MbitTable[i]] += DP[i][j]
	print(DP[-1][-1])
main()


import collections
from itertools import combinations
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)]

def popcount(x):
	x = x - (x >> 1 & 6148914691236517205)
	x = (x & 3689348814741910323) + (x >> 2 & 3689348814741910323)
	x = x + (x >> 4) & 1085102592571150095
	x = x + (x >> 8)
	x = x + (x >> 16)
	x = x + (x >> 32)
	return x & 127
G = [[-1] * N for i in range(N)]
for i in range(N - 1):
	(a, b) = ab[i]
	a -= 1
	b -= 1
	G[a][b] = i
	G[b][a] = i
q = collections.deque()
G2 = [[0 for j in range(N)] for i in range(N)]
for i in range(N):
	q.append((i, 0))
	reached = [False] * N
	reached[i] = True
	while q:
		(x, s) = q.popleft()
		for y in range(N):
			if G[x][y] == -1 or reached[y]:
				continue
			else:
				G2[i][y] = s | 1 << G[x][y]
				q.append((y, s | 1 << G[x][y]))
				reached[y] = True
ans = 2 ** (N - 1)
ans2 = 0
for i in range(1, 2 ** M):
	tmp = 2 ** (N - 1) - 1
	for j in range(M):
		if (i >> j) % 2 == 1:
			(u, v) = uv[j]
			u -= 1
			v -= 1
			tmp &= ~G2[u][v]
	ans2 += (-1) ** (popcount(i) - 1) * (1 << popcount(tmp))
print(ans - ans2)


INF = 1 << 30
n = int(input())
g = [[] for i in range(n)]
num = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	g[a].append(b)
	g[b].append(a)
	num[a].append(i)
	num[b].append(i)
m = int(input())
u = [0 for i in range(m)]
v = [0 for i in range(m)]
ls = [0 for i in range(m)]
for i in range(m):
	(u[i], v[i]) = map(int, input().split())
	u[i] -= 1
	v[i] -= 1
	cost = [INF for j in range(n)]
	cost[u[i]] = 0
	st = [u[i]]
	pre = [-1 for j in range(n)]
	pre[u[i]] = -2
	while len(st) > 0:
		now = st.pop()
		for to in g[now]:
			if pre[to] == -1:
				pre[to] = now
				st.append(to)
	pos = v[i]
	while pos != u[i]:
		for j in range(len(g[pos])):
			to = g[pos][j]
			if to == pre[pos]:
				ls[i] |= 1 << num[pos][j]
				pos = to
				break
ans = 0
for bit in range(1 << m):
	cnt = 0
	val = 0
	for i in range(m):
		if bit >> i & 1 == 1:
			cnt += 1
			val |= ls[i]
	pcnt = 0
	for i in range(n):
		if val >> i & 1 == 1:
			pcnt += 1
	nokori = n - 1 - pcnt
	if cnt % 2 == 0:
		ans += 2 ** nokori + 1
	else:
		ans -= 2 ** nokori + 1
print(ans)


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)


from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def MI():
	return map(int, sys.stdin.readline().split())

def MI1():
	return map(int1, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]

def main():

	def dfs(u, v, pu=-1):
		if u == v:
			return True
		for cu in to[u]:
			if cu == pu:
				continue
			if dfs(cu, v, u):
				path.append(uvtoi[u, cu])
				return True
		return False
	to = defaultdict(list)
	n = II()
	uvtoi = {}
	for i in range(n - 1):
		(a, b) = MI1()
		to[a].append(b)
		to[b].append(a)
		uvtoi[a, b] = i
		uvtoi[b, a] = i
	m = II()
	itoj = defaultdict(list)
	for j in range(m):
		(u, v) = MI1()
		path = []
		dfs(u, v)
		for i in path:
			itoj[i].append(j)
	en = len(itoj)
	dp = [[0] * (1 << m) for _ in range(en + 1)]
	dp[0][0] = 1
	for (i, jj) in enumerate(itoj.values()):
		mask = sum((1 << j for j in jj))
		for bit in range(1 << m):
			pre = dp[i][bit]
			if pre == 0:
				continue
			dp[i + 1][bit | mask] += pre
			dp[i + 1][bit] += pre
	ans = dp[-1][-1] * pow(2, n - 1 - en)
	print(ans)
main()


from collections import deque
from collections import Counter
N = int(input())
E = [set() for _ in range(N)]
for i in range(N - 1):
	(a, b) = map(lambda x: int(x) - 1, input().split())
	E[a].add((b, i))
	E[b].add((a, i))
M = int(input())
P = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(M)]
pc = [set() for _ in range(M)]

def bfs(S, G, p):
	q = deque([S])
	parent = [(-1, -1)] * N
	while q:
		n = q.popleft()
		for (to, i) in E[n]:
			if parent[to][0] != -1:
				continue
			parent[to] = (n, i)
			if to == G:
				break
			q.append(to)
	n = G
	while n != S:
		(n, i) = parent[n]
		pc[p].add(i)
for (i, p) in enumerate(P):
	bfs(p[0], p[1], i)
ans = 0
for i in range(1 << M):
	whiteset = set()
	sign = 1
	for j in range(M):
		if i >> j & 1:
			whiteset |= pc[j]
			sign *= -1
	ans += sign * (1 << N - 1 - len(whiteset))
print(ans)


n = int(input())
ab = {i: [] for i in range(n)}
for j in range(n - 1):
	(a, b) = [int(i) - 1 for i in input().split()]
	ab[a].append((b, j))
	ab[b].append((a, j))

def dfs(a, b, d=[], c=-1):
	if a == b:
		return d
	for i in ab[a]:
		if i[0] == c:
			continue
		e = dfs(i[0], b, d + [i[1]], a)
		if len(e) != 0:
			return set(e)
	return set()
m = int(input())
ms = []
for _ in range(m):
	(u, p) = [int(i) - 1 for i in input().split()]
	ms.append(dfs(u, p))
ans = 0
for i in range(1 << m):
	k = 0
	a = set()
	for j in range(m):
		if i >> j & 1 == 1:
			k += 1
			a |= ms[j]
	if k % 2 == 1:
		ans += 2 ** (n - 1 - len(a))
	elif k != 0:
		ans -= 2 ** (n - 1 - len(a))
print(2 ** (n - 1) - ans)


import itertools
from collections import defaultdict
N = int(input())
G = [[] for i in range(N + 1)]
edge = defaultdict(int)
for i in range(N - 1):
	(a, b) = map(int, input().split())
	edge[min(a, b), max(a, b)] = i + 1
	G[a].append(b)
	G[b].append(a)
M = int(input())
que = [tuple(map(int, input().split())) for i in range(M)]
Data = [set([]) for i in range(M)]

def dfs(node):
	visited[node] = True
	for child in G[node]:
		if visited[child] == False:
			parent[child] = node
			dfs(child)
for i in range(M):
	(s, g) = que[i]
	visited = [False for i in range(N + 1)]
	parent = [-1 for i in range(N + 1)]
	dfs(s)
	now = g
	while parent[now] > 0:
		number = edge[min(now, parent[now]), max(now, parent[now])]
		Data[i].add(number)
		now = parent[now]
ans = 2 ** (N - 1)
seq = [i for i in range(M)]
for i in range(1, M + 1):
	S = 0
	for v in itertools.combinations(seq, i):
		subset = set([])
		for x in v:
			subset = subset | Data[x]
		S += 2 ** (N - 1 - len(subset))
	ans -= (-1) ** ((i - 1) % 2) * S
print(ans)


import sys
input = sys.stdin.readline

def main():
	n = int(input())
	T = [[] for _ in range(n)]
	D = {}
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		a -= 1
		b -= 1
		T[a].append(b)
		T[b].append(a)
		D[a, b] = 1 << i
		D[b, a] = 1 << i
	m = int(input())

	def dfs(u, v):
		parent = [-1] * n
		seen = [False] * n
		stack = [u]
		seen[u] = True
		while stack:
			nv = stack[-1]
			if nv == v:
				return stack
			for i in T[nv]:
				if seen[i]:
					continue
				stack.append(i)
				seen[i] = True
				break
			else:
				stack.pop()

	def popcount(n):
		c = (n & 6148914691236517205) + (n >> 1 & 6148914691236517205)
		c = (c & 3689348814741910323) + (c >> 2 & 3689348814741910323)
		c = (c & 1085102592571150095) + (c >> 4 & 1085102592571150095)
		c = (c & 71777214294589695) + (c >> 8 & 71777214294589695)
		c = (c & 281470681808895) + (c >> 16 & 281470681808895)
		c = (c & 4294967295) + (c >> 32 & 4294967295)
		return c
	E = [0] * m
	for i in range(m):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		edge = dfs(u, v)
		for j in range(len(edge) - 1):
			E[i] |= D[edge[j], edge[j + 1]]
	ans = 0
	for i in range(2 ** m):
		s = 0
		for j in range(m):
			if i >> j & 1:
				s |= E[j]
		cnt = popcount(i) % 2
		ans += (-1) ** cnt * 2 ** (n - 1 - popcount(s))
	print(ans)
main()


import sys
from itertools import combinations
from collections import defaultdict
input = sys.stdin.readline
N = int(input())
ab = [list(map(int, input().split())) for i in range(N - 1)]
M = int(input())
uv = [list(map(int, input().split())) for i in range(M)]
g = defaultdict(list)
pathnum = {}
for (n, (a, b)) in enumerate(ab):
	g[a].append(b)
	g[b].append(a)
	(a, b) = sorted([a, b])
	pathnum[a, b] = n

def eulerTour(g, s):
	n = len(g)
	dq = [s]
	ls = [-1] * (n + 1)
	rs = [-1] * (n + 1)
	vtour = []
	etour = []
	depth = [-1] * (n + 1)
	parent = [False] * (n + 1)
	visited = [False] * (n + 1)

	def dfs(v, d):
		depth[v] = d
		visited[v] = True
		ls[v] = len(vtour)
		vtour.append(v)
		etour.append(v)
		for nv in g[v]:
			if not visited[nv]:
				parent[nv] = v
				dfs(nv, d + 1)
		rs[v] = len(vtour)
		etour.append(-v)
		vtour.append(parent[v])
	dfs(s, 0)
	return (ls, rs, etour, vtour, parent, depth)
(ls, rs, etour, vtour, parent, depth) = eulerTour(g, 1)
paths = []
depthind = [depth[v] for v in vtour]
for (u, v) in uv:
	(l, r) = (ls[u], ls[v])
	(l, r) = (l, r) if l < r else (r, l)
	lcaind = depthind[l:r].index(min(depthind[l:r]))
	lca = vtour[l + lcaind]
	lpath = []
	x = u
	while x != lca:
		lpath.append(pathnum[tuple(sorted((x, parent[x])))])
		x = parent[x]
	rpath = []
	x = v
	while x != lca:
		rpath.append(pathnum[tuple(sorted((x, parent[x])))])
		x = parent[x]
	path = set(lpath + rpath)
	h = sum([1 << i for i in path])
	paths.append(h)
ans = 2 ** (N - 1)
memo = {1 << i: paths[i] for i in range(M)}
memo[0] = 0
for i in range(1, M + 1):
	for vs in combinations(list(range(M)), i):
		sign = i % 2
		h = sum([1 << i for i in vs])
		ph = h ^ 1 << vs[-1]
		sect = memo[ph] | paths[vs[-1]]
		memo[h] = sect
		num = N - 1 - str(bin(sect)).count('1')
		ans += (-1) ** sign * 2 ** num
print(ans)


N = int(input())
X = [[] for i in range(N)]
for i in range(N - 1):
	(x, y) = map(int, input().split())
	X[x - 1].append(y - 1)
	X[y - 1].append(x - 1)
P = [-1] * N
DE = [0] * N
Q = [0]
while Q:
	i = Q.pop()
	for a in X[i][::-1]:
		if a != P[i]:
			P[a] = i
			DE[a] = DE[i] + 1
			X[a].remove(i)
			Q.append(a)

def lp(u, v):
	t = 0
	while u != v:
		if DE[u] > DE[v]:
			t += 1 << u - 1
			u = P[u]
		elif DE[u] < DE[v]:
			t += 1 << v - 1
			v = P[v]
		else:
			t += 1 << u - 1
			t += 1 << v - 1
			u = P[u]
			v = P[v]
	return t
Y = []
M = int(input())
for _ in range(M):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	Y.append(lp(a, b))
D = {1 << i: i for i in range(50)}
Z = [0] * (1 << M)
ans = 0
CC = [0] * N
BC = [0] * (1 << 17)
for m in range(1, 1 << 17):
	a = m & -m
	BC[m] = BC[m ^ a] + 1
for m in range(1 << M):
	a = m & -m
	if a == m:
		if a == 0:
			Z[m] = 0
		else:
			Z[m] = Y[D[a]]
	else:
		Z[m] = Z[m ^ a] | Y[D[a]]
	aa = Z[m]
	bc = BC[aa % (1 << 17)]
	aa >>= 17
	bc += BC[aa % (1 << 17)]
	aa >>= 17
	bc += BC[aa]
	CC[N - 1 - bc] += 1 if BC[m % 1024] + BC[m >> 10] & 1 == 0 else -1
print(sum([2 ** i * CC[i] for i in range(N)]))


class Tree:

	def __init__(self, n, edge, indexed=1):
		self.n = n
		self.tree = [[] for _ in range(n)]
		for e in edge:
			self.tree[e[0] - indexed].append(e[1] - indexed)
			self.tree[e[1] - indexed].append(e[0] - indexed)

	def setroot(self, root):
		self.root = root
		self.parent = [None for _ in range(self.n)]
		self.parent[root] = -1
		self.depth = [None for _ in range(self.n)]
		self.depth[root] = 0
		self.order = []
		self.order.append(root)
		self.size = [1 for _ in range(self.n)]
		stack = [root]
		while stack:
			node = stack.pop()
			for adj in self.tree[node]:
				if self.parent[adj] is None:
					self.parent[adj] = node
					self.depth[adj] = self.depth[node] + 1
					self.order.append(adj)
					stack.append(adj)
		for node in self.order[::-1]:
			for adj in self.tree[node]:
				if self.parent[node] == adj:
					continue
				self.size[node] += self.size[adj]

	def heavylight_decomposition(self):
		self.order = [None for _ in range(self.n)]
		self.head = [None for _ in range(self.n)]
		self.head[self.root] = self.root
		self.next = [None for _ in range(self.n)]
		stack = [self.root]
		order = 0
		while stack:
			node = stack.pop()
			self.order[node] = order
			order += 1
			maxsize = 0
			for adj in self.tree[node]:
				if self.parent[node] == adj:
					continue
				if maxsize < self.size[adj]:
					maxsize = self.size[adj]
					self.next[node] = adj
			for adj in self.tree[node]:
				if self.parent[node] == adj or self.next[node] == adj:
					continue
				self.head[adj] = adj
				stack.append(adj)
			if self.next[node] is not None:
				self.head[self.next[node]] = self.head[node]
				stack.append(self.next[node])

	def range_hld(self, u, v, edge=False):
		res = []
		while True:
			if self.order[u] > self.order[v]:
				(u, v) = (v, u)
			if self.head[u] != self.head[v]:
				res.append((self.order[self.head[v]], self.order[v] + 1))
				v = self.parent[self.head[v]]
			else:
				res.append((self.order[u] + edge, self.order[v] + 1))
				return res
import sys
input = sys.stdin.readline
N = int(input())
edge = [tuple(map(int, input().split())) for _ in range(N - 1)]
M = int(input())
restriction = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(M)]
t = Tree(N, edge)
t.setroot(0)
t.heavylight_decomposition()
white_node = [set() for _ in range(M)]
for i in range(M):
	(u, v) = restriction[i]
	for (lt, rt) in t.range_hld(u, v, 1):
		for j in range(lt, rt):
			white_node[i].add(j)
res = 0
for bit in range(2 ** M):
	cnt = 0
	det = set()
	for i in range(M):
		if bit >> i & 1:
			cnt += 1
			det |= white_node[i]
	if cnt % 2 == 0:
		res += 2 ** (N - 1 - len(det))
	else:
		res -= 2 ** (N - 1 - len(det))
print(res)


import os
import sys
from functools import lru_cache
if os.getenv('LOCAL'):
	sys.stdin = open('_in.txt', 'r')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
IINF = 10 ** 18
MOD = 10 ** 9 + 7
N = int(sys.stdin.buffer.readline())
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N - 1)]
M = int(sys.stdin.buffer.readline())
VU = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]
graph = [[] for _ in range(N)]
edges = {}
for (i, (a, b)) in enumerate(AB):
	a -= 1
	b -= 1
	graph[a].append(b)
	graph[b].append(a)
	edges[a, b] = i
	edges[b, a] = i

@lru_cache(maxsize=None)
def path(v, u, p):
	if v == u:
		return [u]
	for nv in graph[u]:
		if nv == p:
			continue
		ret = path(v, nv, u)
		if ret is not None:
			return ret + [u]
	return None
constraints = [0 for _ in range(N - 1)]
for (i, (v, u)) in enumerate(VU):
	v -= 1
	u -= 1
	pp = path(v, u, None)
	for (pv, pu) in zip(pp, pp[1:]):
		constraints[edges[pv, pu]] |= 1 << i
dp = [0 for _ in range(1 << M)]
dp[0] = 1
for c in constraints:
	for i in reversed(range(1 << M)):
		dp[i | c] += dp[i]
print(dp[-1])


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop, heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10 ** 9 + 7
inf = float('inf')

def I():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))
n = I()
ab = [LI() for _ in range(n - 1)]
m = I()
uv = [LI() for _ in range(m)]
edge = [[] for i in range(n)]
lst = [[None] * n for i in range(n)]
cnt = 0
for (i, [a, b]) in enumerate(ab):
	edge[a - 1].append(b - 1)
	edge[b - 1].append(a - 1)
	lst[a - 1][b - 1] = i
	lst[b - 1][a - 1] = i
L = []
for (u, v) in uv:
	stack = deque()
	stack.append(u - 1)
	flg = [True] * n
	par = [None] * n
	par[u - 1] = -1
	while stack:
		x = stack.pop()
		if x == v - 1:
			break
		flg[x] = False
		for y in edge[x]:
			if flg[y]:
				par[y] = x
				stack.append(y)
	tmp = v - 1
	tmp2 = []
	while 1:
		if par[tmp] == -1:
			break
		tmp2.append(lst[tmp][par[tmp]])
		tmp = par[tmp]
	tmp2.sort()
	L.append(tmp2)
e = [0] * m
for i in range(m):
	x = 0
	for j in L[i]:
		x |= 1 << j
	e[i] = x
ans = 0
for i in range(1 << m):
	black = 0
	cnt = 0
	for j in range(m):
		if i >> j & 1:
			cnt += 1
			black |= e[j]
	cnt2 = 0
	for j in range(n - 1):
		if black >> j & 1:
			cnt2 += 1
	if cnt % 2:
		ans -= 1 << n - 1 - cnt2
	else:
		ans += 1 << n - 1 - cnt2
print(ans)


import sys
input = sys.stdin.readline
N = int(input())
graph = [[] for _ in range(N)]
Edges = [[None] * N for _ in range(N)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	graph[a - 1].append(b - 1)
	graph[b - 1].append(a - 1)
	Edges[a - 1][b - 1] = i
	Edges[b - 1][a - 1] = i

def dfs(p, L, checked, goal):
	if p == goal:
		return L
	checked[p] = True
	ok = False
	for np in graph[p]:
		if not checked[np]:
			L.append(np)
			retL = dfs(np, L, checked, goal)
			if retL:
				ok = True
				break
			L.pop()
	if ok:
		return retL
	else:
		return []
M = int(input())
Compression = []
for _ in range(M):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	path = dfs(a, [], [False] * N, b)
	bit = 0
	pre = a
	for p in path:
		bit += 1 << Edges[pre][p]
		pre = p
	Compression.append(bit)
ans = 0
for bitmask in range(1, 1 << M):
	whitebit = 0
	for i in range(M):
		if 1 << i & bitmask:
			whitebit |= Compression[i]
	p = 1
	for n in range(M):
		if bitmask & 1 << n:
			p ^= 1
	E = 1
	for m in range(N - 1):
		if whitebit & 1 << m == 0:
			E *= 2
	ans += E * (-1) ** p
print(2 ** (N - 1) - ans)


import sys
input = sys.stdin.readline

def popcnt(n):
	c = (n & 6148914691236517205) + (n >> 1 & 6148914691236517205)
	c = (c & 3689348814741910323) + (c >> 2 & 3689348814741910323)
	c = (c & 1085102592571150095) + (c >> 4 & 1085102592571150095)
	c = (c & 71777214294589695) + (c >> 8 & 71777214294589695)
	c = (c & 281470681808895) + (c >> 16 & 281470681808895)
	c = (c & 4294967295) + (c >> 32 & 4294967295)
	return c

def main():
	n = int(input())
	edge = [[] for i in range(n)]
	for _ in [0] * (n - 1):
		(a, b) = map(int, input().split())
		edge[a - 1].append(b - 1)
		edge[b - 1].append(a - 1)
	m = int(input())
	dg = 100
	uv = []
	for _ in [0] * m:
		(u, v) = map(int, input().split())
		uv.append(u * dg - dg + v - 1)
	par = [-2] * n
	root = 0
	par[0] = -1
	tank = [0]
	order = []
	orderIdx = [0] * n
	cnt = 0
	while tank:
		now = tank.pop()
		for nxt in edge[now]:
			if par[nxt] == -2:
				par[nxt] = now
				tank.append(nxt)
		order.append(now)
		orderIdx[now] = cnt
		cnt += 1
	res = pow(2, n - 1)
	bitOne = set()
	for i in range(m):
		bitOne.add(1 << i)
	dp = [0] * (1 << m)
	for i in range(1, 1 << m):
		pc = popcnt(i)
		if pc == 1:
			idx = (-i & i).bit_length() - 1
			(u, v) = (uv[idx] // dg, uv[idx] % dg)
			tmp = 0
			while u != v:
				if orderIdx[u] < orderIdx[v]:
					tmp |= 1 << v
					v = par[v]
				else:
					tmp |= 1 << u
					u = par[u]
			dp[i] = tmp
		else:
			dp[i] = dp[-i & i] | dp[-i & i ^ i]
		res += (-1) ** (pc % 2) * pow(2, n - 1 - popcnt(dp[i]))
	print(res)
main()


import sys
readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

def main():
	from collections import defaultdict, deque
	from itertools import combinations
	N = int(readline())
	edge = defaultdict(list)
	for i in range(N - 1):
		(a, b) = map(int, readline().split())
		edge[a - 1].append((b - 1, i))
		edge[b - 1].append((a - 1, i))

	def bfs(s, g):
		que = deque()
		que.append((s, []))
		visited = [False] * N
		visited[s] = True
		while que:
			(cur, path) = que.popleft()
			if cur == g:
				return set(path)
			for (nx, i) in edge[cur]:
				if not visited[nx]:
					new_path = path + [i]
					que.append((nx, new_path))
					visited[nx] = True
	M = int(readline())
	constraints = []
	for _ in range(M):
		(u, v) = map(int, readline().split())
		u -= 1
		v -= 1
		constraints.append(bfs(u, v))
	cnt = 0
	for i in range(1, M + 1):
		sign = 1 if i % 2 == 1 else -1
		for per in combinations(range(M), r=i):
			incl = set()
			for x in per:
				incl = incl.union(constraints[x])
			cnt += sign * 2 ** (N - 1 - len(incl))
	print(2 ** (N - 1) - cnt)
main()


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))

def bitcount32(n):
	n = (n >> 1 & 6148914691236517205) + (n & 6148914691236517205)
	n = (n >> 2 & 3689348814741910323) + (n & 3689348814741910323)
	n = (n >> 4 & 1085102592571150095) + (n & 1085102592571150095)
	n = (n >> 8 & 71777214294589695) + (n & 71777214294589695)
	n = (n >> 16 & 281470681808895) + (n & 281470681808895)
	n = (n >> 32 & 4294967295) + (n & 4294967295)
	return n
n = int(input())
links = [set() for _ in range(n)]
for i in range(n - 1):
	(a, b) = 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) = map(int, input().split())
	u -= 1
	v -= 1
	conditions.append(dfs(u, v, links))
ans = 0
for i in range(1 << m):
	cnd_cnt = bitcount32(i)
	bit = 0
	k = i
	while k:
		b = k & -k
		j = b.bit_length() - 1
		bit |= conditions[j]
		k ^= b
	free_link_cnt = n - 1 - bitcount32(bit)
	val = 2 ** free_link_cnt
	if cnd_cnt % 2:
		ans -= val
	else:
		ans += val
print(ans)


from collections import defaultdict, Counter
N = int(input())
ab = [[] for _ in range(N)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	ab[a - 1].append((b - 1, i))
	ab[b - 1].append((a - 1, i))
M = int(input())
uv = [[int(i) for i in input().split()] for _ in range(M)]
cnt = [set() for _ in range(M)]

def dfs(cur, pre, dest, i):
	if cur == dest:
		return True
	for (nex, j) in ab[cur]:
		if nex == pre:
			continue
		if dfs(nex, cur, dest, i):
			cnt[i].add(j)
			return True
	return False
for (i, (u, v)) in enumerate(uv):
	dfs(u - 1, -1, v - 1, i)
ret = 1 << N - 1
for i in range(1, 1 << M):
	sgn = 1
	s = set([])
	for j in range(M):
		if i & 1 << j:
			s |= cnt[j]
			sgn *= -1
	ret += sgn * (1 << N - 1 - len(s))
print(ret)


def main():
	import sys
	from collections import defaultdict, deque
	input = sys.stdin.readline

	class SegTree:

		def __init__(self, N):
			self.N0 = 2 ** (N - 1).bit_length()
			self.INF = 2 ** 31 - 1
			self.seg_min = [self.INF] * (2 * self.N0)

		def update(self, index, value):
			index += self.N0 - 1
			self.seg_min[index] = value
			while index > 0:
				index = (index - 1) // 2
				self.seg_min[index] = min(self.seg_min[index * 2 + 1], self.seg_min[index * 2 + 2])

		def query(self, first, last):
			first += self.N0 - 1
			last += self.N0 - 1
			ret = self.INF
			while first <= last:
				if not first & 1:
					ret = min(ret, self.seg_min[first])
				if last & 1:
					ret = min(ret, self.seg_min[last])
				first = first // 2
				last = last // 2 - 1
			return ret

	def EulerTour(adj, root):
		st = [root]
		ret = []
		seen = [0] * len(adj)
		par = [0] * len(adj)
		depth = [0] * len(adj)
		while st:
			v = st.pop()
			if seen[v]:
				ret.append(v)
				continue
			ret.append(v)
			seen[v] = 1
			if par[v] != 0:
				st.append(par[v])
			for u in adj[v]:
				if seen[u] == 0:
					st.append(u)
					par[u] = v
					depth[u] = depth[v] + 1
		return (ret, depth, par)

	def f(a, b):
		return a * 100 + b
	N = int(input())
	adj = [[] for _ in range(N + 1)]
	for _ in range(N - 1):
		(a, b) = map(int, input().split())
		adj[a].append(b)
		adj[b].append(a)
	(et, depth, par) = EulerTour(adj, 1)
	segtree = SegTree(len(et) + 1)
	left = [-1] * (N + 1)
	right = [-1] * (N + 1)
	for (i, v) in enumerate(et):
		segtree.update(i + 1, depth[v])
		if left[v] < 0:
			left[v] = i
		right[v] = i
	M = int(input())
	edge2cond = defaultdict(int)
	for j in range(M):
		(a, b) = map(int, input().split())
		lca_depth = segtree.query(min(left[a], left[b]) + 1, max(right[a], right[b]) + 1)
		prev = a
		for i in range(depth[a] - lca_depth):
			parent = par[prev]
			edge2cond[parent * 100 + prev] += 2 ** j
			prev = parent
		prev = b
		for i in range(depth[b] - lca_depth):
			parent = par[prev]
			edge2cond[parent * 100 + prev] += 2 ** j
			prev = parent
	que = deque()
	que.append(1)
	seen = [-1] * (N + 1)
	seen[1] = 0
	par = [0] * (N + 1)
	child = [[] for _ in range(N + 1)]
	seq = []
	while que:
		v = que.popleft()
		seq.append(v)
		for u in adj[v]:
			if seen[u] == -1:
				seen[u] = seen[v] + 1
				par[u] = v
				child[v].append(u)
				que.append(u)
	seq.reverse()
	dp = [[0] * 2 ** M for _ in range(N)]
	dp[0][0] = 1
	for (i, v) in enumerate(seq):
		if v == 1:
			continue
		for mask in range(2 ** M):
			u = par[v]
			mask_new = edge2cond[u * 100 + v]
			dp[i + 1][mask] += dp[i][mask]
			dp[i + 1][mask | mask_new] += dp[i][mask]
	print(dp[-1][-1])
main()


from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def I():
	return int(sys.stdin.readline())

def LS():
	return [list(x) for x in sys.stdin.readline().split()]

def S():
	res = list(sys.stdin.readline())
	if res[-1] == '\n':
		return res[:-1]
	return res

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]
sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():

	def dijkstra(s):
		d = [float('inf')] * n
		p = [s] * n
		d[s] = 0
		q = [(0, s)]
		while q:
			(dx, x) = heappop(q)
			nd = dx + 1
			for y in v[x]:
				if nd < d[y]:
					d[y] = nd
					p[y] = x
					heappush(q, (nd, y))
		path = [[i] for i in range(n)]
		for i in range(1, n):
			pre = path[i][-1]
			while pre != s:
				path[i].append(p[pre])
				pre = path[i][-1]
			path[i] = path[i][::-1]
		return (d, path)
	n = I()
	v = [[] for i in range(n)]
	e = defaultdict(lambda : 0)
	for i in range(n - 1):
		(a, b) = LI()
		a -= 1
		b -= 1
		v[a].append(b)
		v[b].append(a)
		e[a, b] = i
		e[b, a] = i
	d = [[0] * n for i in range(n)]
	path = [[None] * n for i in range(n)]
	for i in range(n):
		(D, p) = dijkstra(i)
		d[i] = [j for j in D]
		path[i] = [j for j in p]
	m = I()
	l = LIR(m)
	for i in range(m):
		l[i][0] -= 1
		l[i][1] -= 1
	ans = 0
	B = [0] * m
	for j in range(m):
		(x, y) = l[j]
		for k in range(len(path[x][y]) - 1):
			(a, b) = (path[x][y][k], path[x][y][k + 1])
			B[j] |= 1 << e[a, b]
	for b in range(1, 1 << m):
		f = bin(b).count('1')
		p = 0
		for j in range(m):
			if b & 1 << j:
				p |= B[j]
		s = bin(p).count('1')
		f &= 1
		k = 1 << n - s - 1
		if f:
			ans += k
		else:
			ans -= k
	print((1 << n - 1) - ans)
	return
solve()


from collections import deque

def main():
	n = int(input())
	edge = []
	edge_id = []
	for i in range(n):
		edge.append([])
		edge_id.append(dict())
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		edge[a - 1].append(b - 1)
		edge[b - 1].append(a - 1)
		edge_id[a - 1].update({b - 1: i})
		edge_id[b - 1].update({a - 1: i})
	m = int(input())
	uv = []
	for i in range(m):
		uv.append(list(map(int, input().split())))
	edge_mask = []
	for i in range(m):
		distance_from_u = []
		visited = []
		for j in range(n):
			distance_from_u.append(0)
			visited.append(False)
		que = deque()
		que.append([uv[i][0] - 1, 0])
		while len(que) > 0:
			(now, dist) = que.popleft()
			if visited[now]:
				continue
			visited[now] = True
			distance_from_u[now] = dist
			for x in edge[now]:
				if not visited[x]:
					que.append([x, dist + 1])
		next = uv[i][1] - 1
		edge_set = set()
		while distance_from_u[next] > 0:
			for x in edge[next]:
				if distance_from_u[x] < distance_from_u[next]:
					edge_set.add(edge_id[next][x])
					next = x
					break
		edge_mask.append(edge_set)
	dp_mask = []
	for i in range(n - 1):
		new_mask = 0
		for j in range(m):
			if i in edge_mask[j]:
				new_mask = new_mask | 1 << j
		dp_mask.append(new_mask)
	dp = []
	for i in range(n):
		dp.append([])
		for j in range(1 << m):
			dp[i].append(0)
	dp[0][0] = 1
	for i in range(n - 1):
		for j in range(1 << m):
			dp[i + 1][j] += dp[i][j]
			dp[i + 1][j | dp_mask[i]] += dp[i][j]
	ans = dp[n - 1][(1 << m) - 1]
	print(ans)
main()


printn = lambda x: print(x, end='')
inn = lambda : int(input())
inl = lambda : list(map(int, input().split()))
inm = lambda : map(int, input().split())
ins = lambda : input().strip()
DBG = True and False
BIG = 10 ** 18
R = 10 ** 9 + 7

def ddprint(x):
	if DBG:
		print(x)

def popcnt(x):
	c = 0
	while x > 0:
		c += x % 2
		x >>= 1
	return c

def dfs(u, v, p):
	global d
	d[u][v] = p
	for x in dst[v]:
		if u != x and d[u][x] == 0:
			p |= 1 << dst[v][x]
			dfs(u, x, p)
			p ^= 1 << dst[v][x]
n = inn()
dst = [{} for i in range(n + 1)]
for i in range(n - 1):
	(a, b) = inm()
	dst[a][b] = dst[b][a] = i
m = inn()
u = []
v = []
for i in range(m):
	(uu, vv) = inm()
	u.append(uu)
	v.append(vv)
if False and n == 2 and (m == 1):
	print(0)
	exit()
d = [[0] * (n + 1) for i in range(n + 1)]
for i in range(1, n + 1):
	dfs(i, i, 0)
dd = []
for i in range(m):
	dd.append(d[u[i]][v[i]])
ddprint(dst)
ddprint(d)
ddprint(u)
ddprint(v)
ddprint(dd)
y = 0
for i in range(1, 2 ** m):
	nbits = x = 0
	for j in range(m):
		if (i >> j) % 2 > 0:
			x |= dd[j]
			nbits += 1
	nsegs = popcnt(x)
	s = 2 * (nbits % 2) - 1
	y += s * 2 ** (n - 1 - nsegs)
print(2 ** (n - 1) - y)


from itertools import product as p
n = int(input())
s = [[] for i in range(n + 1)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	s[a].append([b, i])
	s[b].append([a, i])
m = int(input())
l = []
for i in range(m):
	(u, v) = map(int, input().split())
	a = [[] for i in range(n + 1)]
	a[u] = []
	q = [u]
	while q:
		t = q.pop(0)
		d = 0
		for (i, j) in s[t]:
			if a[i] == []:
				a[i] = a[t] + [j]
				q.append(i)
				if i == v:
					d = 1
					break
		if d == 1:
			break
	l.append(a[v])
for i in range(m):
	l[i] = set(l[i])
s = [0] * (m + 1)
for i in p([0, 1], repeat=m):
	d = set([])
	if sum(i) != 0:
		for j in range(m):
			if i[j]:
				d |= l[j]
		s[sum(i)] += pow(2, n - 1 - len(d))
l = 0
for i in range(1, m + 1):
	l += (-1) ** (i - 1) * s[i]
print(pow(2, n - 1) - l)


n = int(input())
adj = {a: [] for a in range(1, n + 1)}
for i in range(n - 1):
	(a, b) = map(int, input().split())
	adj[a].append((b, i))
	adj[b].append((a, i))
m = int(input())
ranges = [tuple(map(int, input().split())) for i in range(m)]

def findpath(u, v, parent=None):
	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)
			return p
	return None

def powerset(seq, bag):
	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)
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
	w = 2 ** (n - 1 - len(b))
	sign = -1 if l % 2 == 0 else 1
	white += sign * w
coloring = 2 ** (n - 1) - white
print(coloring)


import sys
from collections import defaultdict as dd
from itertools import combinations as combi
input = sys.stdin.readline
N = int(input())
el = []
e = dd(list)
for _ in range(N - 1):
	(u, v) = map(int, input().split())
	e[u].append(v)
	e[v].append(u)
	if u > v:
		(u, v) = (v, u)
	el.append((u, v))
vis = []

def dfs(s, t):
	global vis
	vis.append(s)
	if s == t:
		res = list(vis)
		vis.remove(s)
		return res
	res = []
	for x in e[s]:
		if x in vis:
			continue
		tt = dfs(x, t)
		if len(tt):
			res = tt
			break
	vis.remove(s)
	return res
M = int(input())
table = [[0] * (N - 1) for _ in range(M)]
for i in range(M):
	(u, v) = map(int, input().split())
	p = dfs(u, v)
	for j in range(len(p) - 1):
		for k in range(N - 1):
			x = p[j]
			y = p[j + 1]
			if x > y:
				(x, y) = (y, x)
			if el[k] == (x, y):
				table[i][k] = 1
				break
revtable = [0] * (N - 1)
for i in range(N - 1):
	for j in range(M):
		if table[j][i]:
			revtable[i] += pow(2, j)
dp = [0] * pow(2, M)
dp[0] = 1
for i in range(N - 1):
	for j in range(pow(2, M) - 1, -1, -1):
		dp[revtable[i] | j] += dp[j]
print(dp[-1])


import sys
input = sys.stdin.readline
n = int(input())
C = [list(map(int, input().split())) for i in range(n - 1)]
m = int(input())
U = [list(map(int, input().split())) for i in range(m)]
for i in range(n - 1):
	for j in range(2):
		C[i][j] -= 1
for i in range(m):
	for j in range(2):
		U[i][j] -= 1
B = [[0] * m for i in range(n - 1)]
M = [[] for i in range(n)]
for i in range(n - 1):
	M[C[i][0]].append([C[i][1], 1])
	M[C[i][1]].append([C[i][0], 1])
E = [[-1] * n for i in range(n)]
for i in range(n - 1):
	E[C[i][0]][C[i][1]] = i
	E[C[i][1]][C[i][0]] = i
F = [[] for i in range(m)]
import heapq
for mm in range(m):
	uu = U[mm][0]
	vv = U[mm][1]
	D = [float('inf')] * n
	P = [-1] * n
	D[uu] = 0
	V = [0] * n
	Q = []
	for v in range(n):
		heapq.heappush(Q, [D[v], v])
	le = len(Q)
	while le > 0:
		q = heapq.heappop(Q)
		u = q[1]
		du = q[0]
		if V[u] == 0:
			V[u] = 1
			le -= 1
			for i in range(len(M[u])):
				v = M[u][i][0]
				luv = M[u][i][1]
				if V[v] == 0:
					alt = du + luv
					if D[v] > alt:
						D[v] = alt
						P[v] = u
						heapq.heappush(Q, [alt, v])
	tt = vv
	while tt != uu:
		ss = P[tt]
		F[mm].append(E[ss][tt])
		tt = ss
for i in range(m):
	for j in F[i]:
		B[j][i] = 1
M2 = [1]
for i in range(30):
	M2.append(M2[-1] * 2)
BB = [[] for i in range(m + 1)]
for i in range(len(B)):
	BB[sum(B[i])].append(B[i][:])
CC = []
for i in range(len(BB)):
	for j in range(len(BB[i])):
		CC.append(BB[i][j])
B = CC
import itertools
G = [0] * 2 ** m
G[0] = 1
for i in range(n - 1):
	ii = 0
	K = []
	for j in range(m):
		if B[i][j] == 1:
			K.append(j)
		ii += B[i][j] * M2[m - 1 - j]
	GG = G[:]
	for jj in range(2 ** m):
		GG[jj | ii] += G[jj]
	G = GG[:]
print(G[-1])


import sys
input = sys.stdin.readline

def main():
	n = int(input())
	T = [[] for _ in range(n)]
	D = {}
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		a -= 1
		b -= 1
		T[a].append(b)
		T[b].append(a)
		D[a, b] = 1 << i
		D[b, a] = 1 << i
	m = int(input())

	def dfs(u, v):
		parent = [-1] * n
		seen = [False] * n
		stack = [u]
		seen[u] = True
		while stack:
			nv = stack[-1]
			if nv == v:
				return stack
			for i in T[nv]:
				if seen[i]:
					continue
				stack.append(i)
				seen[i] = True
				break
			else:
				stack.pop()
	E = [0] * m
	for i in range(m):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		edge = dfs(u, v)
		for j in range(len(edge) - 1):
			E[i] |= D[edge[j], edge[j + 1]]
	ans = 0
	for i in range(2 ** m):
		s = 0
		for j in range(m):
			if i >> j & 1:
				s |= E[j]
		cnt = bin(i).count('1') % 2
		ans += (-1) ** cnt * 2 ** (n - 1 - bin(s).count('1'))
	print(ans)
main()


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop, heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10 ** 9 + 7
inf = float('inf')

def I():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def dfs(s, g, p):
	global tmp
	if s == g:
		tmp = []
		return True
	for (v, i) in edge[s]:
		if v == p:
			continue
		if dfs(v, g, s):
			tmp.append(i)
			return True
	return False
n = I()
edge = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = LI()
	a -= 1
	b -= 1
	edge[a].append((b, i))
	edge[b].append((a, i))
m = I()
lst = []
tmp = []
for _ in range(m):
	(u, v) = LI()
	u -= 1
	v -= 1
	dfs(u, v, -1)
	lst.append(tmp)
e = [0] * m
for i in range(m):
	x = 0
	for j in lst[i]:
		x |= 1 << j
	e[i] = x
ans = 0
for i in range(1 << m):
	black = 0
	cnt = 0
	for j in range(m):
		if i >> j & 1:
			cnt += 1
			black |= e[j]
	cnt2 = 0
	for j in range(n - 1):
		if black >> j & 1:
			cnt2 += 1
	if cnt % 2:
		ans -= 1 << n - 1 - cnt2
	else:
		ans += 1 << n - 1 - cnt2
print(ans)


import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():
	N = int(input())
	G = [[] for _ in range(N)]
	for i in range(N - 1):
		(a, b) = map(int, input().split())
		a -= 1
		b -= 1
		G[a].append((b, i))
		G[b].append((a, i))
	between = [[set() for _ in range(N)] for _ in range(N)]
	for i in range(N):
		stack = [(i, [])]
		while stack:
			(v, before) = stack.pop()
			between[i][v] = set(before)
			for (e, j) in G[v]:
				if e == i or len(between[i][e]) >= 1:
					continue
				between[i][e] = set(before + [j])
				stack.append((e, before + [j]))
	M = int(input())
	condition = [tuple(map(int, input().split())) for _ in range(M)]
	condition = [(a - 1, b - 1) for (a, b) in condition]
	ans = 0
	for bit in range(1 << M):
		ret = set()
		cnt = 0
		for i in range(M):
			if bit >> i & 1:
				cnt += 1
				ret |= between[condition[i][0]][condition[i][1]]
		free = N - len(ret) - 1
		if cnt % 2 == 0:
			ans += pow(2, free)
		else:
			ans -= pow(2, free)
	print(ans)
main()


import sys
from collections import defaultdict
readline = sys.stdin.readline
(N,) = map(int, readline().split())

def con(ll, E):
	r = 0
	for (u, v) in zip(ll, ll[1:]):
		(u, v) = sorted([u, v])
		r += 1 << E[u, v]
	return r

def process():
	G = [[] for _ in range(N + 1)]
	E = dict()
	for i in range(N - 1):
		(a, b) = sorted(map(int, readline().split()))
		G[a].append(b)
		G[b].append(a)
		E[a, b] = i
	(M,) = map(int, readline().split())
	qes = dict()
	for _ in range(M):
		(u, v) = sorted(map(int, readline().split()))
		if u not in qes:
			qes[u] = list()
		qes[u].append(v)
	dep = []
	for i in qes:
		ms = qes[i]
		path = []
		stack = [i]
		vs = set([i])
		while stack:
			v = stack.pop()
			if v > 0:
				vs.add(v)
				path.append(v)
				for u in G[v]:
					if u in vs:
						continue
					if u in ms:
						dep.append(con(path + [u], E))
					stack += [-v, u]
			else:
				path.pop()
	r = 0
	for i in range(1, 2 ** M):
		t = 0
		ns = 0
		for j in range(M):
			if i % 2:
				ns = ns | dep[j]
				t += 1
			i = i >> 1
		xx = (1 if t % 2 else -1) * 2 ** (N - 1 - bin(ns).count('1'))
		r += xx
	print(2 ** (N - 1) - r)
process()


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)


import sys
input = sys.stdin.readline
n = int(input())
Edge = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	Edge[a - 1].append((b - 1, i))
	Edge[b - 1].append((a - 1, i))
m = int(input())
M = []
for i in range(m):
	M.append(tuple(map(int, input().split())))
inf = float('inf')
path = [-1] * n
path[0] = 0
stack = [0]
while stack:
	cur = stack.pop()
	for (next, num) in Edge[cur]:
		if path[next] == -1:
			path[next] = path[cur] | 1 << num
			stack.append(next)

def popcount(x):
	return bin(x).count('1')
passing = []
for (u, v) in M:
	passing.append(path[u - 1] ^ path[v - 1])
ans = 2 ** (n - 1)
for i in range(1, 2 ** m):
	i_ct = popcount(i)
	condition = 0
	for j in range(m):
		if i & 1 << j:
			condition = condition | passing[j]
	cond_ct = popcount(condition)
	ans += pow(-1, i_ct) * pow(2, n - 1 - cond_ct)
print(ans)


import sys
INF = float('inf')
from collections import defaultdict
from collections import deque
import math

class Graph(object):

	def __init__(self, N):
		self.N = N
		self.E = defaultdict(list)

	def add_edge(self, f, t, w=1):
		self.E[f].append((t, w))
		self.E[t].append((f, w))

class LCA(object):

	def __init__(self, g: Graph, root: int=0):
		self.construct(g, root)

	def construct(self, g: Graph, root=0):
		self.N = g.N
		self.LN = len(bin(g.N).lstrip('-0b'))
		par = [INF] * self.N
		self.depth = [INF] * self.N
		que = deque()
		que.append([root, 0, None])
		while len(que) > 0:
			(curr, dep, pre) = que.popleft()
			par[curr] = pre
			self.depth[curr] = dep
			for (n, w) in g.E[curr]:
				if n != pre:
					que.append([n, dep + w, curr])
		self.anc = [par]
		for i in range(self.LN):
			buf = [None] * self.N
			for j in range(self.N):
				if self.anc[i][j] == None:
					continue
				buf[j] = self.anc[i][self.anc[i][j]]
			self.anc.append(buf)
		return

	def query(self, u: int, v: int):
		dd = self.depth[v] - self.depth[u]
		if dd < 0:
			(u, v) = (v, u)
			dd = -dd
		for k in range(self.LN):
			if dd & 1:
				v = self.anc[k][v]
			dd >>= 1
		if u == v:
			return u
		for k in range(self.LN - 1, -1, -1):
			pu = self.anc[k][u]
			pv = self.anc[k][v]
			if pu != pv:
				u = pu
				v = pv
		return self.anc[0][u]

def bit_sum(n):
	return bin(n).count('1')

def solve(N: int, a: 'List[int]', b: 'List[int]', M: int, u: 'List[int]', v: 'List[int]'):
	g = Graph(N)
	for (X, Y) in zip(a, b):
		g.add_edge(X - 1, Y - 1)
	lca = LCA(g)
	paths = []
	for j in range(M):
		path = 0
		a1 = u[j] - 1
		a2 = v[j] - 1
		p = lca.query(a1, a2)
		while a1 != p:
			path |= 1 << a1 - 1
			a1 = lca.anc[0][a1]
		while a2 != p:
			path |= 1 << a2 - 1
			a2 = lca.anc[0][a2]
		paths.append(path)
	ans = 2 ** (N - 1)
	for p in range(1, 1 << M):
		spider_net = 0
		strp = bin(p).lstrip('0b')
		for (i, c) in enumerate(strp[::-1]):
			if c == '1':
				spider_net |= paths[i]
		C = bit_sum(spider_net)
		if bit_sum(p) % 2 == 1:
			ans -= 2 ** (N - 1 - C)
		else:
			ans += 2 ** (N - 1 - C)
	print(ans)
	return

def main():

	def iterate_tokens():
		for line in sys.stdin:
			for word in line.split():
				yield word
	tokens = iterate_tokens()
	N = int(next(tokens))
	a = [int()] * (N - 1)
	b = [int()] * (N - 1)
	for i in range(N - 1):
		a[i] = int(next(tokens))
		b[i] = int(next(tokens))
	M = int(next(tokens))
	u = [int()] * M
	v = [int()] * M
	for i in range(M):
		u[i] = int(next(tokens))
		v[i] = int(next(tokens))
	solve(N, a, b, M, u, v)
main()


def examA():
	N = I()
	L = LI()
	L.sort()
	if sum(L) <= L[-1] * 2:
		print('No')
	else:
		print('Yes')
	return

def examB():
	(N, M) = LI()
	A = [LI() for _ in range(N)]
	A.sort(key=lambda x: x[0])
	ans = 0
	for (a, b) in A:
		if M <= b:
			ans += a * M
			break
		ans += a * b
		M -= b
	print(ans)
	return

def examC():
	N = I()
	S = [SI() for _ in range(N)]
	D = defaultdict(int)
	for s in S:
		cur = []
		for (i, j) in Counter(s).items():
			cur.append((i, j))
		cur.sort()
		cur = tuple(cur)
		D[cur] += 1
	ans = 0
	for d in D.values():
		ans += (d - 1) * d // 2
	print(ans)
	return

def examD():
	(N, K) = LI()
	A = LI()
	S = [0] * (N + 1)
	for i in range(N):
		S[i + 1] = S[i] + A[i]
	ans = 0
	for i in range(N):
		l = i - 1
		r = N
		if S[-1] - S[i] < K:
			break
		while r - l > 1:
			now = (l + r) // 2
			if S[now] - S[i] < K:
				l = now
			else:
				r = now
		ans += N - r + 1
	print(ans)
	return

def examE():

	class SegmentTree:

		def __init__(self, n, ele, segfun):
			self.ide_ele = ele
			self.segfun = segfun
			self.n = n
			self.N0 = 1 << n.bit_length()
			self.data = [self.ide_ele] * (self.N0 * 2)

		def update_add(self, l, r, val):
			l += self.N0
			r += self.N0
			while l < r:
				if l & 1:
					self.data[l] += val
					l += 1
				if r & 1:
					self.data[r - 1] += val
					r -= 1
				l //= 2
				r //= 2

		def update(self, l, r, val):
			l += self.N0
			r += self.N0
			while l < r:
				if l & 1:
					self.data[l] = self.segfun(self.data[l], val)
					l += 1
				if r & 1:
					self.data[r - 1] = self.segfun(self.data[r - 1], val)
					r -= 1
				l //= 2
				r //= 2

		def query(self, i):
			i += len(self.data) // 2
			ret = self.data[i]
			while i > 0:
				i //= 2
				ret = self.segfun(ret, self.data[i])
			return ret
	(N, D, A) = LI()
	X = [LI() for _ in range(N)]
	X.sort()
	L = [0] * N
	for i in range(N):
		L[i] = X[i][0]
	S = SegmentTree(N, 0, lambda a, b: a + b)
	ans = 0
	for (i, [x, h]) in enumerate(X):
		H = h - S.query(i)
		if H <= 0:
			continue
		ne = bisect.bisect_right(L, x + 2 * D)
		need = (H - 1) // A + 1
		S.update(i, ne, need * A)
		ans += need
	print(ans)
	return

def examF():
	N = I()
	V = [[] for _ in range(N)]
	Num_edge = {}
	for i in range(N - 1):
		(a, b) = LI()
		a -= 1
		b -= 1
		V[a].append(b)
		V[b].append(a)
		Num_edge[a, b] = i
		Num_edge[b, a] = i

	def dfs(S, s, p, g):
		now = s
		neS = []
		if now == g:
			return S
		for ne in V[now]:
			if ne == p:
				continue
			neS = dfs(S + (1 << Num_edge[now, ne]), ne, now, g)
			if neS:
				return neS
		return
	M = I()
	Q = [0] * M
	for i in range(M):
		(a, b) = LI()
		a -= 1
		b -= 1
		Q[i] = dfs(0, a, -1, b)
	ans = pow(2, N - 1)
	loop = 2 ** M
	for i in range(1, loop):
		cur = 0
		num = 0
		for k in range(M):
			if i & 1 << k > 0:
				num += 1
				cur |= Q[k]
		if num % 2 == 1:
			ans -= 1 << N - 1 - bin(cur).count('1')
		else:
			ans += 1 << N - 1 - bin(cur).count('1')
	print(ans)
	return
import sys, bisect, itertools, heapq, math, random
from copy import deepcopy
from heapq import heappop, heappush, heapify
from collections import Counter, defaultdict, deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def I():
	return int(readline())

def LI():
	return list(map(int, readline().split()))

def LSI():
	return list(map(str, sys.stdin.readline().split()))

def LS():
	return sys.stdin.readline().split()

def SI():
	return sys.stdin.readline().strip()
global mod, mod2, inf, alphabet, _ep
mod = 10 ** 9 + 7
mod2 = 998244353
inf = 10 ** 18
_ep = 10 ** (-12)
alphabet = [chr(ord('a') + i) for i in range(26)]
sys.setrecursionlimit(10 ** 7)
examF()


import sys
input = sys.stdin.readline

def I():
	return int(input())

def MI():
	return map(int, input().split())

def LI():
	return list(map(int, input().split()))

def main():
	mod = 10 ** 9 + 7
	N = I()
	adj = [[] for _ in range(N)]
	from collections import defaultdict
	dd = defaultdict(int)
	for i in range(N - 1):
		(a, b) = MI()
		a -= 1
		b -= 1
		if a > b:
			(a, b) = (b, a)
		adj[a].append(b)
		adj[b].append(a)
		dd[a, b] = 1 << i

	def popcount(x):
		x = x - (x >> 1 & 6148914691236517205)
		x = (x & 3689348814741910323) + (x >> 2 & 3689348814741910323)
		x = x + (x >> 4) & 1085102592571150095
		x = x + (x >> 8)
		x = x + (x >> 16)
		x = x + (x >> 32)
		return x & 127

	def EulerTour(n, X, i0):
		P = [-1] * n
		st = [~i0, i0]
		ct = -1
		ET = []
		ET1 = [0] * n
		ET2 = [0] * n
		DE = [0] * n
		de = -1
		while st:
			i = st.pop()
			if i < 0:
				ct += 1
				ET.append(P[~i])
				ET2[~i] = ct
				de -= 1
				continue
			if i >= 0:
				ET.append(i)
				ct += 1
				if ET1[i] == 0:
					ET1[i] = ct
				de += 1
				DE[i] = de
			for a in X[i][::-1]:
				if a != P[i]:
					P[a] = i
					for k in range(len(X[a])):
						if X[a][k] == i:
							del X[a][k]
							break
					st.append(~a)
					st.append(a)
		return (ET, ET1, ET2, DE, P)
	(S, F, Frev, depth, P) = EulerTour(N, adj, 0)
	INF = (N, None)
	M = 2 * N
	M0 = 2 ** (M - 1).bit_length()
	data = [INF] * (2 * M0)
	for (i, v) in enumerate(S):
		data[M0 - 1 + i] = (depth[v], i)
	for i in range(M0 - 2, -1, -1):
		data[i] = min(data[2 * i + 1], data[2 * i + 2])

	def _query(a, b):
		yield INF
		a += M0
		b += M0
		while a < b:
			if b & 1:
				b -= 1
				yield data[b - 1]
			if a & 1:
				yield data[a - 1]
				a += 1
			a >>= 1
			b >>= 1

	def query(u, v):
		fu = F[u]
		fv = F[v]
		if fu > fv:
			(fu, fv) = (fv, fu)
		return S[min(_query(fu, fv + 1))[1]]

	def make_route(u, v):
		e = 0
		lca = query(u, v)
		for i in range(2):
			if i == 1:
				v = u
			while v != lca:
				p = P[v]
				if p < v:
					e += dd[p, v]
				else:
					e += dd[v, p]
				v = p
		return e
	M = I()
	U = [0] * M
	V = [0] * M
	E = []
	for i in range(M):
		(U[i], V[i]) = MI()
		U[i] -= 1
		V[i] -= 1
		E.append(make_route(U[i], V[i]))
	ans = 0
	for i in range(pow(2, M)):
		e = 0
		for j in range(M):
			if i >> j & 1:
				e2 = E[j]
				e = e | e2
		temp = pow(2, N - 1 - popcount(e))
		if popcount(i) % 2 == 0:
			ans += temp
		else:
			ans -= temp
	print(ans)
main()