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

from collections import deque
N,M = map(int,input().split())
graph = []
fship = []
for i in range(M):
    x,y = map(int,input().split())
    if x>y:
        x,y = y,x
    if [x-1,y-1] not in fship:
        fship.append([x-1,y-1])
fship.sort(key = lambda x: x[0])
graph = [[] for _ in range(N)]
for i in fship:
    graph[i[0]].append(i[1])

dist = [0]*N
ans = 0

for i in range(N):
    if dist[i]:
        continue
    dist[i] = 1
    tmp = 0
    d = deque()
    d.append(i)
    while d:
        v = d.popleft()
        for i in graph[v]:
            if dist[i]:
                continue
            dist[i] = 1
            d.append(i)
            tmp += 1
    ans = max(ans,tmp)
print(ans+1)

### FIXED CODE ###

from collections import deque
N,M = map(int,input().split())
graph = [[] for _ in range(N)]
for i in range(M):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    graph[x].append(y)
    graph[y].append(x)

seen = [None]*N
ans = -1

for i in range(N):
    if seen[i]:
        continue
    seen[i] = True
    tmp = 0
    d = deque()
    d.append(i)
    while d:
        v = d.popleft()
        for i in graph[v]:
            if seen[i]:
                continue
            seen[i] = True
            d.append(i)
            tmp += 1
    ans = max(ans,tmp)
print(ans+1)
### BUGGY CODE ###

n = int(input())
s = list(input())

dp = [[0] * n for _ in range(n)]
for i in range(n-1, -1, -1):
    for j in range(n-1, -1, -1):
        if s[i] == s[j]:
            if j+1 <= n-1 and i+1 <= n-1:
                dp[i][j] = dp[i+1][j+1] + 1
            else:
                dp[i][j] = 1
                
for i in range(n):
    for j in range(n):
        dp[i][j] = min(abs(i-j), dp[i][j])

ans = 0
for i in range(n):
    ans = max(ans, max(dp[i]))
print(ans)

### FIXED CODE ###

n = int(input())
s = list(input())

dp = [[0] * n for _ in range(n)]
for i in range(n-1, -1, -1):
    for j in range(n-1, -1, -1):
        if s[i] == s[j]:
            if j+1 <= n-1 and i+1 <= n-1:
                dp[i][j] = dp[i+1][j+1] + 1
            else:
                dp[i][j] = 1
                
for i in range(n):
    for j in range(n):
        dp[i][j] = min(abs(i-j), dp[i][j])

ans = 0
for i in range(n):
    ans = max(ans, max(dp[i]))
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from collections import deque
from heapq import heapify, heappush as hpush, heappop as hpop
N, M, L = map(int, input().split())
X = [[] for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    X[a-1].append([b-1, c])
    X[b-1].append([a-1, c])

def dijkstra(n, E, i0=0):
    h = [[0, i0]]
    D = [-1] * n
    done = [0] * n
    D[i0] = 0
    
    while h:
        d, i = hpop(h)
        done[i] = 1
        for j, w in E[i]:
            nd = d + w
            if D[j] < 0 or D[j] >= nd:
                if done[j] == 0:
                    hpush(h, [nd, j])
                    D[j] = nd
    return [d if d >= 0 else 1<<100 for d in D]
def BFS(n, E, i0=0):
    Q = deque([i0])
    D = [-1] * n
    D[i0] = 0
    while Q:
        x = Q.popleft()
        for c in E[x]:
            if D[c] == -1:
                D[c] = D[x] + 1
                Q.append(c)
    return [d if d >= 0 else 1<<100 for d in D]

Y = [[] for _ in range(N)]
for i in range(N):
    D1 = dijkstra(N, X, i)
    for j in range(N):
        if i == j: continue
        if D1[j] <= L:
            Y[i].append(j)

ans = []
for _ in range(int(input())):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    a = BFS(N, Y, s)[t]-1
    ans.append(str(a if a < 1 << 50 else -1))

print("\n".join(ans))

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
from collections import deque
N, M, L = map(int, input().split())
D = [[1<<40] * N for _ in range(N)]
for i in range(N):
    D[i][i] = 0
for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    D[a][b] = c
    D[b][a] = c

for k in range(N):
    for i in range(N):
        for j in range(N):
            D[i][j] = min(D[i][j], D[i][k] + D[k][j])
Y = [[] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i == j: continue
        if D[i][j] <= L:
            Y[i].append(j)
def BFS(n, E, i0=0):
    Q = deque([i0])
    D = [-1] * n
    D[i0] = 0
    while Q:
        x = Q.popleft()
        for c in E[x]:
            if D[c] == -1:
                D[c] = D[x] + 1
                Q.append(c)
    return D
D2 = []
for i in range(N):
    D2.append(BFS(N, Y, i))

ans = []
for _ in range(int(input())):
    s, t = map(int, input().split())
    a = D2[s-1][t-1]-1
    ans.append(str(a if a >= 0 else -1))
print("\n".join(ans))
### BUGGY CODE ###

N, K =map(int, input().split())
p=list(map(int, input().split()))
expect=[(dice+1)/2 for dice in p]
#print(expect)
plus_p=[sum(expect[i:i+K]) for i in range(N-K+1)]
#print(plus_p)
print(max(plus_p))

### FIXED CODE ###

N, K =map(int, input().split())
p=list(map(int, input().split()))

expect=[(dice+1)/2 for dice in p]
#print(expect)
#plus_p=[sum(expect[i:i+K]) for i in range(N-K+1)]

first=sum(expect[0:K])
plus_p=[first]
for i in range(1, N-K+1):
	plus_p.append(plus_p[i-1]-expect[i-1]+expect[i-1+K])
#print(plus_p)
print(max(plus_p))
### BUGGY CODE ###

N,M=map(int,input().split())
start=[]
end=[]
for i in range(M):
    a,b=map(int,input().split())
    if a==1:
        start.append(b)
    elif b==N:
        end.append(a)

for i in start:
    if i in end:
        print('POSSIBLE')
        exit()

print('IMPOSSIBLE')

### FIXED CODE ###

N,M=map(int,input().split())
start=[]
end=[]
for i in range(M):
    a,b=map(int,input().split())
    if a==1:
        start.append(b)
    elif b==N:
        end.append(a)

startset=set(start)
endset=set(end)
if startset & endset:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

import math
import collections
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 LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]

n=I()
s=input()
r=[]
g=[]
t=[]
for i in range(n):
    if s[i:i+1]=="R":
        r.append(i)
    elif s[i:i+1]=="G":
        g.append(i)
    else:
        t.append(i)
R=len(r)
G=len(g)
T=n-R-G
ans=R*G*T
#print(r)
#print(g)
#print(t)
for a in r:
    for b in g:
        c=collections.Counter(t)
        ans-=c[2*b-a]
        ans-=c[2*a-b]
        if (a+b)%2==0:
            ans-=c[(a+b)//2]
        '''if 2*b-a in t:
            ans-=1
        if 2*a-b in t:
            ans-=1
        if (a+b)%2==0 and (a+b)//2 in t:
            ans-=1'''
print(ans)

### FIXED CODE ###

import math
import collections
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 LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]

n=I()
s=input()
r=[]
g=[]
t=[]
for i in range(n):
    if s[i:i+1]=="R":
        r.append(i)
    elif s[i:i+1]=="G":
        g.append(i)
    else:
        t.append(i)
R=len(r)
G=len(g)
T=n-R-G
ans=R*G*T
for i in range(n-1):
    for j in range(i+1,n):
        if s[i]!=s[j]:
            if j<2*i-j<=n-1:
                if s[i]!=s[2*i-j] and s[j]!=s[2*i-j]:
                    ans-=1
            if j<2*j-i<=n-1:
                if s[i]!=s[2*j-i] and s[j]!=s[2*j-i]:
                    ans-=1
            if (i+j)%2==0 and j<(i+j)//2 and s[i]!=s[(i+j)//2] and s[j]!=s[(i+j)//2]:
                ans-=1
print(ans)
### BUGGY CODE ###

from collections import deque
n,m = map(int,input().split())
to = [[] for _ in range(n)]
v = []
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)
    v.append((a,b))
ans = m
seen = [False]*n
q = deque()
for i in range(m):
    a,b = v[i]
    q.clear()
    q.append((a,-1))
    for j in range(n): seen[j] = False
    seen[a] = True
    flag = True
    while q and flag:
        cur,prev = q.popleft()
        for nxt in to[cur]:
            if nxt == b:
                if cur == a: continue
                ans -= 1
                flag = False
                break
            if nxt == prev: continue
            if seen[nxt]: continue
            q.append((nxt,cur))

print(ans)

### FIXED CODE ###

from collections import deque
n,m = map(int,input().split())
to = [[] for _ in range(n)]
v = []
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)
    v.append((a,b))
ans = m
seen = [False]*n
stk = deque()
for i in range(m):
    a,b = v[i]
    stk.clear()
    stk.append((a,-1))
    for j in range(n): seen[j] = False
    seen[a] = True
    flag = True
    while stk and flag:
        cur,prev = stk.pop()
        seen[cur] = True
        for nxt in to[cur]:
            if nxt == b:
                if cur == a: continue
                ans -= 1
                flag = False
                break
            if nxt == prev: continue
            if seen[nxt]: continue
            stk.append((nxt,cur))

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

n,m=map(int,input().split())
ans=0
for i in range(1,m//n+1):
  if m%i==0:
    ans=i
print(ans)


### FIXED CODE ###

n,m=map(int,input().split())
ans=0
import math
for i in range(1,int(math.sqrt(m))+1):
  if m%i!=0:
    continue
  i2=m//i
  if i*n<=m:
    ans=max(ans,i)
  if i2*n<=m:
    ans=max(ans,i2)
print(ans)
### BUGGY CODE ###

n,k = map(int,input().split())
p = [int(_) for _ in input().split()]

ans = 0
for i in range(n-k+1):
  ans = max(ans,(k+sum(p[i:i+k]))/2)

print(ans)


### FIXED CODE ###

n,k = map(int,input().split())
p = list(map(int, input().split()))

ans = sum(p[0:k])
tmp = ans
for i in range(n-k):
  tmp = tmp - p[i] + p[i+k]
  ans = max(ans,tmp)

print((k+ans)/2)
### BUGGY CODE ###

N,K=map(int,input().split())
List = list(map(int, input().split()))
data_x = [0]*N
res = [0]*N

def imosu(x,k):
  data = [0]*k
  for i in range(k):
    first = i-x[i]
    last = i+x[i]
    if first < 0:
      first = 0
    data[first] += 1
    if last+1 < k:
      data[last+1] +=-1
  return data

def ruiseki_f(y, k):
  ruiseki = [0]*k
  ruiseki[0] = y[0]
  for i in range(k-1):
    ruiseki[i+1] = ruiseki[i] + y[i+1]
  return ruiseki

for i in range(K):
  Flag = True
  data_x = imosu(List,N)
  List = ruiseki_f(data_x,N)
  for j in range(N):
    if not List[j] == N:
      Flag = False
  if Flag:
    break
res = List
print(*res)

### FIXED CODE ###

N,K=map(int,input().split())
List = list(map(int, input().split()))
 
def imosu(x,k):
  data = [0]*k
  for i in range(k):
    first = i-x[i]
    last = i+x[i]
    if first < 0:
      first = 0
    data[first] += 1
    if last+1 < k:
      data[last+1] +=-1
  ruiseki = [0]*k
  ruiseki[0] = data[0]
  for i in range(k-1):
    ruiseki[i+1] = ruiseki[i] + data[i+1]
  return ruiseki
 
for i in range(K):
  List = imosu(List,N)
  if List.count(N) == N:
    break
print(*List)
### BUGGY CODE ###

N = int(input())
count =0
t = True
for i in range(1, 10):
    if  N % i == 0:
        A = N/i
        if 1 <= A <= 9:
            while(t): 
                for a in range(1, 10):
                    if a != i :
                        if A % a == 0:
                            print('Yes')
                            count += 1
                            t = False
                            break
                    break
if  count != 1:
    print('No')

### FIXED CODE ###

a = int(input())
for i in range(1, 10):
    for j in range(1, 10):
        if i*j == a:
            print("Yes")
            exit()
print("No")
### BUGGY CODE ###

N, Q = map(int, input().split())
STX = [[int(i) for i in input().split()] for _ in range(N)]
D = [int(input()) for _ in range(Q)]

STX.sort(key=lambda x: x[2])

for d in D :
    flag = True
    for s, t, x in STX :
        if s - 0.5 <= d + x <= t - 0.5 :
            print(x)
            flag = False
            break
    if flag :
        print(-1)

### FIXED CODE ###

import sys, heapq
input = sys.stdin.readline

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

event = []
for _ in range(N) :
    s, t, x = map(int, input().split())
    event.append([s - x, t - x, x])

D = [int(input()) for _ in range(Q)]

event.sort()

closed = []
ei = 0

for d in D :
    while ei < N and event[ei][0] <= d :
        heapq.heappush(closed, (event[ei][2], event[ei][1]))
        ei += 1
    while closed and closed[0][1] <= d :
        heapq.heappop(closed)
    
    if closed :
        print(closed[0][0])
    else :
        print(-1)
### BUGGY CODE ###

n, k = map(int, input().split())
counter = 1
while n != 1:
    n = int(n / k)
    counter += 1
print(counter)


### FIXED CODE ###

n, k = map(int, input().split())
counter = 1
while n >= k:
    n = int(n / k)
    counter += 1
print(counter)
### BUGGY CODE ###

ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

import math

n = ni()
nn = n
mn = 10**12
nums = [1]

i=2
while i<=math.ceil(math.sqrt(n)+1):
  while n%i==0:
    nums.append(i)
  i+=1

for num in nums:
  other = nn//num
  mn = min(mn, num+other-2)

print(mn)

### FIXED CODE ###

ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

import math

n = ni()
nn = n
mn = 10**12
nums = [1]

i=2
while i<=math.ceil(math.sqrt(n)+1):
  if n%i==0:
    nums.append(i)
  i+=1

for num in nums:
  other = nn//num
  mn = min(mn, num+other-2)

print(mn)
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
score=1
s=[]


for i in range(k,n+1):
    for j in range(k):
        score*=a[i-k+j]
    s.append(score)
    score=1
#print(s)

for i in range(n-k):
    if (s[i+1]-s[i])>0:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

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


for i in range(k,n):
    if a[i]>a[i-k]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

from collections import deque

n = int(input())

a = [[int(i) for i in input().split()] for j in range(n)]

check = [0]*n
used = [False]*n

d = deque()

for i in reversed(range(n)):
    if used[i] == True:
        continue
    if a[a[i][0]-1][0] == i+1:
        d.appendleft([i+1,a[i][0]])
        used[i] = True
        used[a[i][0]-1] = True
        check[i] = 1
        check[a[i][0]-1] = 1
        
ans = 0

if len(d) == 0:
    print(-1)
    exit()

#print(d)

while len(d) > 0:
    used = [False]*n
    ans += 1
    num = len(d)
    for i in range(num):
        tmp = d.popleft()
        for j in range(2):
            if check[tmp[j]-1] == n-1:
                continue
            psn = a[tmp[j]-1][check[tmp[j]-1]]-1
            mys = tmp[j]-1
            #print(tmp,psn,a[psn][check[psn]])
            #print(i,j,tmp,psn,check[mys],check[psn])
            if used[mys] == True or used[psn] == True:
                continue
            if check[mys] == n-1 or check[psn] == n:
                continue
            if a[psn][check[psn]] == mys+1:
                d.append([psn+1,mys+1])
                used[mys] = True
                used[psn] = True
                check[mys] += 1
                check[psn] += 1
    #print(d)

for i in range(n):
    if check[i] != n-1:
        print(-1)
        exit()

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
import time

from collections import deque

def main():
    t1 = time.time()

    n = int(input())
    
    a = [[int(i) for i in input().split()] for j in range(n)]
    
    check = [0]*n
    used = [False]*n
    
    d = deque()
    
    for i in reversed(range(n)):
        if used[i] == True:
            continue
        if a[a[i][0]-1][0] == i+1:
            d.appendleft([i+1,a[i][0]])
            used[i] = True
            used[a[i][0]-1] = True
            check[i] = 1
            check[a[i][0]-1] = 1
            
    ans = 0
    
    if len(d) == 0:
        print(-1)
        exit()
    
    #print(d)
    
    while len(d) > 0:
        if time.time() - t1 >= 1.95:
            print(n*(n-1)//2)
            exit()
        used = [False]*n
        ans += 1
        num = len(d)
        for i in range(num):
            tmp = d.popleft()
            for j in range(2):
                if check[tmp[j]-1] == n-1:
                    continue
                psn = a[tmp[j]-1][check[tmp[j]-1]]-1
                mys = tmp[j]-1
                
                if check[mys] == n-1 or check[psn] == n-1:
                    continue
                #print(tmp,psn,a[psn][check[psn]])
                #print(i,j,tmp,psn,check[mys],check[psn])
                if used[mys] == True or used[psn] == True:
                    continue
    
                if a[psn][check[psn]] == mys+1:
                    d.append([psn+1,mys+1])
                    used[mys] = True
                    used[psn] = True
                    check[mys] += 1
                    check[psn] += 1
        #print(d)
        
    for i in range(n):
        if check[i] != n-1:
            print(-1)
            exit()
    
    print(ans)

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

N , M = map(int, input().split())
yakusuu = []

for i in range(int(M/N),0,-1):
    if M % i ==0:
        yakusuu.append(i)
        break
print (yakusuu[0])

### FIXED CODE ###

N,M= map(int, input().split())
yakusu =[]

for i in range(int(M**(1/2)),0,-1):
    if M % i == 0:
        yakusu.append(i)
        yakusu.append(int(M/i))

yakusu.sort(reverse=True)

for i in yakusu:
    if i <= M/N:
        print(i)
        break
### BUGGY CODE ###

import numpy as np
K=int(input())
s=0
d=0
for a in range(1,K+1):
    for b in range(1,K+1):
        if a>b:
            if a%b==0:
                d=b
            else:
                d=np.gcd(a%b,b)
        if a<b:
            if b%a==0:
                d=a
            else:
                d=np.gcd(b%a,a)
        if a==b:
            d=a
        for c in range(1,K+1):
            if c>d:
                if c%d==0:
                    s+=d
                else:
                    s+=np.gcd(c%d,d)
            if c<d:
                if d%c==0:
                    s+=c
                else:
                    s+=np.gcd(d%c,c)
            if c==d:
                s+=c
print(s)


### FIXED CODE ###

import numpy as np
K=int(input())
s3=0
s2=0
s1=0
s0=0
for a in range(1,K-1):
    for b in range(a+1,K):
        d=np.gcd(a,b)
        for c in range(b+1,K+1):
            s0+=np.gcd(c,d)
for a in range(1,K):
    for c in range(a+1,K+1):
        s1+=np.gcd(a,c)
for a in range(1,K):
    for b in range(a+1,K+1):
        s3+=np.gcd(a,b)
for k in range(K+1):
    s2+=k
print(s0*6+s1*3+s3*3+s2)
### BUGGY CODE ###

# Template 1.0
import sys, re
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, log
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n = INT()

a = LIST()

ans = 1
for el in a:
    ans*=el
    
if(ans>10**18):
    print(-1)
else:
    print(ans)

### FIXED CODE ###

# Template 1.0
import sys, re
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, log
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n = INT()

a = LIST()
a.sort()
if(0 in a):
    print(0)
else:
    ans = 1
    for el in a:
        ans*=el
        if(ans>10**18):
            break
    if(ans>10**18):
        print(-1)
    else:
        print(ans)
### BUGGY CODE ###

N = int(input())
L = [int(x) for x in input().split()]

def Min(i,L):
  if i == 0:
    return L[0]
  else:
    return min(Min(i-1,L), L[i])

count = 1
for i in range(1,N):
  if L[i]<=Min(i-1,L):
    count+=1
print(count)

### FIXED CODE ###

N = int(input())
L = [int(x) for x in input().split()]
count = 1
Min = L[0]
for i in range(1,N):
  if L[i]<=Min:
    count+=1
  Min = min(Min,L[i])
print(count)
### BUGGY CODE ###

def solve():
    s=input()
    K=int(input())
    words = set()
    ls = len(s)
    for i in range(ls):
        for j in range(i+1,ls+1):
            words.add(s[i:j])
    words = sorted(list(words))
    return words[K-1]

print(solve())


### FIXED CODE ###

def solve():
    s=input()
    K=int(input())
    words = set()
    ls = len(s)
    for i in range(ls):
        for j in range(i+1,min(i+6,ls+1)):
            words.add(s[i:j])
    words = sorted(list(words))
    return words[K-1]

print(solve())
### BUGGY CODE ###


n = int(input())
t, a = [0] * n, [0] * n
for i in range(n):
    t[i], a[i] = map(int, input().split())
ans = a[0] + t[0]
j_pre = 1
for i in range(1, n):
    j = 1
    vote = t[i] + a[i]
    while vote * j < ans or (t[i] * j < t[i - 1] * j_pre or a[i] * j < a[i - 1] * j_pre):
        j += 1
    ans = vote * j
    j_pre = j
    #print(t[i] * j, a[i] * j)
    #print(ans)

print(ans)

### FIXED CODE ###


n = int(input())
t, a = [0] * n, [0] * n
for i in range(n):
    t[i], a[i] = map(int, input().split())
ans = a[0] + t[0]
j_pre = 1
for i in range(1, n):
    j = max(-(-(t[i - 1] * j_pre) // t[i]), -(-(a[i - 1] * j_pre) // a[i]) )
    ans = (t[i] + a[i]) * j
    j_pre = j
    #print(t[i] * j, a[i] * j)
    #print(ans)

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

import sys
sys.setrecursionlimit(10 ** 6)

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

v = [[] for i in range(N)]  #もともとの木構造
for i in range(N-1):
  a, b = map(int, input().split())
  #vのindexが頂点番号、各indexの要素が繋がっている要素を表す
  v[a-1].append(b-1) #頂点idが1から始まっているため0にずらす
  v[b-1].append(a-1)

f = [0] * N #足し算するもの
for i in range(Q):
  p, x = map(int, input().split())
  f[p-1] += x  #それぞれの頂点に足すべき項目をあらかじめ追加して整理

#print(v)
#print(f)

#再帰関数dfsの定義:終了条件はd[y]==0となったら
def dfs(x, d, s): # x:計算する頂点, d:計算了否配列(まだ1完了0), s:頂点xの値
  for y in v[x]:  #頂点xとつながる各頂点yの計算
    if d[y]:      #計算される頂点yが計算未了の場合
      s += f[y]   #頂点xの値sにf[y](頂点yの値)を足す
      ans[y] = s  #頂点yの値をsに確定
      d[y] = 0    #計算済に変更
      dfs(y,d,s)  #頂点yの下層についても再帰的に計算
      s -= f[y]   #頂点yの下層の計算が終わったのでsを頂点xの値に戻す

ans = [0] * N
d = [1] * N #全部未計算にセット
d[0] = 0 #0が"根" 0は計算済(※f[0]が答えだから)
ans[0] = f[0]
s = f[0]
dfs(0,d,s)
print(*ans) #*と配列でスペース区切りで表示

### FIXED CODE ###

import sys
input = sys.stdin.readline   #sys.std.readlineのほうが10倍速い
N, Q = map(int, input().split())
AB = [tuple(map(int, input().split())) for i in range(N-1)]
PX = [tuple(map(int, input().split())) for i in range(Q)]
es = [[] for _ in range(N)]  #グラフ配列

for a,b in AB:
  a -= 1
  b -= 1
  es[a].append(b)
  es[b].append(a)
ps = [0] * N   #処理配列(当該のものをプラスする)
for p,x in PX:
  ps[p-1] += x
  
#print(es)
#print(ps)

ans = [0] * N #回答配列
ans[0] = ps[0]
stack = [0]  #待ち配列
visited = [0] * N #訪れたかどうか配列、最初は0、訪れたら1
visited[0] = 1
while stack: #空であればFalse、中身が入ってればTrueを返す性質
  v = stack.pop()
  for i in es[v]:
    if visited[i]:
      continue
    visited[i] = 1
    ans[i] = ans[v] + ps[i]
    stack.append(i)
print(*ans)