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

import sys
input = sys.stdin.readline

N,M,R = map(int,input().split())
r = list(map(int,input().split()))
S = [[]for i in range(N)]
for i in range(M):
    a,b,c = map(int,input().split())
    S[a-1].append([b-1,c])
    S[b-1].append([a-1,c])
d = [[float('inf')]*N for i in range(N)]
queue = []
for i in range(N):
    queue = [i]
    d[i][i] = 0
    while queue !=[]:
        hoge = [0]*(M)
        l = 0
        for q in queue:
            for next,c in S[q]:
                if d[i][next] > d[i][q]+c:
                    hoge[l] = next
                    l += 1
                    d[i][next] = d[i][q]+c
        queue = hoge[:l]
def func(x,l):
    if l == []:
        return 0
    ans = float('inf')
    for i in range(len(l)):
        ans =min(ans,func(l[i],l[:i]+l[i+1:]) + d[x-1][l[i]-1])
    return ans
ans = float('inf')
for i in r:
    ans = min(ans,func(i,r))
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N,M,R = map(int,input().split())
r = list(map(int,input().split()))
S = [[]for i in range(N)]
for i in range(M):
    a,b,c = map(int,input().split())
    S[a-1].append([b-1,c])
    S[b-1].append([a-1,c])
d = [[float('inf')]*N for i in range(N)]
queue = []
hoge = [0]*(M)
for i in range(N):
    queue = [i]
    d[i][i] = 0
    while queue !=[]:
        l = 0
        for q in queue:
            for next,c in S[q]:
                if d[i][next] > d[i][q]+c:
                    d[i][next] = d[i][q]+c
                    if not(next in hoge[:l]):
                        hoge[l] = next
                        l += 1
        queue = hoge[:l]
def func(x,l):
    if l == []:
        return 0
    ans = float('inf')
    for i in range(len(l)):
        ans =min(ans,func(l[i],l[:i]+l[i+1:]) + d[x-1][l[i]-1])
    return ans
ans = float('inf')
for i in r:
    ans = min(ans,func(i,r))
print(ans)
### BUGGY CODE ###

def resolve():
    N = int(input())
    P = list(map(int, input().split()))

    n = 0
    for i in range(N):
        for j in range(i):
            if P[i] > P[j]:
                break
        else:
            n += 1
    print(n)
    
resolve()


### FIXED CODE ###

def resolve():
    N = int(input())
    P = list(map(int, input().split()))

    n = 0
    x = 10 ** 20
    for i in range(N):
        if x >= P[i]:
            x = P[i]
            n += 1
    print(n)

resolve()
### BUGGY CODE ###

import sys
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
ct=[0 for i in range(n)]
fin=0
day=0
count=0
check=[-1,0]
while count!=n*(n-1)//2 and day<=10**5:
  if check[len(check)-2]==check[len(check)-1]:
    print(-1)
    sys.exit()
  L=[0 for i in range(n)]
  f1=0
  for i in range(n):
    if L[i]==0 and ct[i]!=n-1:
      x=l[i][ct[i]]
      if l[x-1][ct[x-1]]-1==i and L[x-1]==0:
        ct[i]+=1
        ct[x-1]+=1
        L[i]=1
        L[x-1]=1
        count+=1
  day+=1
  check.append(count)
if day>10**5:
  print(-1)
  sys.exit()
print(day)

### FIXED CODE ###

import sys
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
ct=[0 for i in range(n)]
fin=0
day=0
count=0
check=[0,0]
while count!=n*(n-1)//2 and day<=10**4:
  L=[0 for i in range(n)]
  f1=0
  for i in range(n):
    if L[i]==0 and ct[i]!=n-1:
      x=l[i][ct[i]]
      if l[x-1][ct[x-1]]-1==i and L[x-1]==0:
        ct[i]+=1
        ct[x-1]+=1
        L[i]=1
        L[x-1]=1
        count+=1
  day+=1
  check[0]=check[1]
  check[1]=count
  if check[0]==check[1]:
    print(-1)
    sys.exit()
if day>10**4:
  print(n*(n-1)//2)
  sys.exit()
print(day)
### BUGGY CODE ###

from collections import deque

Y, X = map(int,input().split())
# sy, sx = map(int, input().split())
# gy, gx = map(int, input().split())
sy,sx = 1,1
gy,gx = Y,X
s = [["#"]*(X+2) for _ in range(Y+2)]
for y in range(Y):
    s[y+1] = list("#"+input()+"#")
inf = 1e15
c = [[inf]*X for _ in range(Y)]
c[sy-1][sx-1] = 0
drs = [[-1,0],[1,0],[0,0],[0,-1],[0,1]]
q = deque([(sy-1, sx-1)])

while q:
    y,x = q.popleft()
    cost = c[y][x]
    for dx,dy in drs:
        x2 = x+dx
        y2 = y+dy
        if s[y2+1][x2+1] == "." and c[y2][x2] > cost:
            c[y2][x2] = cost+1
            q.appendleft((y2,x2))
if c[gy-1][gx-1] == inf:
    print("-1")
else:
    dots = 0
    for s1 in s:
        dots +=s1.count(".")
    print(dots-c[gy-1][gx-1]-1)

### FIXED CODE ###

H, W = map(int,input().split())
c = [["#"]*(W+2) for _ in range(H+2)]
dots = 0
for y in range(H):
    c[y+1] = "#",*list(input()),"#" 
    dots += c[y+1].count(".")
inf = H*W
m = [[inf]*W for _ in range(H)]
m[0][0] = 0
drs = [[-1,0],[1,0],[0,-1],[0,1]]

s = 0
yx = [[1, 1]]
notgoal = True
while notgoal and yx:
    yx2 = []
    s += 1
    for y,x in yx:
        for dy, dx in drs:
            x2 = x+dx
            y2 = y+dy
            if c[y2][x2] == "." and m[y2-1][x2-1] == inf:
                m[y2-1][x2-1] = s
                if (y2,x2) == (H,W):
                    notgoal = False
                else:
                    yx2.append([y2, x2])
    yx = yx2

if notgoal:
    print("-1")
else:
    print(dots-s-1)
### BUGGY CODE ###

N = int(input())
l = []
for i in range(N):
    x = input()
    if len(l) == 0:
        l.append(x)
    else:
        good = True
        for j in range(len(l)):
            if x == l[j]:
                good = False
                break
        if good:
            l.append(x)
print(len(l))


### FIXED CODE ###

import collections

N = int(input())
l = [input() for i in range(N)]
print(len(collections.Counter(l)))
### BUGGY CODE ###

S = list(input())
N = len(S)
C = [0] * N
L = [None] * N

C[0] = 0
L[0] = [S[0]]
for i in range(1, N):
    if len(L[i-1]) > 0 and L[i-1][-1] != S[i]:
        C[i] = C[i-1] + 2
        L[i] = L[i-1][:-1]
    else:
        C[i] = C[i-1]
        L[i] = L[i-1] + [S[i]]
print(C[-1])

### FIXED CODE ###

S = input()
red_count = S.count('0')
blue_count = S.count('1')
print(min(red_count, blue_count) * 2)
### BUGGY CODE ###

def f(n,m):
     a = list(map(int,input().split()))
     min_a = min(a)
     for i in range(m):
          b,c = map(int,input().split())
          if c>min_a:
               a += [c]*b
     a.sort()
     print(sum(a[len(a)-n:]))
 
n,m = map(int,input().split())
f(n,m)

### FIXED CODE ###

def f(n,m):
     a = list(map(int,input().split()))
     min_a = min(a)
     a = [(1,i) for i in a]
     b_c = [tuple(map(int,input().split())) for i in range(m)]
     a += b_c
     a.sort(key=lambda x:x[1])
     ans = 0
     while True:
          if n>a[-1][0]:
               ans += a[-1][0]*a[-1][1]
               n -= a[-1][0]
               a.pop()
          else:
               ans += a[-1][1]*n
               break
     print(ans)

n,m = map(int,input().split())
f(n,m)
### BUGGY CODE ###

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

N = int(input().strip())
S_list = [input().strip() for _ in range(N)]
#-----

def count_brackets(brackets):
    L = R = 0
    L_rev = R_rev = 0
    max_R = -float("inf")
    max_L = -float("inf")
    
    
    for i in range(len(brackets)):
        if brackets[i] == "(":
            L += 1
        else:  # brackets[i] == ")"
            R += 1
            max_R = max(max_R, R - L)
        
        if brackets[len(brackets)-1-i] == "(":
            L_rev += 1
            max_L = max(max_L, L_rev - R_rev)
        else:  # brackets[len(brackets)-1-i] == ")"
            R_rev += 1
    
    if max_L < 0: max_L = 0
    if max_R < 0: max_R = 0
    
    return max_L, max_R


tmp_cnt1 = []  #  the number of "("  >=  the number of ")"
tmp_cnt2 = []  #  the number of "("  <   the number of ")"

for S in S_list:
    cnt_L,cnt_R = count_brackets(S)

    if cnt_L == cnt_R == 0:
        continue
    
    if cnt_L >= cnt_R:
        tmp_cnt1.append( (cnt_L,cnt_R) )
    else:
        tmp_cnt2.append( (cnt_L,cnt_R) )


tmp_cnt1.sort(key=lambda x: x[1])
tmp_cnt2.sort(key=lambda x: -x[0])


sum_bracket = 0
flag = True

for cnt_L,cnt_R in (tmp_cnt1 + tmp_cnt2):
    sum_bracket -= cnt_R
    if sum_bracket < 0:  flag = False
    
    sum_bracket += cnt_L
    if sum_bracket < 0:  flag = False
    
    if flag == False:
        break


if (sum_bracket == 0) and flag:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

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

N = int(input().strip())
S_list = [input().strip() for _ in range(N)]
#-----

def count_brackets(brackets):
    L = R = 0
    L_rev = R_rev = 0
    max_R = -float("inf")
    max_L = -float("inf")
    
    
    for i in range(len(brackets)):
        if brackets[i] == "(":
            L += 1
        else:  # brackets[i] == ")"
            R += 1
            max_R = max(max_R, R - L)
        
        if brackets[len(brackets)-1-i] == "(":
            L_rev += 1
            max_L = max(max_L, L_rev - R_rev)
        else:  # brackets[len(brackets)-1-i] == ")"
            R_rev += 1
    
    if max_L < 0: max_L = 0
    if max_R < 0: max_R = 0
    
    return max_L, max_R


tmp_cnt1 = []  #  the number of "("  >=  the number of ")"
tmp_cnt2 = []  #  the number of "("  <   the number of ")"

for S in S_list:
    cnt_L,cnt_R = count_brackets(S)

    if cnt_L == cnt_R == 0:
        continue
    
    if cnt_L >= cnt_R:
        tmp_cnt1.append( (cnt_L,cnt_R) )
    else:
        tmp_cnt2.append( (cnt_L,cnt_R) )


tmp_cnt1.sort(key=lambda x: x[1])
tmp_cnt2.sort(key=lambda x: -x[0])


sum_bracket = 0
flag = True

for cnt_L,cnt_R in (tmp_cnt1 + tmp_cnt2):
    sum_bracket -= cnt_R
    if sum_bracket < 0:  flag = False
    
    sum_bracket += cnt_L
    if sum_bracket < 0:  flag = False
    
    if flag == False:
        break


if (sum_bracket == 0) and flag:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

N=int(input())
L=[]
for i in range(N):
  L.append(int(input()))
S=[]
M=[]
t=0
S=L[1:len(L)]
print(max(S))
M=L[0:len(L)-1]
for i in range(1,len(L)-1):
  S=L[0:i]
  M=L[i+1:len(L)]
  print(max(max(S),max(M)))
M=L[0:len(L)-1]
print(max(M))

### FIXED CODE ###

N=int(input())
L=[]
s,e,s1,e1,t=0,0,0,0,0
for i in range(N):
  L.append(int(input()))
s=L.index(max(L))
e=L[s]
L[s]=0
s1=L.index(max(L))
e1=L[s1]
for i in range(N):
  if i!=s:
    print(e)
  else:
    print(e1)
### BUGGY CODE ###

def main():
    # input
    import sys
    input = sys.stdin.readline
    MAX = 10**9+7

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

    li = [0]*61
    for i in a:
        for ind, j in enumerate(bin(i)[:1:-1]):
            li[ind] += int(j)

    ans = 0
    bit = 1
    for i in li:
        ans += bit * i * (n-i)
        bit *= 2
    print(ans%MAX)

    # calc



if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    MAX = 10**9+7

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

    li = [0]*61
    for i in a:
        for j in range(61):
            li[j] += i&1
            i >>= 1
    ans = 0
    bit = 1
    for i in li:
        ans += bit * i * (n-i)
        bit <<= 1
    print(ans%MAX)

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

n = int(input())
boss_list = list(map(int, input().split(' ')))

for i in range(n):
    print(boss_list.count(i + 1))


### FIXED CODE ###

n = int(input())
boss_list = list(map(int, input().split(' ')))

# for i in range(n):
#     print(boss_list.count(i + 1))

import collections
c = collections.Counter(boss_list)

for i in range(n):
    print(c[i + 1])
### BUGGY CODE ###

import bisect

n, m = map(int, input().split())
a_array = sorted([int(x) for x in input().split()])
bc_array = sorted([[int(x) for x in input().split()] for x in range(m)], key=lambda x: x[1], reverse=True)

candidate_replace_cnt = n
replace_sum = 0
replace_cnt = 0
for b, c in bc_array:
    if a_array[0] > c:
        break
    # 何枚入れられそうか
    num = bisect.bisect_left(a_array, c)
    # 入れ替えられる最大枚数が決まる
    candidate_replace_cnt = min(candidate_replace_cnt, num)
    # 全部入れ替えられる
    if candidate_replace_cnt <= b:
        replace_sum += c*candidate_replace_cnt
        a_array = a_array[candidate_replace_cnt:]
        break
    candidate_replace_cnt -= b
    replace_sum += c*b
    a_array = a_array[b:]
print(replace_sum + sum(a_array))


### FIXED CODE ###

import bisect

n, m = map(int, input().split())
a_array = sorted([int(x) for x in input().split()])
bc_array = sorted([[int(x) for x in input().split()] for x in range(m)], key=lambda x: x[1], reverse=True)

# 何枚入れ替えられるか
candidate_replace_cnt = n
for b, c in bc_array:
    if a_array[0] >= c or candidate_replace_cnt < 0:
        break
    for i in range(b):
        a_array.append(c)
    candidate_replace_cnt -= b
a_array.sort(reverse=True)
print(sum(a_array[:n]))
### BUGGY CODE ###

N,W=map(int,input().split())
listN=[[0 for i in range(W+1)] for k in range(N+1)]
for i in range(N):
  w,v=map(int,input().split())
  for k in range(1,W+1):
    if k>=w:
      listN[i+1][k]=max(listN[i][k],listN[i][k-w]+v)
    else:
      listN[i+1][k]=listN[i][k]     
ans=listN[N][W]
print(ans)

### FIXED CODE ###

N,W=map(int,input().split())
listN=[[0 for i in range(W+1)] for k in range(N+1)]
for i in range(N):
  w,v=map(int,input().split())
  for k in range(1,W+1):
    if k>=w:
      listN[i+1][k]=max(listN[i][k],listN[i][k-w]+v)
    else:
      listN[i+1][k]=listN[i][k]     
ans=listN[N][W]
print(ans)
### BUGGY CODE ###

from collections import deque
n,m = map(int,input().split())
p = [input() for _ in range(n)]
q = deque([])
a = 0
for i in range(n):
    for j in range(m):
        if p[i][j] == "#":
            q.append((i,j))
for i in range(n):
    for j in range(m):
        a = max(min(abs(i-a)+abs(j-b)for a,b in q),a)
print(a)

### FIXED CODE ###

from collections import deque
n,m = map(int,input().split())

maze = [list(input()) for _ in range(n)]

def bfs():
    dx = (1, 0, -1, 0)
    dy = (0, 1, 0, -1)
    d = [([-1]*m)for _ in range(n)]
    q = deque([])
    for i in range(n):
        for j in range(m):
            if maze[i][j] == "#":
                d[i][j] = 0
                q.append((i,j))
    a = 0

    while q:
        x,y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<= nx < n and 0<= ny < m and maze[nx][ny] != '#' and d[nx][ny] == -1:
                q.append((nx,ny))
                d[nx][ny] = d[x][y] +1
                a = max(a,d[nx][ny])
    return a

print(bfs())
### BUGGY CODE ###

#coding: utf-8
N, M = map(int, input().split())
points = list(map(int, input().split()))
points = sorted(points)
koma = [points[i+1] - points[i] for i in range(M-1)]
sum_ = 0
for i in range(M-N):
  sum_ += min(koma)
  koma.remove(min(koma))
print(sum_)

### FIXED CODE ###

#coding: utf-8
N, M = map(int, input().split())
points = list(map(int, input().split()))
if N > M:
  print(0)
else:
  points.sort()
  koma = [points[i+1] - points[i] for i in range(M-1)]
  koma.sort()
  print(sum(koma[:M-N]))
### BUGGY CODE ###

n=int(input())
x=[]
y=[]
z=[]
for k in range(n):
  x.append(input())
  if x[-1] not in y:
    y.append(x[-1])
x.sort()
y.sort()
count=[1]*len(y)
head=0
for k in range(1,n):
  if x[k]!=x[k-1]:
    head+=1
  else:
    count[head]+=1
maxim=max(count)
for i in range(len(y)):
  if count[i]==maxim:
    print(y[i])

### FIXED CODE ###

n=int(input())
x=[]
for k in range(n):
  x.append(input())
x.sort()
count=[1]
head=[0]
for k in range(1,n):
  if x[k]!=x[k-1]:
    head.append(k)
    count.append(1)
  else:
    count[-1]+=1
maxim=max(count)
for k in range(len(count)):
  if count[k]==maxim:
    print(x[head[k]])
### BUGGY CODE ###

a, b, k = map(int, input().split())
l = [i for i in range(a, b+1)]

for i in range(len(l)):
  if i < k or i >= len(l)-k:
    print(l[i])

### FIXED CODE ###

a, b, k = map(int, input().split())
ans = []
for i in range(a, a+k):
  if i >= a and i <= b:
    ans.append(i)

for i in range(b-k+1, b+1):
  if not i in ans and i >= a and i <= b:
    ans.append(i)

for i in ans:
  print(i)
### BUGGY CODE ###

def main():
    n, p = map(int, input().split())
    s = input()
    mu = [None]*n
    ans = 0
    c = [0]*p
    ss = map(int, s)
    if 10%p == 0:
        ss = list(ss)
        for i in range(n):
            if ss[i]%p == 0:
                ans += i+1
        print(ans)
        return
    num = int(s)
    tens = 10**(n-1)
    for i, si in enumerate(ss):
        v = num%p
        mu[i] = v
        c[v] += 1
        num -= si*tens
        tens //= 10
    c[0] += 1
    for i in c:
        if i:
            ans += ((i-1)*i)//2
        
    print(ans)
    

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n, p = map(int, input().split())
    s = input()
    mu = [None]*n
    ans = 0
    c = [0]*p
    if 10%p == 0:
        ss = map(int, s)
        ss = list(ss)
        for i in range(n):
            if ss[i]%p == 0:
                ans += i+1
        print(ans)
        return
    sr = s[::-1]
    ssr = map(int, sr)
    tens = 1
    v = 0
    for i, si in enumerate(ssr):
        v = (v + (si%p)*tens)%p
        mu[i] = v
        c[v] += 1
        tens *= 10
        tens %= p
    c[0] += 1
    for i in c:
        if i:
            ans += ((i-1)*i)//2
        
    print(ans)
    

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

import sys
input = sys.stdin.readline

def main():
    N = int(input())
    D = list(map(int, input().split()))
    if D[0] != 0:
        print(0)
        exit()
    Dnum = [0] * N
    for i in D:
        Dnum[i] += 1
    if Dnum[0] != 1:
        print(0)
        exit()
    ans = 1
    num = 0
    for i in range(N-1):
        if num == N:
            break
        else:
            ans *= Dnum[i] ** Dnum[i+1]
    print(ans%998244353)


if __name__ == '__main__': main()

### FIXED CODE ###

import sys
from collections import Counter
input = sys.stdin.readline

def main():
    _ = int(input())
    D = list(map(int, input().split()))
    Dnum = Counter(D)
    if D[0] != 0 or Dnum[0] != 1:
        print(0)
        exit()
    ans = 1
    for i in range(1, max(D)+1):
        ans *= Dnum[i] ** Dnum[i+1]
        if ans == 0:
            break
    print(ans%998244353)


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

import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
# from scipy.special import comb,perm #permはnPk

N,M = map(int,input().split())
length = N

i = [] #頂点(始点)
j = [] #頂点(終点)
d = [] #頂点間の距離
for _ in range(M):
    A,B = map(int,input().split())
    i.append(A-1)
    j.append(B-1)
    d.append(1)

graph = csr_matrix((d, (i, j)), shape=(N, N)) # 頂点i,jはゼロスタートである必要ある

#返り値は各頂点間の距離の値を含んだ隣接行列(float64型のnp.array)
dist,pred = dijkstra(graph, directed=False,indices=0,return_predecessors=True,unweighted=True)

print("Yes")
for i in range(1,N):
    print(pred[i]+1)

### FIXED CODE ###

# from math import factorial,sqrt,ceil #,gcd
# from itertools import permutations,combinations,combinations_with_replacement
# from collections import deque,Counter
# import re
# from bisect import bisect_left
# from heapq import heappush,heappop
# from numba import njit,jit
# from functools import lru_cache # 簡単メモ化 @lru_cache(maxsize=1000)
# from fractions import gcd

# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
from networkx import Graph
from networkx.algorithms.traversal.breadth_first_search import bfs_predecessors
G = Graph()
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix
# from scipy.special import comb,perm #permはnPk

# slist = "abcdefghijklmnopqrstuvwxyz"
N,M = map(int,input().split())
rows = [list(map(int,input().split())) for _ in range(M)]

G.add_edges_from(rows)

# shortestPath = shortest_path(G,target=1)
preds = bfs_predecessors(G,source=1)
# shortestPath = single_target_shortest_path(G,target=1)
# shortestPathLength,shortestPath = single_source_dijkstra(G,source=1)

preds = dict(preds)
if len(preds)+1 != N:
    print("No")
    exit()

print("Yes")
for i in range(2,N+1):
    print(preds[i])
### BUGGY CODE ###

n, m = map(int, input().split())
src = list(map(int, input().split()))
def waru(org_list):
    new = sorted(org_list, reverse=True)
    new[0] = new[0]//2
    return new
for _ in range(m):
    src = waru(src)
print(sum(src))

### FIXED CODE ###

import heapq
import math
n, m = map(int, input().split())
src = list(map(int, input().split()))
new_src = []
for s in src:
    new_src.append(s*-1)
heapq.heapify(new_src)

def waru(heap):
    tmp = heapq.heappop(heap)
    heapq.heappush(heap, math.ceil(tmp / 2))
    return heap
for _ in range(m):
    new_src = waru(new_src)
print(sum(new_src)*-1)
### BUGGY CODE ###

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

from collections import deque
n, m = map(int, input().split())
g = [[] for i in range(n)]
deg = [0]*n
deg2 = [0]*n
atode = []
for i in range(m):
    s, t = map(int, input().split())
    g[s-1].append(t-1)
    deg[t-1] += 1
    deg2[s-1] += 1
    atode.append((s-1,t-1))

ans = list(v for v in range(n) if deg[v]==0)
deq = deque(ans)
used = [0]*n

while deq:
    v = deq.popleft()
    for t in g[v]:
        deg[t] -= 1
        if deg[t]==0:
            deq.append(t)
            ans.append(t)
c = {j:i for i,j in enumerate(ans)}

e = [-1]*n
def rec(cur):
    if e[cur] != -1:
        return e[cur]
    res = 0
    cnt = 0
    for to in g[cur]:
        res += rec(to)+1
        cnt += 1
    if cnt:
        res /= cnt
    e[cur] = res
    return e[cur]

rec(0)

ee = [-1]*n
def rec2(cur, s,t):
    if c[cur] > c[s]:
        return e[cur]
    if ee[cur] != -1:
        return ee[cur]
    res = 0
    cnt = 0
    for to in g[cur]:
        if cur==s and to ==t:
            continue
        res += rec2(to,s,t)+1
        cnt += 1
    if cnt:
        res /= cnt
    ee[cur] = res
    return ee[cur]

ret = e[0]

for s,t in atode:
    if deg2[s] < 2:
        continue
    ee = [-1]*n
    rec2(0,s,t)
    ret = min(ret, ee[0])
print(ret)

### FIXED CODE ###

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

def main():
    n, m = map(int, input().split())
    g = [[] for i in range(n)]
    deg2 = [0]*n
    atode = []
    for i in range(m):
        s, t = map(int, input().split())
        g[s-1].append(t-1)
        deg2[s-1] += 1
        atode.append((s-1,t-1))

    ee = [-1]*n
    def rec2(cur, s,t):
        if ee[cur] != -1:
            return ee[cur]
        res = 0
        cnt = 0
        for to in g[cur]:
            if cur==s and to ==t:
                continue
            res += rec2(to,s,t)+1
            cnt += 1
        if cnt:
            res /= cnt
        ee[cur] = res
        return ee[cur]

    rec2(0,-1,-1)
    ret = ee[0]

    use = [[-1, -1] for i in range(n)]
    for s,t in atode:
        if deg2[s] < 2:
            continue
        if use[s][1] < ee[t]:
            use[s][0] = t
            use[s][1] = ee[t]

    for s, (t,cost) in enumerate(use):
        if s == -1:
            continue
        ee = [-1]*n
        rec2(0,s,t)
        ret = min(ret, ee[0])
    print(ret)

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

def gcd(a,b):
    if a < b:
        a, b = b, a
    q = a // b
    r = a - q * b
    if r == 0:
        return b
    else:
        return gcd(b,r)

sum = 0
K = 200
for i in range(1,K+1):
    for j in range(1, K+1):
        for k in range(1, K+1):
            sum += gcd(i, gcd(j,k))
print(sum)

### FIXED CODE ###

import collections

def gcd(a,b):
    if a < b:
        a, b = b, a
    q = a // b
    r = a - q * b
    if r == 0:
        return b
    else:
        return gcd(b,r)

K = int(input())

a = []

for i in range(1,K+1):
    for j in range(1, K+1):
        a.append(gcd(i,j))
        
col = collections.Counter(a)

sum = 0
for k in range(1, K+1):
    for key, value in col.items():
         sum += gcd(k, key) * value
print(sum)