Harryxun/stf_run huggingface dataset:
cnt = 0
def s(start, end):
    global cnt
    if(start==len(S)-1):
        return 
    numS = int(S[start:end+1])
    if(numS%2019==0 and numS!=0):
        cnt += 1
    if(end==len(S)-1):
        end = start+2
        s(start+1, end)
        return
    s(start, end+1)

S = input()
s(0, 0)
print(cnt)

### FIXED CODE ###

S = list(map(int, list(input())))[::-1]
N = len(S)
CNT = [0]*2019
CNT[0] = 1
num = 0
d = 0
for i in range(N):
    num += S[i]*pow(10, d, 2019)
    num %= 2019
    CNT[num] += 1
    d += 1
ans = 0 
for cnt in CNT:
    ans += (cnt*(cnt - 1)) // 2
print(ans)
f = []
f = input().split()
if '1' in f:
if '9' in f:
if '7' in f:
if '4' in f:
print("YES")
else:
print("NO")
else:
print("NO")
else:
print("NO")
else:
print("NO")


### FIXED CODE ###

f = []
f = input().split()
if '1' in f:
     if '9' in f:
          if '7' in f:
               if '4' in f:
                    print("YES")
               else:
                    print("NO")
          else:
               print("NO")
     else:
          print("NO")
else:
     print("NO")
s=input()
m=len(s)
sm=0
for i in range(2**(m-1)):
  a=list(str(bin(i)))[::-1]
  b=list(s)
  for j in range(len(a)):
    if a[j]==1:
      b.insert(-j-1,'+')
  sm+=eval(''.join(b))
print(sm)s=input()
m=len(s)
sm=0
for i in range(2**(m-1)):
  a=list(str(bin(i)))[::-1]
  b=list(s)
  for j in range(len(a)-1,-1,-1):
    if a[j]=='1':
      b.insert(-j-1,'+')
  sm+=eval(''.join(b))
print(sm)

### FIXED CODE ###

s=input()
m=len(s)
sm=0
for i in range(2**(m-1)):
  a=list(str(bin(i)))[::-1]
  b=list(s)
  for j in range(len(a)-1,-1,-1):
    if a[j]=='1':
      b.insert(-j-1,'+')
  sm+=eval(''.join(b))
print(sm)
S = map(int, input().split())
if S = ABC
	print("ARC")
else:
  	print("ABC")

### FIXED CODE ###

S = input()
if S == "ABC":
	print("ARC")
else:
  	print("ABC")
n=int(input())
a=list(map(int,input().split()))
bbottom=""
btop=""
for i in range(n):
  if i%2==0:
    bbottom.append(a[i])
  else:
    btop.append(a[i])
ans=btop[::-1]+bbottom
if n%2==1:
  ans=ans[::-1]
print(ans)
       


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
bbottom=[]
btop=[]
for i in range(n):
  if i%2==0:
    bbottom.append(a[i])
  else:
    btop.append(a[i])
ans=btop[::-1]+bbottom
if n%2==1:
  ans=ans[::-1]
print(*ans)
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

limit=50
graph=[[False]*limit for _ in range(limit)]
visited=[False]*limit

def dfs(n,v):
  visited[v]=True
  for v2 in range(n):
    if graph[v][v2]==False:
      continue
    if visited[v2]:
      continue
    dfs(n,v2)

def main():
  n,m=LI()
  a=[[] for _ in range(n)]
  b=[[] for _ in range(n)]
  for i in range(m):
    _a,_b=LI()
    _a-=1
    _b-=1
    a[i]=_a
    b[i]=_b
    graph[_a][_b]=True
    graph[_b][_a]=True

  ans=0
  for i in range(m):
    graph[a[i]][b[i]]=False
    graph[b[i]][a[i]]=False

    for j in range(n):
      visited[j]=False
    dfs(n,0)
    no_visited=False
    for j in range(n):
      if visited[j]==False:
        no_visited=True
    if no_visited:
      ans+=1
    graph[a[i]][b[i]]=True
    graph[b[i]][a[i]]=True

  return ans

# main()
print(main())


### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

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

nmax=50
graph=[[False]*nmax for _ in range(nmax)]
visited=[False]*nmax

def dfs(n,v):
  visited[v]=True
  for v2 in range(n):
    if graph[v][v2]==False:
      continue
    if visited[v2]:
      continue
    dfs(n,v2)

def main():
  n,m=LI()
  a=[]
  b=[]
  for _ in range(m):
    _a,_b=LI()
    a.append(_a-1)
    b.append(_b-1)
    graph[_a-1][_b-1]=True
    graph[_b-1][_a-1]=True

  ans=0
  for i in range(m):
    graph[a[i]][b[i]]=False
    graph[b[i]][a[i]]=False

    for j in range(n):
      visited[j]=False

    dfs(n,j)

    bridge=False
    for j in range(n):
      if visited[j]==False:
        bridge=True
    if bridge:
      ans+=1

    graph[a[i]][b[i]]=True
    graph[b[i]][a[i]]=True

  return ans

# main()
print(main())
def abe(n):
    count = 0
    while n % 2 ==0:
        n = n / 2
        count += 1
    return count

x = int(input())
y = map(int,input().split())
z = min(map(abe,y))
print(z)

### FIXED CODE ###

S = input()
count = 0
for i in S:
    if i == "1":
        count += 1
print(count)
import math

n, x0 = map(int, input().split())
x = list(map(int, input().split())) + [x0]

x = list(set(x))
x.sort()
if len(x) >= 3:
    diff_x = [x[i+1] - x[i] for i in range(n-1)]
    ans = diff_x[0]
    for dx in diff_x[1:]:
        ans = math.gcd(ans, dx)
else:
    ans = x[1] - x[0]

print(ans)

### FIXED CODE ###

def gcd(a, b):
    m, n = max(a,b), min(a,b)
    while n != 0:
        m, n = n, m%n
    return m

n, x0 = map(int, input().split())
x = list(map(int, input().split())) + [x0]

x = list(set(x))
x.sort()
if len(x) >= 3:
    diff_x = [x[i+1] - x[i] for i in range(n)]
    ans = diff_x[0]
    for dx in diff_x[1:]:
        ans = int(gcd(ans, dx))
elif len(x) == 2:
    ans = x[1] - x[0]


print(ans)
a = int(input())
b = int(1)
while True:
	if b < a+1:
		x = map(int,input().split(' '))
		x.sort()
		if x[0]**2 + x[1]**2 = x[2]**2:
			print('YES')
		else:
			print('NO')
		b += 1
		continue
	else:
		break

### FIXED CODE ###

for val in range(input()):
	x = map(int,raw_input().split(' '))
	x.sort()
	if x[0]**2+x[1]**2==x[2]**2: print 'YES'
	else: print 'NO'
import sys
from functools import lru_cache
 
#read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
def mp(arg):
  return map(int,arg.split())
n=read()
res=1
mod=10**18
a=list(reads())
if 0 in a:
  print("0")
  exit()
for i in range(n):   
    res*=a[i]
    print(res)
    if res>mod:
        print("-1")
        exit()
print(res)

### FIXED CODE ###

from decimal import *
a,b=input().split()
a=int(a)
b=Decimal(b)
print(int(a*b))
import sys
import numpy as np

def main(N, S):
    dp = np.zeros((N + 1, N + 1), dtype=int)
    ans=0
    for i in range(N - 1):
        for j in range(i + 1, N):
            dp[i][j] = min(j - i, dp[i - 1][j - 1] + 1) if S[i] == S[j] else 0
        ans = max(ans, max(dp[i]))
    return ans

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

    def cc_export(f, signature):
        cc.export(f.__name__, signature)(f)
        return numba.njit(f)

    main = cc.export('main', 'i8(i8,i8[:])')
    cc.compile()

from my_module import main

N = int(input())
S = np.array([ord(_) for _ in input()])
print(main(N, S))


### FIXED CODE ###

import itertools
N = int(input())
S = input()
dp = [[0] * N for _ in range(N)]
ans = 0
for i, j in itertools.combinations(range(N), 2):
    if S[i] == S[j]:
        dp[i][j] = dp[i - 1][j - 1] + 1
    else:
        dp[i][j] = 0
    ans = max(ans, min(j - i, dp[i][j]))
print(ans)
def tax(p,x):
    return p*(100+x) // 100
def solve(X,Y,S):
    for a in range(1,S):
        for b in range(1,S-a+1):
            sum = tax(a,X)+tax(b,X)
            if sum == S:
                NS = tax(a,Y)+tax(b,Y)
                if newsum > ans:
                    A = NS
            if sum > S:
                break
    return A 
while True:
    X,Y,S = map(int, input().split()) 
    if X == 0:
        break
    print(solve(X,Y,S))


### FIXED CODE ###

def tax(p,x):
    return p*(100+x) // 100

def solve(X,Y,S):
    A=0
    sum=0
    NS=0
    for a in range(1,S):
        for b in range(1,S-a+1):
            sum = tax(a,X)+tax(b,X)
            if sum == S:
                NS = tax(a,Y)+tax(b,Y)
                if NS > A:
                    A = NS
            if sum > S:
                break
    return A 

while True:
    X,Y,S = map(int, input().split()) 
    if X == 0:
        break
    print(solve(X,Y,S))
import numpy as np
from collections import deque

n = int(input())
matrix = np.zeros((n,n),dtype="int32")
for i in range(n-1):
    v,w,d = map(int,input().split())
    matrix[v-1,w-1] = d
#print(matrix)

queue = deque([0])
check = [0]
ans = np.zeros((n),dtype="int32")

while queue:
    x = queue.popleft()
    #print("x:",x)
    for i in range(n):
        #print("i:",i,"check:",check)
        if i not in check:
            if matrix[x,i] != 0:
                #print("d:",matrix[x,i])
                if matrix[x,i]%2==0:
                    #print("even")
                    ans[i] = ans[x]
                else:
                    #print("odd")
                    if ans[x] == 0:
                        ans[i] = 1
                    else:
                        ans[i] = 0
                check.append(i)
                queue.append(i)
                #print("APPEND check:",check,"queue:",queue)
                
for i in ans:
    print(i)

### FIXED CODE ###

# coding: utf-8
from collections import deque

n = int(input())

lw = [[] for _ in range(n+1)]
for i in range(n-1):
    u,v,w = map(int,input().split())
    lw[u].append((v,w))
    lw[v].append((u,w))

#print(lw)

ans = [-1] * (n+1)
q = deque()
ans[1] = 0
q.append(1)
while q:
    r = q.popleft()
    prev = ans[r]
    
    for x in lw[r]:
        #print(x)
        y = x[0]
        if ans[y] >= 0:
            continue
        q.append(y)
        if x[1]%2==0:
            ans[y] = ans[r]
        else:
            ans[y] = 1 - ans[r]

for x in ans[1:]:
    print(x)
import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    import functools
    n=int(input())
    n * 2 // functools.gcd(n, 2)

resolve()

### FIXED CODE ###


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

def resolve():
    import fractions
    n=int(input())
    print(n * 2 // fractions.gcd(n, 2))
resolve()
def solve(i, m):
  if dp[i][m]!=-1
    return dp[i][m]

  if m == 0:
    dp[i][m] = 1
  elif i >= n:
    dp[i][m] = 0
  elif solve(i+1, m):
    dp[i][m] = 1
  elif solve(i+1, m-A[i]):
    dp[i][m] = 1
  else:
    dp[i][m] = 0

  return dp[i][m]



n = input()
A = map(int, raw_input().split())
p = input()
m = map(int, raw_input().split())

for i in range(n):
  for m in range(p):
    dp[i][m] == -1

for i in range(p):
  if solve(0, m[i]):
    print 'yes'
  else:
    print 'no'

### FIXED CODE ###

def solve(i, m):
  if dp[i][m] != -1:
    return dp[i][m]

  if m == 0:
    dp[i][m] = 1
  elif i >= n:
    dp[i][m] = 0
  elif solve(i+1, m):
    dp[i][m] = 1
  elif solve(i+1, m-A[i]):
    dp[i][m] = 1
  else:
    dp[i][m] = 0

  return dp[i][m]



n = input()
A = map(int, raw_input().split())
p = input()
m = map(int, raw_input().split())

dp = [[-1 for col in range(2000)] for row in range(n+1)]

for i in range(p):
  if solve(0, m[i]):
    print 'yes'
  else:
    print 'no'
N,M = list(map(int,input().split()))
a = [int(input()) for i in range(M)]
dekai = 1000000007
 
def Fib(n):
	a,b = 0,1
	if n == 1:
		return a
	elif n == 2:
		return b
	else:
		for i in range(n-2):
			a,b = b,a+b
		return b


ans = 1
for i in range(M+1):
	if i == 0:
		ans = ans*Fib(a[0]-(-1))%dekai
	elif i == M:
		ans = ans*Fib(N+1-a[M-1])%dekai
	else:
		ans = ans*Fib(a[i]-a[i-1])%dekai
print(ans)

### FIXED CODE ###

N,M = list(map(int,input().split()))
a = [int(input()) for i in range(M)]
dekai = 1000000007
"""
import sympy as sym

def Fib(n):
	x = sym.symbols('x',nonnegative=True,integer=True)
	Fib=1/sym.sqrt(5)*(((1+sym.sqrt(5))/2)**(n-1)-((1-sym.sqrt(5))/2)**(n-1))
	result=Fib.subs(x,n)
	result=result.evalf(int(n*3/14)+1)
	return int(result)


"""
def Fib(n):
	a,b = 0,1
	if n == 1:
		return a
	elif n == 2:
		return b
	else:
		for i in range(n-2):
			a,b = b,a+b
		return b
ans = 1

if M == 0:
	print(Fib(N+1-(-1))%dekai)
	exit()

for i in range(M+1):
	if i == 0:
		ans = (ans*(Fib(a[0]-(-1))%dekai))%dekai
	elif i == M:
		ans = (ans*(Fib(N+1-a[M-1])%dekai))%dekai
	else:
		ans = (ans*(Fib(a[i]-a[i-1])%dekai))%dekai
print(ans)
n= int(input())
s = input()
a = [str(c) for c in s]

z = [0, n-1]


def search(a,n,x,y):
  x1 = x
  y1 = y

  for i in range(n):
    x = x1 + i
    if a[x1 +i] == 'W':
      break
  for i in range(n):
    y = y1 -i
    if a[y1-i] == 'R':
      break
  return[x, y]

c = 0

while True:
  z = search(a, n, z[0],z[1])
  if z[0] > z[1]:
    break
  else:
    c +=1
    a[z[0]], a[z[1]] = a[z[1]], a[z[0]]
  
  
    
print(c)

### FIXED CODE ###

n = int(input())
s = input()
a = [str(c) for c in s]

def sea(a, x, y, n):
  while x < n-1:
    if a[x] == 'W':
      break
    x += 1
    
  while y > 0:
    if a[y] == 'R':
      break
    y -= 1
  
  return[x, y]

z = [0, n-1]

z = sea(a, z[0] ,z[1], n)
c = 0
while z[0] < z[1]:
  a[z[0]], a[z[1]] = a[z[1]], a[z[0]]
  c += 1
  z = sea(a,z[0], z[1],n)
  
print(c)
n, k = map(int, input().split())
l = list(map(int, input().split()))
S = collections.Counter(l)
S = sorted(S.values())
print(sum(S[:len(S)-k]))

### FIXED CODE ###

import collections
n, k = map(int, input().split())
l = list(map(int, input().split()))
S = collections.Counter(l)
S = sorted(S.values())
print(sum(S[:len(S)-k]))
N, M = map(int, input().split())
s = [list(map(int, input().spllit())) for i in range(M)]
p = list(map(int, input().split()))
total = 0
flag = 1
for i in range(2 ** N):
  now = format(i, "0{}b".format(n))
  for k in range(M):
    tmp = 0
    for l in range(s[k][0]):
      if now[s[k][l+1]-1] == '1':
        tmp += 1
    if tmp % 2 == p[k]:
      continue
    else:
      flag = 0
      break
  if flag == 1
    total += 1
  flag = 1
print(total)


### FIXED CODE ###

n, m = map(int, input().split())
switch = []
for i in range(m):
    switch.append(list(map(int, input().split())))
p = list(map(int, input().split()))

ans = 0
for i in range(2**n):
    i = format(i, "0{}b".format(n))
    flag = 1
    for j in range(m):
        count = 0
        for k in range(switch[j][0]):
            if i[switch[j][k+1]-1] == "1":
                count += 1
        if count % 2 == p[j]:
            continue
        else:
            flag = 0
            break
    if flag == 1:
        ans += 1
print(ans)
# import sys
# sys.setrecursionlimit(2000)

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


class Group:
    
    def __init__(self):
        self.n = 0
        self.x = []
        self.y = []
        
    def new_cor_n(self):
        return len(self.x) * len(self.y) - self.n
    
def grouping(group, x, xcor, ycor):
    xcor[x][1] = True
    group.x.append(x)
    for y in xcor[x][0]:
        if ycor[y][1]:
            continue
        group.n += 1
        ycor[y][1] = True
        group.y.append(y)
        for x_ in ycor[y][0]:
            if xcor[x_][1]:
                continue
            group.n += 1
            grouping(group, x_, xcor, ycor)
            
if N <= 2:
    print(0)
else:
    xcor, ycor = {}, {}
    for xi, yi in COR:
        if xi in xcor:
            xcor[xi][0].append(yi)
        else:
            xcor[xi] = [[yi], False]
        if yi in ycor:
            ycor[yi][0].append(xi)
        else:
            ycor[yi] = [[xi], False]
    group_list = []
    for x, v in xcor.items():
        if v[1]:
            continue
        group = Group()
        group_list.append(group)
        grouping(group, x, xcor, ycor)
    s = 0
    for group in group_list:
        s += group.new_cor_n()
    print(s)

### FIXED CODE ###

# import sys
# sys.setrecursionlimit(20000)


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


class Group:
    
    def __init__(self):
        self.n = 0
        self.x = 0
        self.y = 0
        self.xy = {}
        
    def new_cor_n(self):
        return self.x * self.y - self.n
        

def grouping(group, x, xcor, ycor):
    x_list = []
    group.x += 1
    for y in xcor[x][0]:
        if (x, y) not in group.xy:
            group.n += 1
            group.xy[(x, y)] = None
        if ycor[y][1]:
            continue
        ycor[y][1] = True
        group.y += 1
        for x_ in ycor[y][0]:
            if (x_, y) not in group.xy:
                group.n += 1
                group.xy[(x_, y)] = None
            if xcor[x_][1]:
                continue
            xcor[x_][1] = True
            x_list.append(x_)
    return x_list

if N <= 2:
    print(0)
else:
    xcor, ycor = {}, {}
    for xi, yi in COR:
        if xi in xcor:
            xcor[xi][0].append(yi)
        else:
            xcor[xi] = [[yi], False]
        if yi in ycor:
            ycor[yi][0].append(xi)
        else:
            ycor[yi] = [[xi], False]
    group_list = []
    for i, v in xcor.items():
        if v[1]:
            continue
        group = Group()
        group_list.append(group)
        xcor[i][1] = True
        x_list = [i]
        while True:
            new_x_list = []
            for x in x_list:
                new_x_list += grouping(group, x, xcor, ycor)
            if new_x_list == []:
                break
            x_list = new_x_list
    s = 0
    for group in group_list:
        s += group.new_cor_n()
    print(s)
print(-int(input()+int(input())*2) 

### FIXED CODE ###

print(-int(input())+int(input())*2)
n = list[int(input()) for i in range(3)]
print((n[0] - n[1] + 1) * (n[0] - n[2] + 1) )

### FIXED CODE ###

n = [int(input()) for i in range(3)]
print((n[0] - n[1] + 1) * (n[0] - n[2] + 1) )
import itertools
N = int(input())
p = tuple(map(int, input().split()))
q = tuple(map(int, input().split()))

junretu = [i + 1 for i in range(N)]
cnt = 0
for i in itertools.permutations(junretu, N):
    cnt += 1
    if i == p:
        a = cnt
        #cnt += 1
    elif i == q:
        b = cnt
        #cnt += 1
    #cnt += 1
print(abs(a - b))

### FIXED CODE ###

import itertools
N = int(input())
p = tuple(map(int, input().split()))
q = tuple(map(int, input().split()))

junretu = [i + 1 for i in range(N)]
cnt = 0
for i in itertools.permutations(junretu, N):
    cnt += 1
    if i == p:
        a = cnt
        #cnt += 1
    if i == q:
        b = cnt
        #cnt += 1
    #cnt += 1
print(abs(a - b))
c500 = int(input())
c100 = int(input())
c500 = int(input())
t = int(input())
s = 0

for a in range(0, c500 + 1):
    for b in range(0, c100 + 1):
        for c in range(0, c50 + 1):
            if 500*a + 100*b + 50*c == t:
                s = s + 1
print(s)


### FIXED CODE ###

c500 = int(input())
c100 = int(input())
c50 = int(input())
t = int(input())
s = 0

for a in range(0, c500 + 1):
    for b in range(0, c100 + 1):
        for c in range(0, c50 + 1):
            if 500*a + 100*b + 50*c == t:
                s = s + 1
print(s)
import sys

sys.setrecursionlimit = 10**8

n = int(input())
tr = [list() for _ in range(n)]
num = [None]*n
ran = [0]*n
par = [-1]*n
dep = [0]*n
for _ in range(n-1):
  a,b = map(int,input().split())
  a -= 1; b -= 1
  tr[a].append(b)
  tr[b].append(a)
k = int(input())
root,c = map(int,input().split())
root -= 1
num[root] = c
def dfs(v,p,par,dep):
  for x in tr[v]:
    if x == p:
      continue
    par[x] = v
    dep[x] = dep[v] + 1
    dfs(x,v,par,dep)
  return
dfs(root,-1,par,dep)
for _ in range(k-1):
  v,c = map(int,input().split())
  v -= 1
  if abs(c-num[root]) > dep[v] or dep[v]%2 != (c-num[root])%2:
    print("No")
    exit(0)
  num[v] = c

def dfs2(v,p,ran):
  cur = [-10**9,10**9] if num[v] is None else [num[v],num[v]]
  if tr[v] == [p]: 
    ran[v] = tuple(cur)
    return
  for x in tr[v]:
    if x == p:
      continue
    dfs2(x,v,ran)
    if ran[x][0] > cur[0]:
      cur[0] = ran[x][0]
    if ran[x][1] < cur[1]:
      cur[1] = ran[x][1]
  cur[0] -= 1; cur[1] += 1
  ran[v] = tuple(cur)
  return

dfs2(root,None,ran)
  
q = [(root,None)]
while q:
  v,p = q.pop()
  for x in tr[v]:
    if x == p:
      continue
    if ran[x][0]<=num[v]+1<=ran[x][1]:
      num[x] = num[v] + 1
    elif ran[x][0]<=num[v]-1<=ran[x][1]:
      num[x] = num[v] - 1
    else:
      print("No")
      exit(0)
    q.append((x,v))
print("Yes")
for c in num:
  print(c)


### FIXED CODE ###

import sys

sys.setrecursionlimit(10**6)

n = int(input())
tr = [list() for _ in range(n)]
num = [None]*n
ran = [0]*n
dep = [0]*n
for _ in range(n-1):
  a,b = map(int,input().split())
  a -= 1; b -= 1
  tr[a].append(b)
  tr[b].append(a)
k = int(input())
root,c = map(int,input().split())
root -= 1
num[root] = c
def dfs(v,p,dep):
  for x in tr[v]:
    if x == p:
      continue
    dep[x] = dep[v] + 1
    dfs(x,v,dep)
  return
dfs(root,-1,dep)
for _ in range(k-1):
  v,c = map(int,input().split())
  v -= 1
  if abs(c-num[root]) > dep[v] or dep[v]%2 != (c-num[root])%2:
    print("No")
    exit(0)
  num[v] = c

def dfs2(v,p,ran):
  cur = [-10**9,10**9] if num[v] is None else [num[v],num[v]]
  if tr[v] == [p]: 
    ran[v] = tuple(cur)
    return
  for x in tr[v]:
    if x == p:
      continue
    dfs2(x,v,ran)
    if ran[x][0] > cur[0]:
      cur[0] = ran[x][0]
    if ran[x][1] < cur[1]:
      cur[1] = ran[x][1]
  cur[0] -= 1; cur[1] += 1
  ran[v] = tuple(cur)
  return

dfs2(root,None,ran)
  
q = [(root,None)]
while q:
  v,p = q.pop()
  for x in tr[v]:
    if x == p:
      continue
    if ran[x][0]<=num[v]+1<=ran[x][1]:
      num[x] = num[v] + 1
    elif ran[x][0]<=num[v]-1<=ran[x][1]:
      num[x] = num[v] - 1
    else:
      print("No")
      exit(0)
    q.append((x,v))
print("Yes")
for c in num:
  print(c)
a = int(input())
b = map(int, input().split())
b_list = list(b)
count = 0
for i in range(len(b_list)):
    if b_list[i] == min(b_list[:i+1]):
        count += 1
        
print(count)

### FIXED CODE ###

n = input()
(p,q) = n.split()
a='Yes'
b='No'
if p == q:
    print(a)
else:
    print(b)
A,B,C=map(int,input().split())
d=B//A
if d<C:
  print(d)
  else:
    print(C)

### FIXED CODE ###

A,B,C=map(int,input().split())
d=B//A
if d<C:
  print(d)
else:
  print(C)
N,X=map(int,input().split())
A=list(map(int,input().split()))
D=0
cnt=1
for i in range(X+1):
  D+=A[i]
  if D <= X:
    cnt+=1
  else:
    print(cnt)
    exit()

### FIXED CODE ###

N,X=map(int,input().split())
A=list(map(int,input().split()))
D=0
cnt=1
if sum(A)<= X:
  print(N+1)
  exit()
else:
  for i in range(X+1):
    D+=A[i]
    if D <= X:
      cnt+=1
    else:
      print(cnt)
      exit()
n, init = map(int, input().split())
y = list(map(int, input().split()))
x = list(map(lambda a: abs(a-init),y))
def gcd(m,n):
    if n > m:
        gcd(n,m)
    elif m%n == 0:
        return n
    else:
        gcd(n,m%n)
g = x[0]
for i in range(n):
    if g == 1:
        break
    elif (x[i] % g) != 0:
        g = gcd(g,x[i])
print(g)


### FIXED CODE ###

n, init = map(int,input().split())
x = list(map(lambda x: abs(int(x)-init), input().split()))
g = x[0]
def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x%y)
for i in range(1,n):
    g = gcd(g,x[i])
print(g)
import numpy
N = int(input())
ary = list(map(int, input().split(' ')))
count = 0
zero_count = 0
for i in range(N):
    if ary[0] == 0:
        zero_count += 1
        ary.pop(0)
        continue
    elif ary[0] == ary[1]:
        ary.pop(0)
        continue
    else:
        if zero_count != 0:
            count += zero_count * (zero_count + 1) / 2
            zero_count = 0
        ary_int = numpy.cumsum(ary)
        count += ary_int.tolist().count(0)
        ary.pop(0)
if zero_count != 0:
    count += zero_count * (zero_count + 1) / 2
    zero_count = 0

print(int(count))

### FIXED CODE ###

import numpy
N = int(input())
ary = list(map(int, input().split(' ')))
ary_int = numpy.cumsum(ary).tolist()
ary_int.sort()
ary_int.append(float('inf'))

count = 0
same_count = 0
for i in range(N):
    if ary_int[i] == ary_int[i+1]:
        same_count += 1
    else:
        count += same_count * (same_count + 1) // 2
        same_count = 0
count += ary_int.count(0)
print(int(count))