Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

from collections import deque

class Node:
    def __init__(self, idx):
        self.idx = idx
        self.a = []


n, x, y = map(int, input().split())
nodes = []

for i in range(n):
    node = Node(i+1)
    nodes.append(node)

for i in range(n-1):
    cur = nodes[i]
    next = nodes[i+1]

    cur.a.append(next)
    next.a.append(cur)

X = nodes[x-1]
Y = nodes[y-1]
X.a.append(Y)
Y.a.append(X)

for k in range(1, n):
    temp = 0
    for i in range(n):
        node = nodes[i]
        q = deque()
        q.append((node, 0))
        done = set()

        while q:
            t = q.popleft()
            node, d = t[0], t[1]
            if d > k:
                break

            if node.idx not in done:
                done.add(node.idx)
                if d == k:
                    temp += 1
                for adj in node.a:
                    q.append((adj, d+1))
    print(temp//2)

### FIXED CODE ###

from collections import deque

class Node:
    def __init__(self, idx):
        self.idx = idx
        self.a = []


n, x, y = map(int, input().split())
nodes = []

for i in range(n):
    node = Node(i+1)
    nodes.append(node)

for i in range(n-1):
    cur = nodes[i]
    next = nodes[i+1]

    cur.a.append(next)
    next.a.append(cur)

X = nodes[x-1]
Y = nodes[y-1]
X.a.append(Y)
Y.a.append(X)
dp = [[None] * (n+1) for _ in range(n+1)]

for i in range(n):
    node = nodes[i]
    q = deque()
    q.append((node, 0))
    done = set()

    while q:
        t = q.popleft()
        node, d = t[0], t[1]

        if node.idx not in done:
            dp[i + 1][node.idx] = d
            done.add(node.idx)
            for adj in node.a:
                q.append((adj, d + 1))

# for i in range(1, n+1):
#     print(dp[i])

m = {}

for i in range(1, n + 1):
    for j in range(1, n + 1):
        dis = dp[i][j]
        if dis in m:
            m[dis] += 1
        else:
            m[dis] = 1

for k in range(1, n):
    if k in m:
        print(m[k] // 2)
    else:
        print(0)
### BUGGY CODE ###

H, W = map(int, input().split())

grid = [[] for h in range(H)]

for h in range(H):
    grid[h] = list(input())

L = [[0] * W for h in range(H)]
U = [[0] * W for h in range(H)]
R = [[0] * W for h in range(H)]
D = [[0] * W for h in range(H)]

for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            L[h][w] = 0
            U[h][w] = 0
        else:
            if w == 0:
                L[h][w] = 1
            else:
                L[h][w] = L[h][w - 1] + 1

            if h == 0:
                U[h][w] = 1
            else:
                U[h][w] = U[h - 1][w] + 1

    for w in range(W - 1, -1, -1):
        if grid[h][w] == '#':
            R[h][w] = 0
        else:
            if w == W - 1:
                R[h][w] = 1
            else:
                R[h][w] = R[h][w + 1] + 1

for h in range(H - 1, -1, -1):
    for w in range(W):
        if grid[h][w] == '#':
            D[h][w] = 0
        else:
            if h == H - 1:
                D[h][w] = 1
            else:
                D[h][w] = D[h + 1][w] + 1

import numpy as np
print(max((np.array(L) + np.array(R) + np.array(U) + np.array(D) - 3).ravel()))

### FIXED CODE ###

import numpy as np

H, W = map(int, input().split())
S = np.array([list(input()) for _ in range(H)]) == '.'

D = np.zeros((H, W), dtype=int)
U = np.zeros((H, W), dtype=int)
L = np.zeros((H, W), dtype=int)
R = np.zeros((H, W), dtype=int)

for h in range(H):
    U[h] = (U[h - 1] + 1) * S[h]
    D[-h - 1] = (D[-h] + 1) * S[-h - 1]
for w in range(W):
    L[:, w] = (L[:, w - 1] + 1) * S[:, w]
    R[:, -w - 1] = (R[:, -w] + 1) * S[:, -w - 1]
print(np.max(U + D + L + R) - 3)
### BUGGY CODE ###

##########
import math
#import numpy as np
from itertools import product as prod
#from itertools import permutations as perm
#from itertools import combinations as comb
#from itertools import combinations_with_replacement as combr

ii = lambda:int(input())
li = lambda:list(map(int,input().split()))
##########
def main(k):
    res = 0
    for item in prod(range(1,k+1),repeat=3):
        res += calc(item)
    return res
        
def calc(item):
    a,b,c = item
    return math.gcd(a,math.gcd(b,c))

k = ii()
print(main(k))

### FIXED CODE ###

##########
import math
#import numpy as np
from itertools import product as prod
#from itertools import permutations as perm
#from itertools import combinations as comb
#from itertools import combinations_with_replacement as combr

ii = lambda:int(input())
li = lambda:list(map(int,input().split()))
##########
def main(k):
    res = 0
    for item in prod(range(1,k+1),repeat=3):
        res += calc(item)
    return res
        
def calc(item):
    a,b,c = item
    return math.gcd(a,math.gcd(b,c))

k = ii()
print(main(k))
### BUGGY CODE ###

#abc164-4
s = input()

counts = [0]*2019#modの値と個数を記録するリスト
d = 0
counts[0] += 1
for i in range(0,len(s)):
    d += int(s[-i-1])*(10**i)
    #print(d, d%2019)
    counts[d % 2019] += 1
#print(counts)
sumcount = 0
for m in counts:
    sumcount += m*(m-1)/2
print(int(sumcount))
#TLE

### FIXED CODE ###

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力
### BUGGY CODE ###

import bisect,copy,heapq,string
from collections import *
from math import *
from itertools import *
import sys
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n, m = MAP()
s = input()
t = input()
l = n*m//gcd(n, m)

for i in range(l):
        if (n*i) % l == (m*i) % l == 0 and s[n*i//l] != t[m*i//l]:
                print(-1)
                exit()
print(l)

### FIXED CODE ###

import bisect,copy,heapq,string
from collections import *
from math import *
from itertools import *
import sys
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n, m = MAP()
s = input()
t = input()
k = gcd(n,m)
l = n*m//k

for i in range(0,l,l//k):
        if (n*i) % l == (m*i) % l == 0 and s[n*i//l] != t[m*i//l]:
                print(-1)
                exit()
print(l)
### BUGGY CODE ###

# 4 3
# 1 2
# 2 3
# 2 4
# 2 10
# 1 100
# 3 1

n, q = list(map(int, input().split(" ")))
a = []
b = []
for i in range(n-1):
    j, k = list(map(int, input().split(" ")))
    a.append(j)
    b.append(k)

p = []
x = []
for i in range(q):
    j, k = list(map(int, input().split(" ")))
    p.append(j)
    x.append(k)


class Node:
    def __init__(self, id):
        self.id = id
        self.counter = 0
        self.linked = []

    def add_node(self, node):
        self.linked.append(node)

    def add_count(self, count):
        self.counter += count


# make node
tree = []
for i in range(n):
    tree.append(Node(i))

for j, k in zip(a, b):
    tree[j-1].add_node(tree[k-1])

for j, k in zip(p, x):
    tree[j-1].add_count(k)

# traverse
for i in tree:
    for j in i.linked:
        j.counter += i.counter

m = []
for i in tree:
    m.append(i.counter)

print(" ".join(map(str, m)))






### FIXED CODE ###

n, q = list(map(int, input().split(" ")))
a = []
b = []
tree = []

class Node:
    def __init__(self, id):
        self.id = id
        self.counter = 0
        self.linked = []

    def add_node(self, node):
        self.linked.append(node)

    def add_count(self, count):
        self.counter += count

# make node
for i in range(n):
    tree.append(Node(i))

# add node
for i in range(n-1):
    j, k = list(map(int, input().split(" ")))
    tree[j-1].add_node(tree[k-1])

# add count
for i in range(q):
    j, k = list(map(int, input().split(" ")))
    tree[j-1].add_count(k)

# traverse
for i in tree:
    for j in i.linked:
        j.counter += i.counter

m = []
for i in tree:
    m.append(i.counter)

print(" ".join(map(str, m)))
### BUGGY CODE ###

s = input()
ans = 0

for i in range(len(s)):
    if s[i] == "A":
        a = i
        for j in range(len(s)):
            if s[j] == "Z":
                z = j+1
                if ans < len(s[a:z]):
                    ans = len(s[a:z])
print(ans)


### FIXED CODE ###

s = input()

for i in range(len(s)):
    if s[i] == "A":
        a = i
        break
for i in range(len(s)):
    if s[i] == "Z":
        z = i+1

print(len(s[a:z]))
### BUGGY CODE ###

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

def nC2(n):
    return n * (n - 1) // 2

d = {i:a.count(i) for i in set(a)}

s = sum([nC2(d[i]) for i in set(a)])

for i in a:
    print(s + (1 - d[i]))

### FIXED CODE ###

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

def nC2(n):
    return n * (n - 1) // 2

d = {}
for i in a:
    if i in d.keys():
        d[i] += 1
    else:
        d[i] = 1
    
s = sum([nC2(i) for i in d.values()])

for i in a:
    print(s + (1 - d[i]))
### BUGGY CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[2]:


import math


# In[19]:


N = int(input())


# In[20]:


for i in range(1,N+1):
#     print("f(%s)"%i)
    ans = 0
    for x in range(1,int(math.sqrt(i))+1):
        if i - x**2 - x > 0:
            for y in range(1,int(math.sqrt(i-x**2-x))+1):
                if i - x**2 - x - y**2 - y - x*y > 0:
                    for z in range(1,int(math.sqrt(i-x**2-x-y**2-y-x*y)+1)):
                        if x**2 + y**2 + z**2 + x*y + y*z + z*x == i:
#                             print(x,y,z)
                            ans += 1
    print(ans)


# In[ ]:






### FIXED CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[23]:


import math
import itertools


# In[27]:


N = int(input())


# In[28]:


for i in range(1,N+1):
#     print("f(%s)"%i)
    ans = 0
    for x in range(1,int(math.sqrt(i))+1):
        if i - x**2 - x > 0:
            for y in range(x,int(math.sqrt(i-x**2-x))+1):
                if i - x**2 - x - y**2 - y - x*y > 0:
                    for z in range(y,int(math.sqrt(i-x**2-x-y**2-y-x*y)+1)):
                        if x**2 + y**2 + z**2 + x*y + y*z + z*x == i:
                            if x==y and y==z:
                                ans += 1
                            elif x==y:
                                ans += 3
                            elif y==z:
                                ans += 3
                            else:
                                ans += 6
    print(ans)


# In[ ]:
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
 
count = 0
while True:
    for i in range(n):
        if a[i] % 2 == 0:
            a[i] /= 2
        else:
            print(count)
            break
    count += 1
print(count)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
 
count = 0
while True:
    for i in range(n):
        if a[i] % 2 == 0:
            a[i] = a[i]//2
        else:
            print(count)
            exit()
    count += 1
print(count)
### BUGGY CODE ###

import sys
import math
from collections import defaultdict
from collections import deque
from itertools import combinations
import bisect

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    N, MA, MB = NMI()
    D = []
    for _ in range(N):
        a, b, c = NMI()
        t = a*MB - b*MA
        D.append((t, c))
    D.sort()

    D1 = D[:N//2]
    D2 = D[N//2:]
    ld1 = len(D1)
    ld2 = len(D2)

    S1 = defaultdict(lambda: 10**5)
    for case in range(2**ld1):
        if case == 0: continue
        s, c = 0, 0
        for i in range(ld1):
            if (case>>i)&1:
                s += D1[i][0]
                c += D1[i][1]
        S1[s] = min(S1[s], c)

    S2 = defaultdict(lambda: 10**5)
    for case in range(2 ** ld2):
        if case == 0: continue
        s, c = 0, 0
        for i in range(ld2):
            if (case >> i) & 1:
                s += D2[i][0]
                c += D2[i][1]
        S2[s] = min(S2[s], c)

    ans = 10**5
    for s, c in list(S1.items()):
        ans = min(ans, c + S2[-s])
    ans = min(ans, S1[0], S2[0])
    if ans >= 10**5:
        print(-1)
    else:
        print(ans)



if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
import math
from collections import defaultdict
from collections import deque
from itertools import combinations
import bisect

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    N, MA, MB = NMI()
    D = []
    for _ in range(N):
        a, b, c = NMI()
        t = a*MB - b*MA
        D.append((t, c))
    D.sort()

    D1 = D[:N//2]
    D2 = D[N//2:]
    ld1 = len(D1)
    ld2 = len(D2)

    S1 = defaultdict(lambda: 10**5)
    for case in range(2**ld1):
        if case == 0: continue
        s, c = 0, 0
        for i in range(ld1):
            if (case>>i)&1:
                s += D1[i][0]
                c += D1[i][1]
        S1[s] = min(S1[s], c)

    S2 = defaultdict(lambda: 10**5)
    for case in range(2 ** ld2):
        if case == 0: continue
        s, c = 0, 0
        for i in range(ld2):
            if (case >> i) & 1:
                s += D2[i][0]
                c += D2[i][1]
        S2[s] = min(S2[s], c)

    ans = 10**5
    for s, c in list(S1.items()):
        ans = min(ans, c + S2[-s])
    ans = min(ans, S1[0], S2[0])
    if ans >= 10**5:
        print(-1)
    else:
        print(ans)



if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys
import numpy as np

if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC
    cc = CC('my_module')

    @cc.export('solve', 'i4(i4, i4[:])')
    def solve(N, P):
        minDist = np.ones((N, N), dtype=np.int32)
        isFilled = np.ones((N, N), dtype=np.int32)

        for h in range(N):
            for w in range(N):
                minDist[h][w] = min(h, N - h - 1, w, N - w - 1)

        ans = 0
        for p in P:
            h, w = divmod(p, N)
            ans += minDist[h][w]
            isFilled[h][w] = False

            st = [[h, w]]
            while st:
                h, w = st.pop()
                dist = minDist[h][w] + isFilled[h][w]

                if h + 1 < N and minDist[h + 1][w] > dist:
                    minDist[h + 1][w] = dist
                    st.append([h + 1, w])
                if h - 1 >= 0 and minDist[h - 1][w] > dist:
                    minDist[h - 1][w] = dist
                    st.append([h - 1, w])
                if w + 1 < N and minDist[h][w + 1] > dist:
                    minDist[h][w + 1] = dist
                    st.append([h, w + 1])
                if w - 1 < N and minDist[h][w - 1] > dist:
                    minDist[h][w - 1] = dist
                    st.append([h, w - 1])
        return ans

    cc.compile()
    exit(0)

from my_module import solve

N = int(input())
P = np.asarray(list(map(lambda a: int(a) - 1, input().split())), dtype=np.int32)

print(solve(N, P))


### FIXED CODE ###

import sys
import numpy as np

if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC
    cc = CC('my_module')

    @cc.export('solve', 'i4(i4, i4[:])')
    def solve(N, P):
        minDist = np.ones((N, N), dtype=np.int32)
        isFilled = np.ones((N, N), dtype=np.int32)

        for h in range(N):
            for w in range(N):
                minDist[h][w] = min(h, N - h - 1, w, N - w - 1)

        ans = 0
        for p in P:
            h, w = divmod(p, N)
            ans += minDist[h][w]
            isFilled[h][w] = False

            st = [(h, w)]
            while st:
                h, w = st.pop()
                dist = minDist[h][w] + isFilled[h][w]

                if h + 1 < N and minDist[h + 1][w] > dist:
                    minDist[h + 1][w] = dist
                    st.append((h + 1, w))
                if h - 1 >= 0 and minDist[h - 1][w] > dist:
                    minDist[h - 1][w] = dist
                    st.append((h - 1, w))
                if w + 1 < N and minDist[h][w + 1] > dist:
                    minDist[h][w + 1] = dist
                    st.append((h, w + 1))
                if w - 1 < N and minDist[h][w - 1] > dist:
                    minDist[h][w - 1] = dist
                    st.append((h, w - 1))
        return ans

    cc.compile()
    exit(0)

from my_module import solve

N = int(input())
P = np.asarray(list(map(lambda a: int(a) - 1, input().split())), dtype=np.int32)

print(solve(N, P))
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input() 
data = [ tuple(map(int, input().split())) for _ in range(Q) ] 

counter = [0 for _ in range(Q)]
index = -1
while True:
	index = S.find("AC", index+1)

	if index == -1:
		break
	
	for i, (l, r ) in enumerate(data):
		if l-1 <= index < r-1:
			counter[i] += 1


for res in counter:
	print(res)


### FIXED CODE ###

N, Q = map(int, input().split())
S = input() 

t = [0] * (N + 1) 

for i in range(N):
	t[i+1] = t[i] + (1 if S[i:i+2] == "AC" else 0)

for i in range(Q):
	l, r = map(int, input().split())
	print(t[r-1] - t[l-1])
### BUGGY CODE ###

K,S=map(int,input().split())
if 2<=K<=2500 and 0<=S<=3*K:
    Ks=[]
    wa=[]
    for i in range(K+1):
        Ks.append(i)
    X,Y,Z =Ks,Ks,Ks
    for x in X:
        if x<=S:
            X_=[]
            X_.append(x)
            for y in Y:
                if y<=S:
                    X_Y_=[]
                    X_Y_=list(X_)
                    X_Y_.append(y)
                    for z in Z:
                        if z<=S:
                            X_Y_Z_=list(X_Y_)
                            X_Y_Z_.append(z) 
                            wa_=sum(X_Y_Z_)
                            wa.append(wa_)
    print(len([c for c in wa if c==S]))

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
K,S=map(int,input().split())
count=0
for x in range(K+1):
    for y in range(K+1):
        if S-(x+y)>=0 and S-(x+y)<=K: count+=1
print(count)
### BUGGY CODE ###

from copy import deepcopy


def translate(r, c):
    return r * (C + 1) + c


R, C, K = map(int, input().split())
rcv = [list(map(int, input().split())) for _ in range(K)]
N = (R + 1) * (C + 1)

d = [[] for _ in range(R + 1)]
for r, c, v in rcv:
    d[r].append([c, v])

for r in range(R + 1):
    d[r].sort()

dp = [[0] * (C + 1) for _ in range(R + 1)]
for r, li in enumerate(d[1:], 1):
    dp[r] = deepcopy(dp[r-1])
    for i, (cs, vs) in enumerate(li):
        mx = 0
        for cg, vg in li[i+1:]:
            val = vs + mx + vg
            dp[r][cg] = max(dp[r][cg], dp[r-1][cs] + val)
            mx = max(mx, vg)

        dp[r][cs] = max(dp[r][cs], dp[r-1][cs] + vs)

    for c in range(C):
        dp[r][c+1] = max(dp[r][c+1], dp[r][c])

ans = dp[R][C]
print(ans)


### FIXED CODE ###

R, C, K = map(int, input().split())
rcv = [list(map(int, input().split())) for _ in range(K)]

board = [[0] * (C + 1) for _ in range(R + 1)]
for r, c, v in rcv:
    board[r][c] = v

dp = [[[0] * (C + 1) for _ in range(R + 1)] for _ in range(4)]

for r in range(1, R + 1):
    for c in range(1, C + 1):
        v = board[r][c]
        for i in range(4):
            dp[0][r][c] = max(dp[0][r][c], dp[i][r-1][c])
            dp[1][r][c] = max(dp[1][r][c], dp[i][r-1][c] + v)

            dp[i][r][c] = max(dp[i][r][c], dp[i][r][c-1])
            if i > 0:
                dp[i][r][c] = max(dp[i][r][c], dp[i-1][r][c-1] + v)

ans = 0
for i in range(4):
    ans = max(ans, dp[i][R][C])

print(ans)
### BUGGY CODE ###

N=int(input())
A=[0]+[int(x) for x in input().split()]
B=[0 for i in range(N+1)]

for i in range(N):
  B[i+1]=A[i+1]^B[i]
  A[i+1]=A[i+1]+A[i]

c=0
for l in range(1,N+1):
  for r in range(l,N+1):
    if A[r]-A[l-1] == B[r]^B[l-1]:
      c += 1

print(c)


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))

r,S,R=0,0,0

for l in range(N):
  while r<N:
    if S&A[r]==0:
      S|=A[r]
      r+=1
    else:
      break
  R+=r-l
  S&=~A[l]

print(R)
### BUGGY CODE ###

k,s = map(int, input().split())

count = 0
for i in range(k+1):
    if s-i > k:
        rang = k
    else:
        rang = s-i
    for j in range(rang+1):
        if s-i-j < 0:
            continue
        elif s-i-j > k:
            rangg = k
        else:
            rang = s-i-j
        for h in range(rang+1):
            if i+j+h == s:
                count += 1

print(count)

### FIXED CODE ###

k,s = map(int, input().split())

count = 0
for i in range(k+1):
    for j in range(k+1):
        if s-i-j > k or s-i-j < 0:
            continue
        else:
            count += 1
print(count)
### BUGGY CODE ###

import numpy as np

N = int(input())
A = list(map(int, input().split()))
a = 10**9+7

A = np.mod(A,a)

ans = 0

for i in range(N):
    for j in range(i+1,N):
        ans += A[i]*A[j]

ans = ans % a
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
a = 10**9+7
sumA = sum(A)

ans = 0

for i in range(N):
    sumA -= A[i]
    ans += A[i] * sumA
    ans %= a
    
print(ans)
### BUGGY CODE ###

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
    condition[i]=ans

ans=2**(N-1)
ban=0
for i in range(1,2**M):
    num=bin(i).count('1')
    s=set([])
    for j in range(0,M):
        if i>>j &1==1:
            for k in condition[j]:
                s.add(k)

    n=len(s)
    if num%2==1:
        ban+=2**(N-1-n)
    else:
        ban-=2**(N-1-n)

print(ans-ban)

### FIXED CODE ###

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)