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

from collections import deque
n, m = map(int, input().split())
q = deque()
t = {i: set() for i in range(1, n + 1)}
v = [0] * n
p = [0] * n

for _ in range(m):
    a, b = map(int, input().split())
    t[a].add(b)
    t[b].add(a)

v[0] = 1
for i in t[1]:
    p[i - 1] = 1
    q.append(i)
while q:
    next = q.popleft()
    v[next -1] = 1
    for i in t[next]:
        if v[i - 1] == 0:
            q.append(i)
            if p[i - 1] == 0:
                p[i - 1] = next
print('Yes')
print(*p[1:], sep='\n')

### FIXED CODE ###

from collections import deque
n, m = map(int, input().split())
q = deque()
t = {i: set() for i in range(1, n + 1)}
v = [-1] * n

for _ in range(m):
    a, b = map(int, input().split())
    t[a].add(b)
    t[b].add(a)
q.append(1)
v[0] = 1
while q:
    next = q.popleft()
    for i in t[next]:
        if v[i - 1] == -1:
            q.append(i)
            v[i - 1] = next
print('Yes')
print(*v[1:], sep='\n')
### BUGGY CODE ###

N=int(input())

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return len(lower_divisors + upper_divisors[::-1])

x=0
for c in range(1,N):
    x+=make_divisors(N-c)
print(x)

### FIXED CODE ###

n = int(input())
ans = 0
for a in range(1, n):
  ans += (n - 1) // a
print(ans)
### BUGGY CODE ###

H, W = map(int, input().split())
sh, sw = map(int, input().split())
gh, gw = map(int, input().split())

sh += 1
sw += 1
gh += 1
gw += 1

S = [0]*(H+4)
S[0] = '*'*(W+4)
S[1] = '*'*(W+4)
S[-2] = '*'*(W+4)
S[-1] = '*'*(W+4)
for h in range(2,H+2):
  S[h] = '**' + input() + '**'

visited = [[float('inf')]*(W+4) for _ in range(H+4)]
dh1 = [0,1,0,-1]
dw1 = [1,0,-1,0]
dh2 = [2,2,2,2,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2]
dw2 = [-2,-1,0,1,2,-2,-1,1,2,-2,2,-2,-1,1,2,-2,-1,0,1,2]

from collections import deque
d = deque()
visited[sh][sw] = 0
d.append((sh,sw,0))

while len(d)>0:
  h,w,cnt = d.popleft()
  for i in range(4):
    h1 = h+dh1[i]
    w1 = w+dw1[i]
    if S[h1][w1]=='.':
      if visited[h1][w1]>cnt:
        visited[h1][w1]=cnt
        d.append((h1,w1,cnt))
  for i in range(20):
    h2 = h+dh2[i]
    w2 = w+dw2[i]
    if S[h2][w2]=='.':
      if visited[h2][w2]>cnt+1:
        visited[h2][w2]=cnt+1
        d.append((h2,w2,cnt+1))
ans = visited[gh][gw] if visited[gh][gw]<float('inf') else -1
print(ans)

### FIXED CODE ###

H, W = map(int, input().split())
sh, sw = map(int, input().split())
gh, gw = map(int, input().split())

sh += 1
sw += 1
gh += 1
gw += 1
s = sh*(W+4)+sw
g = gh*(W+4)+gw
S = [0]*(H+4)
S[0] = '*'*(W+4)
S[1] = '*'*(W+4)
S[-2] = '*'*(W+4)
S[-1] = '*'*(W+4)
for h in range(2,H+2):
  S[h] = '**' + input() + '**'

visited = [10**7]*((W+4)*(H+4))
dh1 = [0,1,0,-1]
dw1 = [1,0,-1,0]
dh2 = [2,2,2,2,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2]
dw2 = [-2,-1,0,1,2,-2,-1,1,2,-2,2,-2,-1,1,2,-2,-1,0,1,2]

from collections import deque

d = deque()
visited[s] = 0
d.append(s)
ans = 10**8
while len(d)>0:
  a = d.popleft()
  h,w = divmod(a,W+4)
  cnt = visited[a]
  if ans<=cnt:
    continue
  for i in range(4):
    h1 = h+dh1[i]
    w1 = w+dw1[i]
    a1 = h1*(W+4)+w1
    if (h1,w1)==(gh,gw):
      ans = min(ans,cnt)
    if S[h1][w1]=='.':
      if visited[a1]>cnt:
        visited[a1]=cnt
        d.appendleft(a1)
  for i in range(20):
    h2 = h+dh2[i]
    w2 = w+dw2[i]
    a2 = h2*(W+4)+w2
    if (h2,w2)==(gh,gw):
      ans = min(ans,cnt+1)
    if S[h2][w2]=='.':
      if visited[a2]>cnt+1:
        visited[a2]=cnt+1
        d.append(a2)
if ans==10**8:
  ans = -1
print(ans)
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()

l_L,r_L = [],[]

for val in range(q):
    l,r = map(int,input().split())
    l_L.append(l-1)
    r_L.append(r-1)

s = list(s)
s.append(" ")

for val in range(n+1):
    if s[val] == "A" and s[val+1] == "C":
        s[val] = "*"


for val in range(q):
    tmp = s[l_L[val]:r_L[val]]
    print(tmp.count("*"))

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

from collections import deque
from copy import deepcopy, copy
dy = [-1, 0, 0, 1]
dx = [0, -1, 1, 0]
N = 3
def MAIN():
    MAP = sum([input().split() for _ in range(N)], [])
    y0, x0 = divmod(MAP.index("0"), N)
    goal = ['1', '2', '3', '4', '5', '6', '7', '8', '0']
    ans = 0
    dp = deque([[y0, x0, 0, MAP]])
    LOG = [MAP]
    while dp:
        y, x, cnt, M = dp.popleft()
        if M == goal:
            print(cnt)
            break
        cnt += 1
        yx = y * N + x
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= ny < N and 0 <= nx < N:
                CM = deepcopy(M)
                nyx = ny * N + nx
                CM[yx], CM[nyx] = CM[nyx], CM[yx]
                if not CM in LOG:
                    dp.append([ny, nx, cnt, CM])
                    LOG.append(CM)
MAIN()



### FIXED CODE ###

from collections import deque
N = 3
m = {8: {7, 5}, 7: {8, 6, 4}, 6: {7, 3}, 5: {8, 4, 2}, 4: {7, 5, 3, 1}, 3: {6, 4, 0}, 2: {5, 1}, 1: {4, 2, 0},
     0: {3, 1}}
goal = 123456780
def g(i, j, a):
    t = a // (10 ** j) % 10
    return a - t * (10 ** j) + t * (10 ** i)
def solve():
    MAP = "".join(input().replace(" ", "") for _ in range(N))
    zero = 8 - MAP.find("0")
    start = int(MAP)
    if start == goal:
        return 0
    dp = deque([(0, start, zero, 1), (0, goal, 0, 0)])
    TABLE = {start: (1, 0), goal: (0, 0)}
    while dp:
        cnt, M, yx, flg = dp.popleft()
        cnt += 1
        for nyx in m[yx]:
            key = g(yx, nyx, M)
            if key in TABLE:
                if TABLE[key][0] != flg:
                    return TABLE[key][1] + cnt
                continue
            TABLE[key] = (flg, cnt)
            dp.append((cnt, key, nyx, flg))
def MAIN():
    print(solve())
MAIN()
### BUGGY CODE ###

#substring列挙したらTLE(部分点)
s = input()
k = int(input())
s_set_sort = sorted(set(s))

li = []
count = 0
while count < k:
    s_head = s_set_sort.pop(0)
    for i in range(len(s)):
        if s[i] == s_head:
            for j in range(len(s)-i):
                if s[i:i+j+1] not in li:
                    count += 1
                    li.append(s[i:i+j+1])
li.sort()
print(li[k-1])

### FIXED CODE ###

#substring列挙したらTLE(部分点)
s = input()
k = int(input())
s_set_sort = sorted(set(s))

li = []
count = 0
while count < k:
    s_head = s_set_sort.pop(0)
    for i in range(len(s)):
        if s[i] == s_head:
            for j in range(k):
                if s[i:i+j+1] not in li:
                    count += 1
                    li.append(s[i:i+j+1])
li.sort()
print(li[k-1])
### BUGGY CODE ###

def main():
    import sys
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline
    N = int(input())
    A = [int(x) for x in input().strip().split()]
    ans = 0
    for i, a in enumerate(A[:-1]):
        if a > N:
            continue
        api = a + i
        for j in range(a-1, N):
            if api + A[j] == j:
                ans += 1

    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    from collections import Counter
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline
    N = int(input())
    A = [int(x) for x in input().strip().split()]
    j_Aj = Counter([j-Aj for j, Aj in enumerate(A, start=1)])
    ans = 0
    for i, a in enumerate(A[:-1], start=1):
        if a > N:
            continue
        ans += j_Aj[a+i]

    print(ans)

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

import sys
import numpy as np
from math import ceil as C, floor as F, sqrt
from collections import defaultdict as D, Counter as CNT
from functools import reduce as R
 
ALP = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
alp = 'abcdefghijklmnopqrstuvwxyz'
def _X(): return sys.stdin.readline().rstrip().split(' ')
def _S(ss): return tuple(ss) if len(ss) > 1 else ss[0]
def S(): return _S(_X())
def Ss(): return list(S())
def _I(ss): return tuple([int(s) for s in ss]) if isinstance(ss, tuple) else int(ss)
def I(): return _I(S())
def _Is(ss): return list(ss) if isinstance(ss, tuple) else [ss]
def Is(): return _Is(I())

_, k = Is()
towns = [i-1 for i in Is()]

now = 0
seen = [0]

while k > 0:
  k -= 1
  now = towns[now]
  
  if now not in seen:
    seen.append(now)
  else:
    seen = seen[seen.index(now):]
    break

if k == 0:
  print(1 + now)
else:
  print(1 + (seen[k % len(seen)]))
  

### FIXED CODE ###

import sys
import numpy as np
from math import ceil as C, floor as F, sqrt
from collections import defaultdict as D, Counter as CNT
from functools import reduce as R
 
ALP = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
alp = 'abcdefghijklmnopqrstuvwxyz'
def _X(): return sys.stdin.readline().rstrip().split(' ')
def _S(ss): return tuple(ss) if len(ss) > 1 else ss[0]
def S(): return _S(_X())
def Ss(): return list(S())
def _I(ss): return tuple([int(s) for s in ss]) if isinstance(ss, tuple) else int(ss)
def I(): return _I(S())
def _Is(ss): return list(ss) if isinstance(ss, tuple) else [ss]
def Is(): return _Is(I())

_, k = Is()
towns = [i-1 for i in Is()]

now = 0
seen = [0]
seenx = {0: 0}

while k > 0:
  k -= 1
  now = towns[now]
  
  if now not in seenx:
    seenx[now] = len(seen)
    seen.append(now)
  else:
    seen = seen[seenx[now]:]
    break

if k == 0:
  print(1 + now)
else:
  print(1 + (seen[k % len(seen)]))
### BUGGY CODE ###

K, S = map(int, input().split())
c = 0
for x in range(K + 1):
    for y in range(K + 1):
        for z in range(K + 1):
            if x + y + z == S:
                c += 1
print(c)

### FIXED CODE ###

K, S = map(int, input().split())
c = 0
for x in range(K + 1):
    for y in range(x + 1):
        if x + y > S:
            break
        z = S - x - y
        if z >= 0 and z < y + 1:
            if x != y and x!= z and y!= z:
                c += 6
            elif x == y and x == z and y == z:
                c += 1
            else:
                c += 3
print(c)
### BUGGY CODE ###

import collections

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

c=collections.Counter(A)
kazu=list(c.values())
kazu1=[i*(i-1)/2 for i in kazu if i>1]

for k in range(N):
    sub=c[A[k]]-1
    print(int(sum(kazu1)-sub))

### FIXED CODE ###

import collections
import numpy as np

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

c=collections.Counter(A)
kazu=list(c.values())
a=np.array(kazu)
sn=a*(a-1)/2
s=sum(sn)
for k in range(N):
    sub=c[A[k]]-1
    print(int(s-sub))
### BUGGY CODE ###

n, q = map(int, input().split())

class Node:
    def __init__(self, root):
        self.root = root
        self.children = []
        self.val = 0

    def set_root(self, root_node):
        self.root = root_node

    def add_child(self, child_node):
        self.children.append(child_node)
        if self.root is not None:
            self.root.add_child(child_node)

nodes = [Node(None)] * n

for i in range(1, n):
    a, b = map(int, input().split())
    a_node = nodes[a - 1]
    nodes[b - 1] = Node(a_node)
    a_node.add_child(nodes[b - 1])

for j in range(q):
    p, x = map(int, input().split())
    node = nodes[p - 1]
    node.val += x
    children = node.children
    for child in children:
        child.val += x

res = []
for node in nodes:
    res.append(str(node.val))
print(" ".join(res))

### FIXED CODE ###

n, q = map(int, input().split())

children_map = [None] * n
vals = [0] * n

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

for j in range(q):
    p, x = map(int, input().split())
    vals[p - 1] += x

res = []
for i in range(n):
    parent = children_map[i]
    if parent is not None:
        vals[i] += vals[parent]
    res.append(str(vals[i]))

print(" ".join(res))
### BUGGY CODE ###

def main():
    n=int(input())
    a=sorted(map(int,input().split()), reverse=True)
    ans=0
    mod=10**9+7
    for i in range(n-1):
        if a[i] == 0:
            break
        for j in range(i+1,n):
            if a[j] == 0:
                break
            ans += a[i]*a[j]%mod
    print(ans%mod)

if __name__ == '__main__':
    main()

### FIXED CODE ###

from itertools import accumulate
def main():
    mod=10**9+7
    n=int(input())
    a=list(map(int,input().split()))
    aa=[0]+list(accumulate(a))
    ans=0
    for i in range(n-1):
        ans += a[i]*(aa[-1]-aa[i+1])%mod
    print(ans%mod)

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

def is_integer(n):
    try:
        float(n)
    except ValueError:
        return False
    else:
        return float(n).is_integer()

N = int(input())
for i in range(1, N+1):
    if i < 6:
        print(0)
        continue
    cnt = 0
    for x in range(1, 45):
        for y in range(1, 45):
             D = (((x+y)**2 - 4*(x**2+y**2+x*y-i)) ** (1/2))
             if ((x+y)**2 - 4*(x**2+y**2+x*y-i)) > 0 :
                 Z = (-(x+y) + D) / 2
                 if is_integer(Z) and Z>0:
                     cnt += 1
    print(cnt)

### FIXED CODE ###

N = int(input())
lis = [0]*N
for x in range(1, 100):
    for y in range(1, 100):
        for z in range(1, 100):
            ans = x**2 + y**2 + z**2 + x*y + y*z + z*x -1
            if ans >= N:
                pass
            else:
                lis[ans] += 1
for i in range(N):
    print(lis[i])
### BUGGY CODE ###

n=int(input())
a=list(map(int, input().split()))
import collections
import math
def combinations_count2(n):
    if(n<=1):
        answer=0
    else:
        answer=n*(n-1)/2
    return answer

table=collections.Counter(a)
keytable=collections.Counter(a).keys()
c=[]

for key in keytable:
    c.append(table[key])
#print(c)
ca=[]
for j in range(len(c)):
    ca.append(combinations_count2(c[j]))
#print(ca)
sums=sum(ca)
#print(sum)
#print(keytable)
#print(table)
for i in range(len(a)):
    keynum=list(keytable).index(a[i])
    answer=sums-ca[keynum]+combinations_count2(c[keynum]-1)
    print(int(answer))

### FIXED CODE ###

n=int(input())
a=list(map(int, input().split()))
import collections
import math
def combinations_count2(n):
    if(n<=1):
        answer=0
    else:
        answer=n*(n-1)/2
    return answer

table=collections.Counter(a)
keytable=table.keys()
sums=0
for value in table.values():
    sums+=combinations_count2(value)
#print(ca)
#print(sum)
#print(keytable)
#print(table)
for i in range(len(a)):
    answer=sums-table[a[i]]+1
    print(int(answer))
### BUGGY CODE ###

n=int(input())
a = list(map(int,input().split()))
for i in range (n):
  for j in range(n):
    if i != j:
      if a[i] == a[j]:
        print('NO')
        exit()
print('YES')

### FIXED CODE ###

n=int(input())
a = list(map(int,input().split()))
a.sort()
for i in range (n-1):
  if a[i] == a[i+1]:
    print('NO')
    exit()
print('YES')
### BUGGY CODE ###

import os

def main():
	x = int(input())
	b = 0 
	while(x + b**5 != 1):
		b -= 1
	print(1,b)
			


if __name__ == "__main__":
	main()


### FIXED CODE ###

import os

def main():
	x = int(input())
	a,b = 0,0
	for i in range(119, -118, -1):
		for j in range(118, -119, -1):
			if i**5 - j**5 == x:
				a = i
				b = j
				break
	print(a,b)				


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

import collections
N, K = map(int, raw_input().split())
P_list = list()
for i in range(N):
    P_list.append(raw_input()[0])
    C_list = collections.Counter(P_list).values()

# clean
C_list = [c for c in C_list if c > 0]
C_list.sort(reverse=True)

res = 0
while True:
    if len(C_list) >= K:
        for i in range(K):
            C_list[i] -= 1
        res += 1
        C_list = [c for c in C_list if c > 0]
        C_list.sort(reverse=True)
    else:
        break
print res

### FIXED CODE ###

import numpy as np
C_vec = np.zeros(26)
N, K = map(int, raw_input().split())

for i in range(N):
    C_vec[ord((raw_input()[0])) - ord('A')] += 1


while True:
    m = int(C_vec.sum() / K)
    C_vec = np.minimum(C_vec, m)
    m_next = int(C_vec.sum() / K)
    if m_next == m:
        break
    else:
        m = m_next

print m
### BUGGY CODE ###

# -*- coding: utf-8 -*-

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

keep_val = 0
check = 0
for i in range(n-k+1):
    ss = sum(p[i:i+k])
    if keep_val < ss:
        check = i
        keep_val = ss

#print(p[check:check+k])

ans = 0
for i in p[check:check+k]:
    ans += (i+1)/2
print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
 
n, k = map(int, input().split())
p = list(map(int, input().split()))

summation = 0
exp_val = []
for i in range(n):
    summation += (p[i]+1)/2
    exp_val.append(summation)
exp_val.insert(0, 0)
#print(exp_val)

ans = 0
for i in range(n-k+1):
    m = exp_val[k+i] - exp_val[i]
    ans = max(ans, m)

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

N, Q = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(N - 1)]
px = [list(map(int, input().split())) for _ in range(Q)]

class Tree:
  C = {}
  N, D = None, None
  def __init__(s, num):
    s.N = num
  def setC(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 exe(s):
    L = [-1] * N
    A = [0] * N
    for p, x in px:
      p -= 1
      A[p] += x
    S = [0]
    while S != []:
      t = S.pop()
      L[t] = 1
      for i in s.C[t]:
        if L[i] == -1:
          L[i] = 1
          A[i] += A[t]
          S.append(i)
    for i in range(N):
      print(A[i], end = " ")

T = Tree(N)
for a, b in ab:
  a -= 1
  b -= 1
  T.setC(a, b)

T.exe()



### FIXED CODE ###

import sys
input = sys.stdin.readline

N, Q = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(N - 1)]
px = [list(map(int, input().split())) for _ in range(Q)]

class Tree:
  C = {}
  N, D = None, None
  def __init__(s, num):
    s.N = num
  def setC(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 exe(s):
    L = [-1] * N
    A = [0] * N
    for p, x in px:
      p -= 1
      A[p] += x
    S = [0]
    while S != []:
      t = S.pop()
      L[t] = 1
      for i in s.C[t]:
        if L[i] == -1:
          L[i] = 1
          A[i] += A[t]
          S.append(i)
    for i in range(N):
      print(A[i], end = " ")

T = Tree(N)
for a, b in ab:
  a -= 1
  b -= 1
  T.setC(a, b)

T.exe()
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
dlt=0
while(len(a)):
  i=a[0]
  j=a.count(i)
  if(j>i):dlt+=j-i
  elif(i>j):dlt+=j
  while(i in a):a.remove(i)
print(dlt)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
dlt=0
push=0
a.sort()
k=0
while(1):
  i=a[k+push]
  if(i>n):
    dlt+=1
    push+=1
  else:
    j=a.count(i)
    push+=j
    if(j>i):dlt+=j-i
    elif(i>j):dlt+=j
  if(k+push>=n):break
print(dlt)
### BUGGY CODE ###

n, m = map(int, input().split())
a = [int(i) for i in input().split()]

a.sort(reverse=True)

for _ in range(m):
    a[0] = a[0] // 2
    
    #swap
    rank = 0
    a0 = a[0]
    for i in range(1, n):
        if a[i] <= a0:
            break
        else:
            a[i-1] = a[i]
            a[i] = a0

print(sum(a))

### FIXED CODE ###

n, m = map(int, input().split())
a = [int(i) for i in input().split()]

#%%

# n, m, a = 3, 3, [1,2,3,4,7,9, 10,8,16,14]

#%%
max_heap = [a[0]]
#%%
def add_heap(array, number):
    array.append(number)

    def swap(array, number, idx):
        if idx == 1:
            return array[idx-1]

        ai = array[idx-1]
        target_idx = (idx//2)
        target = array[target_idx-1]
        
        if ai >= target:
            array[idx-1], array[target_idx-1] =  target, ai

            number = swap(array, number, target_idx)
        else:
            return array[idx-1]

    return swap(array, number, len(array))


#%%
for ai in a[1:]:
    add_heap(max_heap, ai)

#%%
for _ in range(m):
    
    #half
    max_heap[0] //= 2
    
    def sort_heap(array, number, idx):
        top = number
        left_idx = idx*2
        right_idx = idx*2 + 1
        
        if left_idx > len(array):
            left = -1
        else:
            left = array[left_idx - 1]

        if right_idx > len(array):
            right = -1
        else:        
            right = array[right_idx - 1]

        if top >= left and top >= right:
            return array
        elif left > right:
            array[idx-1], array[left_idx-1] = left, top
            sort_heap(array, top, left_idx)
        else:
            array[idx-1], array[right_idx-1] = right, top
            sort_heap(array, top, right_idx)

    sort_heap(max_heap, max_heap[0], 1)

#%%
print(sum(max_heap))

#%%
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline

L = []
sums = []
ans = []

def main():
    global L,ans,sums
    N,Q= map(int, input().split())
    ans = [0]*(N+1)
    sums = [0]*(N+1)
    L=[]
    [L.append([])for _ in range(N+1)]
    for _ in range(N-1):
        A,B = map(int, input().split())
        L[A].append(B)
        L[B].append(A)
    for _ in range(Q):
        p,x = map(int, input().split())
        sums[p]+=x
    dfs(1,0)

    print(*ans[1:N+1])


def dfs(p,pre):
    global ans
    ans[p] = ans[pre] + sums[p]
    for ki in L[p]:
        if pre==ki:
            continue    
        dfs(ki,p)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline

L = []
sums = []
ans = []

def main():
    global L,ans,sums
    N,Q= map(int, input().split())
    ans = [0]*(N+1)
    sums = [0]*(N+1)
    L=[]
    [L.append([])for _ in range(N+1)]
    for _ in range(N-1):
        A,B = map(int, input().split())
        L[A].append(B)
        L[B].append(A)
    for _ in range(Q):
        p,x = map(int, input().split())
        sums[p]+=x
    dfs(1,0)

    print(*ans[1:N+1])


def dfs(p,pre):
    global ans
    ans[p] = ans[pre] + sums[p]
    for ki in L[p]:
        if pre==ki:
            continue    
        dfs(ki,p)


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

N = int(input())
s = list(map(int,input().split()))
m = list(map(int,input().split()))
l = list(map(int,input().split()))
count = 0
for sitem in s:
  for mitem in m:
    for litem in l:
      if sitem < mitem and mitem < litem:
        count += 1
print (count)

### FIXED CODE ###

import bisect

N = int(input())
s = sorted(list(map(int,input().split())))
m = sorted(list(map(int,input().split())))
l = sorted(list(map(int,input().split())))
count = 0
for mitem in m:
  count += bisect.bisect_left(s,mitem)*(N-bisect.bisect_right(l,mitem))
print (count)
### BUGGY CODE ###

s = int(input())

for x in range(min(10**9, s), -1, -1):
  for y in range(x, -1, -1):
    t = s + x*y
    if t <= x*y:
      break
    if t - int(t) == 0:
      if t % 2 == 0 and t / 2 <= 10**9:
        print('{0} {1} {2} {3} {4} {5}'.format(0, 0, x, 2, t//2, y))
        quit()
      else:
        for i in range(1, x, 2):
          if t % i == 0 and t // i <= 10**9:
            print('{0} {1} {2} {3} {4} {5}'.format(0, 0, x, i, t//i, y))
            quit()

### FIXED CODE ###

s = int(input())

a = s // 10**9 + 1
b = 10**9 - s % 10**9
if a > 10**9:
  a -= 1
  b -= 10**9

assert abs(a * 10**9 - b) == s

print(" ".join(map(str, [0, 0, a, 1, b, 10**9])))
### BUGGY CODE ###

# P3:
def get_gcd(numbers):
    """Helper function to get GCD of list of numbers."""
    import math
    from functools import reduce

    if 1 in numbers:
        return 1

    # gcd is associative
    return reduce(lambda x, y: math.gcd(x, y), numbers)


def sum_of_gcd_tuples():
    K = int(input())
    total = 0
    for a in range(1, K + 1):
        for b in range(1, K + 1):
            for c in range(1, K + 1):
                total += get_gcd([a, b, c])

    print(total)


sum_of_gcd_tuples()

### FIXED CODE ###

def sum_of_gcd_tuples():
    from math import gcd
    K = int(input())
    total = 0

    for a in range(1, K + 1):
        for b in range(1, K + 1):
            for c in range(1, K + 1):
                total += gcd(gcd(a, b), c)

    print(total)


sum_of_gcd_tuples()