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


import sys

N, M = map(int, input().split())
uvs = [list(map(lambda x:int(x)-1, input().split())) for _ in range(M)]
S, T = map(lambda x:int(x)-1, input().split())

roots = [[] for _ in range(N)]

for uv in uvs:
    roots[uv[0]].append(uv[1])

costs = [-10000 for _ in range(N)]

from collections import deque

todo = deque([S])
costs[S] = 0
todo_set = set([S])

while len(todo)>0:
    checking = todo.popleft()
    next_targets = deque([checking])
    for i in range(3):
        purposes = set()
        while len(next_targets) > 0:
            now = next_targets.pop()
            for root in roots[now]:
                purposes.add(root)
        next_targets = deque(purposes)
    for next_target in next_targets:
        if costs[next_target] < 0 and next_target not in todo_set:
            costs[next_target] = costs[checking]+1
            todo.append(next_target)
            todo_set.add(next_target)
        if next_target == T:
            print(costs[next_target])
            sys.exit()
print(-1)

### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Tue Jul  7 18:47:41 2020

@author: naoki
"""
import sys
import copy
def func():
    N, M = map(int, input().split())
    uvs = [list(map(lambda x:int(x)-1, input().split())) for _ in range(M)]
    S, T = map(lambda x:int(x)-1, input().split())
    
    roots = [[] for _ in range(N)]
    
    for uv in uvs:
        roots[uv[0]].append(uv[1])
    
    costs = [-10000]*(N)
    
    from collections import deque
    
    todo = deque([S])
    costs[S] = 0
    todo_set = set([S])
    
    layers = [set() for _ in range(3)]
    
    while len(todo)>0:
        checking = todo.popleft()
        next_targets = deque([checking])
        for i in range(3):
            purposes = set()
            while len(next_targets) > 0:
                now = next_targets.pop()
                for root in roots[now]:
                    if root not in layers[i]:
                        layers[i].add(root)
                        purposes.add(root)
            next_targets = purposes.copy()
        for next_target in next_targets:
            if costs[next_target] < 0 and next_target not in todo_set:
                costs[next_target] = costs[checking]+1
                todo.append(next_target)
                todo_set.add(next_target)
                if next_target == T:
                    print(costs[next_target])
                    sys.exit()
    print(-1)
if __name__ == "__main__":
    func()
### BUGGY CODE ###

N=int(input())
a=input().split()
b=sorted([int(_) for _ in a])
print(" ".join([str(a.index(str(_))+1) for _ in b]))


### FIXED CODE ###

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

d=[0 for n in range(N)]
for n in range(N):
    d[A[n]-1] = str(n+1)

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

r1,c1,r2,c2=map(int,input().split())
mod=10**9+7
f=[1]
for i in range(2*10**6+7):f+=[f[-1]*(i+1)%mod]
ans=0
for i in range(c1,c2+1):
  d=((r2+1)*f[i+r2+1]%mod)*f[r1]
  d%=mod
  d=(d+(mod-((r1*f[r2+1]%mod)*f[i+r1])%mod))%mod
  d*=pow((((i+1)*f[i]%mod)*f[r1]%mod)*f[r2+1]%mod,mod-2,mod)
  d%=mod
  ans+=d
  ans%=mod
print(ans)


### FIXED CODE ###

r1,c1,r2,c2=map(int,input().split())
mod=10**9+7
f=[1]
for i in range(2*10**6+7):f+=[f[-1]*(i+1)%mod]
ans=0
for i in range(c1,c2+1):
  d=((r2+1)*f[i+r2+1]%mod)*f[r1]
  d%=mod
  d=(d+(mod-((r1*f[r2+1]%mod)*f[i+r1])%mod))%mod
  d*=pow((((i+1)*f[i]%mod)*f[r1]%mod)*f[r2+1]%mod,mod-2,mod)
  d%=mod
  ans+=d
  ans%=mod
print(ans)
### BUGGY CODE ###

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    H, N, *ab = map(int, read().split())
    A = []
    B = []
    for a, b in zip(*[iter(ab)] * 2):
        A.append(a)
        B.append(b)
    
    dp = [float("inf")] * (H+1)
    dp[0] = 0

    for i in range(N):
        for j in range(H+1):
            if j + A[i] <= H:
                dp[j+A[i]] = min(dp[j+A[i]], dp[j]+B[i])
            else:
                dp[H] = min(dp[H], dp[j]+B[i])

    print(dp[H])


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    H,N = map(int, input().split())
    A = [None]*N
    B = [None]*N
    for i in range(N):
        A[i], B[i] = map(int, input().split())
    
    dp = [float("inf")] * (H+1)
    dp[0] = 0

    for i in range(N):
        for j in range(H+1):
            if j + A[i] <= H:
                dp[j+A[i]] = min(dp[j+A[i]], dp[j]+B[i])
            else:
                dp[H] = min(dp[H], dp[j]+B[i])

    print(dp[H])


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

# N, K = 5, 3
# HRR = [10, 30, 40, 50, 20]

N, K = 3, 1
HRR = [10, 20, 10]

N, K = 2, 100
HRR = [10, 10]

N, K = 10, 4
HRR = [40, 10, 20, 70, 80, 10, 20, 70, 80, 60]

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


def calculate(n, k, hrr):
    result = []
    for i in range(n):
        if i == 0:
            result.append(0)
            continue

        mins = -1
        for j in range(1, k + 1):
            index = i - j
            if index >= 0:
                value = result[index] + abs(hrr[i] - hrr[index])
                if mins == -1:
                    mins = value
                else:
                    if value < mins:
                        mins = value
        result.append(mins)

    print(result[-1])


calculate(N, K, HRR)


### FIXED CODE ###

# N, K = 5, 3
# HRR = [10, 30, 40, 50, 20]

N, K = 3, 1
HRR = [10, 20, 10]

N, K = 2, 100
HRR = [10, 10]

N, K = 10, 4
HRR = [40, 10, 20, 70, 80, 10, 20, 70, 80, 60]

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


def calculate(n, k, hrr):
    result = []
    for i in range(n):
        if i == 0:
            result.append(0)
            continue

        mins = -1
        for j in range(1, k + 1):
            index = i - j
            if index >= 0:
                value = result[index] + abs(hrr[i] - hrr[index])
                if mins == -1:
                    mins = value
                else:
                    if value < mins:
                        mins = value
        result.append(mins)

    print(result[-1])


calculate(N, K, HRR)
### 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 nd > L: continue
            if D[j] < 0 or D[j] >= nd:
                if done[j] == 0:
                    hpush(h, [nd, j])
                    D[j] = nd
    return 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

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 0 <= D1[j] <= L:
            Y[i].append(j)

# print("X =", X)
# print("Y =", Y)
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))

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

import fractions
import sys
input = sys.stdin.readline

def main():

    n=int(input())
    a = [int(x) for x in input().split()]
    ans = a[0]

    mmm=10**9+7
    for i in a[1:]:
        ans = (ans *i )// fractions.gcd(ans, i)

    result=0
    for item in a:
      result+=ans//item

    print(result%mmm)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    from fractions import gcd
    import sys
    n=int(input())
    a = tuple(map(int, input().split()))
    ans = 1

    mmm=10**9+7
    for i in a:
        ans = ans *i // gcd(ans, i)

    result=0
    for item in a:
      result+=ans//item

    print(result%mmm)

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

k=int(input())

ans=0
import itertools
import math
for seq in itertools.product(range(1,k+1),range(1,k+1),range(1,k+1)):
    ans+=math.gcd(math.gcd(seq[0],seq[1]),seq[2])
print(ans)

### FIXED CODE ###

k=int(input())

ans=0
import itertools
import math
for seq in itertools.combinations_with_replacement(range(1,k+1),3):
    if seq[0]==seq[1] or seq[1]==seq[2]:
        if  seq[0]!=seq[2]:
            ans+=(math.gcd(seq[0],math.gcd(seq[1],seq[2])))*3
        else:
            ans+=math.gcd(seq[0],math.gcd(seq[1],seq[2]))

    else:
        ans+=math.gcd(seq[0],math.gcd(seq[1],seq[2]))*6
print(ans)
### BUGGY CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split())) + [0] * (n*k)
dp = [float('inf')] * (n*k + 1)
dp[0] = 0
for i in range(n):
    for j in range(1,k+1):
        dp[i+j] = min(dp[i+j],dp[i] + abs(h[i] - h[i+j]))
print(dp[n-1])


### FIXED CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split())) + [0] * (k)
dp = [float('inf')] * (n*k + 1)
dp[0] = 0
for i in range(n):
    for j in range(1,k+1):
        dp[i+j] = min(dp[i+j],dp[i] + abs(h[i] - h[i+j]))
print(dp[n-1])
### BUGGY CODE ###

from sys import stdin
N = int(stdin.readline().rstrip())
S = (stdin.readline().rstrip())
ans = 0
for a in range(10):
    for b in range(10):
        for c in range(10):
            i_a = 0
            i_b = 0
            i_c = 0
            for s in S:
                s = int(s)
                if s == a and (not i_a):
                    i_a = 1
                    continue
          
                if i_a and (s == b) and (not i_b):
                    i_b = 1
                    continue

                if i_a and i_b and (s == c):
                    ans += 1
                    break
            
print(ans)

### FIXED CODE ###

from collections import defaultdict
from sys import stdin
N = int(stdin.readline().rstrip())
S = (stdin.readline().rstrip())
d = defaultdict(list)
for ind, i in enumerate(S):
    d[i].append(ind+1)
ans = 0

for a in range(10):
    for b in range(10):
        for c in range(10):
            if (a == b == c) and (len(d[str(a)]) < 3):
                continue
            if d[str(a)] and d[str(b)] and d[str(c)]:
                i_a = d[str(a)][0]
                i_b = -1
                i_c = -1
                for j in d[str(b)]:
                    if i_a < j:
                        i_b = j
                        break
                for k in d[str(c)]:
                    if i_b < k:
                        i_c = k
                        break
                if i_a < i_b < i_c:
                    ans += 1
            else:
                continue
print(ans)
### BUGGY CODE ###

n = int(input())
ratios = [tuple(int(x) for x in input().split()) for i in range(n)]

t_votes = 1
a_votes = 1
for ratio in ratios:
    count = 0
    while t_votes > ratio[0]*count or a_votes > ratio[1]*count:
        count += 1
    t_votes = ratio[0] * count
    a_votes = ratio[1] * count
print(t_votes+a_votes)


### FIXED CODE ###

n = int(input())

t_votes = a_votes = 1
for i in range(n):
    t_rate, a_rate = (int(x) for x in input().split())
    count = max(-(-t_votes // t_rate), -(-a_votes // a_rate))
    t_votes = t_rate*count
    a_votes = a_rate*count

print(t_votes+a_votes)
### BUGGY CODE ###

from sys import stdin,setrecursionlimit
import string
from itertools import product
setrecursionlimit(10**7)
n = int(stdin.readline().rstrip())
alpha = "abcdefghijklmn"
kouho = set("")
#0~9までの数字を列挙
li = [str(i) for i in range(n)]
#重複ありで全探索
lin = list(product(li, repeat=n))
for i in lin:
    #数列にする
    s = ''.join(map(str, i))
    point = 0
    moto = s[:]
    while True:
        flag = False
        for j in s:
            #数字が出てきたらアルファベットに置換する
            if j in "0123456789":
                s = s.replace(j,alpha[point])
                point += 1
                flag = True
                break
        #すべての文字列が置換されたらbreak
        if flag == False:
            break
    #重複してたら候補に入れない
    kouho.add(s)
kouho = list(kouho)
kouho.sort()
for i in kouho:
    print(i)

### FIXED CODE ###

import string

alphabet = string.ascii_lowercase

n = int(input())

def DFS(before,keta):
    num = 0
    if keta == n:
        print(before)
        return
    for i in before:
        num = max(num,alphabet.index(i))
    num += 1
    for j in range(num+1):
        DFS(before+alphabet[j],keta+1)

DFS("a",1)
### BUGGY CODE ###

def func(x, nn):
    value = 0
    for i in range(nn - 1):
        for j in range(i + 1, nn):
            value += x[i] ^ x[j]
    ans = value % (10 ** 9 + 7)
    return ans

n = int(input())
li = list(map(int, input().split()))
print(func(li, n))


### FIXED CODE ###

import numpy as np
n = int(input())
arr = np.array([int(i) for i in input().split()])
mod = 10 ** 9 + 7
s = 0

for i in range(60):
    t = arr & 1
    c1 = np.count_nonzero((arr & 1))
    s += 2 ** i * c1 * (n - c1)
    arr >>= 1

print(s % mod)
### BUGGY CODE ###

N,M,S,L=map(int,input().split())
s = 0
for i in range(L//N+1):
    for j in range(L//M+1):
        if N*i + M*j > L:
            break
        for k in range(L//S+1):
            if N*i + M*j + S*k > L:
                break
            if N*i + M*j + S*k == L:
                s+=1
print(s)

### FIXED CODE ###

N,M,S,L=map(int,input().split())
s = 0
for i in range(L//N+1):
    for j in range(L//M+1):
        k = (L-N*i - M*j)//S
        if k <0 :break
        if (L-N*i - M*j)//S == int((L-N*i - M*j)/S) and N*i + M*j + S*k == L:
            s+=1

print(s)
### BUGGY CODE ###

from itertools import permutations
 
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    n=len(d[0])
    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])
    return d
 
N,M,R=[int(x) for x in input().split()]
r=[int(x)-1 for x in input().split()]
 
#INF = float("inf")
route_list=[[10**8]*N for _ in range(N)]
 
for i in range(M):
    a,b,c=[int(x) for x in input().split()]
    route_list[a-1][b-1]=c
    route_list[b-1][a-1]=c
 
wa_list=warshall_floyd(route_list)
ans=30**9
 
for perm in permutations(r):
    #print(perm)
    cur = sum(wa_list[v][u] for v, u in zip(perm, perm[1:]))
    ans = min(ans, cur)
 
print(ans)

### FIXED CODE ###

import math
from itertools import permutations

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    n=len(d[0])
    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])
    return d

N,M,R=[int(x) for x in input().split()]
r=[int(x)-1 for x in input().split()]

route_list=[[10**9]*N for i in range(N)]

for i in range(M):
    a,b,c=[int(x) for x in input().split()]
    route_list[a-1][b-1]=c
    route_list[b-1][a-1]=c

wa_list=warshall_floyd(route_list)
ans=30**9

for perm in permutations(r):
    #print(perm)
    cur = sum(wa_list[v][u] for v, u in zip(perm, perm[1:]))
    ans = min(ans, cur)

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

def main():
    N, K = map(int, input().split())
    l = list(map(int, input().split()))
    t = []
    for i in range(1, N - K + 1):
        if sum(l[i-1:K+i-1]) < sum(l[i:K+i]):
            print('Yes')
        else:
            print('No')
main()  



### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    l = list(map(int, input().split()))
    for i in range(K, N):
        if l[i] > l[i-K]:
            print('Yes')
        else:
            print('No')
main()
### BUGGY CODE ###

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

N = int(input())
S = [Counter(input().rstrip()) for _ in range(N)]

ans = 0
for s1, s2 in combinations(S, 2):
  if s1 == s2:
    ans +=1
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
S={}
for _ in range(N):
  s = ''.join(sorted(input().rstrip()))
  if s in S:
    S[s] += 1
  else:
    S[s] = 1

ans=0
for s in S.values():
  ans += s*(s-1)//2
  
print(ans)
### BUGGY CODE ###

from collections import deque

mae = deque()
usiro=deque()

s=input()
kai=int(input())

siji=[]*kai

for i in range(kai):
    siji.append(input())


state=1
for i in range(kai):
    si=siji[i]
    if(si[0]=='1'):
        state*=-1
    else:
        _,f,c=si.split()
        f=int(f)
        if(state==-1):
            f=3-f
        if(f==1):
            mae. appendleft(c)
        else:
            usiro.append(c)

ans=deque()
for m in mae:
    if(state==1):
        ans.append(m)
    else:
        ans.appendleft(m)
for smoji in s:
    if(state==1):
        ans.append(smoji)
    else:
        ans.appendleft(smoji)
for u in usiro:
    if(state==1):
        ans.append(u)
    else:
        ans.appendleft(u)

kotae=""
for a in ans:
    kotae+=a
print(kotae)

### FIXED CODE ###

from collections import deque

mae = deque()
usiro=deque()

s=input()
kai=int(input())

siji=[]*kai

for i in range(kai):
    siji.append(input())


state=1
for i in range(kai):
    si=siji[i]
    if(si[0]=='1'):
        state*=-1
    else:
        _,f,c=si.split()
        f=int(f)
        if(state==-1):
            f=3-f
        if(f==1):
            mae. appendleft(c)
        else:
            usiro.append(c)

ans=deque()
for m in mae:
    if(state==1):
        ans.append(m)
    else:
        ans.appendleft(m)
for smoji in s:
    if(state==1):
        ans.append(smoji)
    else:
        ans.appendleft(smoji)
for u in usiro:
    if(state==1):
        ans.append(u)
    else:
        ans.appendleft(u)

kotae="".join(ans)
print(kotae)
### BUGGY CODE ###

# coding: UTF-8
import sys
import copy

numlist = []
for line in sys.stdin.readlines():
  numlist.append(int(line.rstrip()))
N = numlist.pop(0)

for i, num in enumerate(numlist):
  nlist = copy.deepcopy(numlist)
  nlist.pop(i)
  maxN = max(nlist)
  print(maxN)


### FIXED CODE ###

# coding: UTF-8
import math
import sys
import copy

numlist = []
for line in sys.stdin.readlines():
  numlist.append(int(line.rstrip()))
N = numlist.pop(0)

nlist = copy.deepcopy(numlist)
Amax1 = max(nlist)
nlist.remove(Amax1)
Amax2 = max(nlist)

for num in numlist:
  if num != Amax1:
    print(Amax1)
  else:
    print(Amax2)
### BUGGY CODE ###

def resolve():
    N = int(input())
    arr = tuple(map(int, input().split()))
    counter = 1
    for i in range(1,N):
        if arr[i] == min(arr[0:i+1]):
            counter += 1
    print(counter)

if __name__ == "__main__":
    resolve()

### FIXED CODE ###

def resolve():
    N = int(input())
    arr = tuple(map(int, input().split()))
    tmp = arr[0]
    counter = 0
    for i in arr:
        if i<=tmp:
            tmp=i
            counter += 1
    print(counter)

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

def main():
    import sys
    input = sys.stdin.readline
    from collections import deque
    n = int(input())
    p = list(map(int, input().split()))

    # 迷路　BFS
    def bfs(sx, sy):
        d = deque()
        d.append((sx, sy, distance[sx][sy]))
        ans = distance[sx][sy]
        v = distance[sx][sy]
        check[sx][sy] = 0

        while len(d):
            x, y, dis = d.popleft()
            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]

                if 0 <= nx < n and 0 <= ny < n:
                    # 更新できるマスは更新
                    if distance[nx][ny] > dis:
                        distance[nx][ny] = dis
                        d.append((nx, ny, dis + check[nx][ny]))

        return ans

    distance = [[0 for i in range(n)] for j in range(n)]
    for i in range(n):
        for j in range(n):
            distance[i][j] += min(i, j, n - i - 1, n - j - 1)
    check = [[1] * n for i in range(n)]

    anss = 0
    for i in p:
        x = (i - 1) // n
        y = (i - 1) % n
        anss += bfs(x, y)

    print(anss)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

distance = [[min(i, j, n - i - 1, n - j - 1) for i in range(n)] for j in range(n)]
check = [[1] * n for i in range(n)]
p = [((i - 1) // n, (i - 1) % n) for i in p]

def move(x,y,nx,ny):
    if distance[nx][ny] > distance[x][y] + check[x][y]:
        distance[nx][ny] = distance[x][y] + check[x][y]
        d.append((nx,ny))

ans = 0
for i, j in p:
    ans += distance[j][i]
    d=[]
    d.append((j,i))
    check[j][i] = 0
    while len(d):
        x, y = d.pop()
        if x!=0:
            move(x,y,x-1,y)
        if x!=n-1:
            move(x,y,x+1,y)
        if y!=0:
            move(x,y,x,y-1)
        if y!=n-1:
            move(x,y,x,y+1)

print(ans)