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

from queue import Queue
N, M, K = map(int, input().split())
F = [set([]) for _ in range(N+1)]
B = [set([]) for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    F[a].add(b)
    F[b].add(a)

for _ in range(K):
    c, d = map(int, input().split())
    B[c].add(d)
    B[d].add(c)

checked = [False] * (N+1)
checked[0] = True
ans = ['0'] * (N+1)
for v in range(1, N+1):
    if checked[v]:
        continue
    A = []
    q = Queue()
    for u in F[v]:
        q.put(u)

    while not q.empty():
        u = q.get()
        if checked[u]: continue
        A.append(u)
        for w in F[u]:
            q.put(w)
        checked[u] = True
    
    for a in A:
        ans[a] = str(len(set(A) - set(B[a]) - set(F[a]) - set([a])))
    
    checked[v] = True

print(' '.join(ans[1:]))

### FIXED CODE ###

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, v):
        if self.parents[v] < 0:
            return v
        else:
            self.parents[v] = self.find(self.parents[v])
            return self.parents[v]

    def unite(self, u, v):
        u = self.find(u)
        v = self.find(v)

        if u == v:
            return

        if self.parents[u] > self.parents[v]:
            u, v = v, u

        self.parents[u] += self.parents[v]
        self.parents[v] = u

    def size(self, v):
        return -self.parents[self.find(v)]

    def same(self, u, v):
        return self.find(u) == self.find(v)

N, M, K = map(int, input().split())
uf = UnionFind(N+1)
F = [0] * (N+1)
B = [0] * (N+1)
for _ in range(M):
    a, b = map(int, input().split())
    uf.unite(a, b)
    F[a] += 1
    F[b] += 1

for _ in range(K):
    c, d = map(int, input().split())
    if uf.same(c, d):
        B[c] += 1
        B[d] += 1

for i in range(1, N+1):
    ans = uf.size(i) - F[i] - B[i] - 1
    print(ans, end=' ')

print()
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
Q = int(input())
B = [0]*Q
C = [0]*Q
for i in range(Q):
    B[i], C[i] = map(int,input().split())
for i in range(Q):
    for j in range(N):
        if A[j] == B[i]:
            A[j] = C[i]
    print(sum(A))

### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
Q = int(input())
cnt = [0]*100005
s = sum(A)
for i in A:
    cnt[i] += 1
for i in range(Q):
    B, C = map(int,input().split())
    s += (C-B)*cnt[B]
    print(s)
    cnt[C] += cnt[B]
    cnt[B] = 0
### BUGGY CODE ###

import numpy as np

n = int(input())
a_list = input().split()
a_list = [int(a) for a in a_list]

b_list = input().split()
b_list = [int(b) for b in b_list]

c_list = input().split()
c_list = [int(c) for c in c_list]

a_ar = np.sort(np.array(a_list))
b_ar = np.sort(np.array(b_list))
c_ar = np.sort(np.array(c_list))

goukei = 0
for b in b_ar:
    goukei += len(a_ar[a_ar<b]) * len(c_ar[c_ar>b])
    
print(goukei)

### FIXED CODE ###

import bisect

n = int(input())
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
c = [int(x) for x in input().split()]

a = sorted(a)
b = sorted(b)
c = sorted(c)

ans = 0

for x in b:
    aa = bisect.bisect_left(a,x)
    cc = len(c) - bisect.bisect_right(c,x)
    ans += aa * cc

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

def resolve():
    from collections import deque
    n, m = map(int, input().split())
    michi = [[0 for i in range(n)] for j in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        michi[a-1][b-1]=1
        michi[b - 1][a - 1] = 1
    heya=[-1]*n

    def f():
        check=0
        que = deque([])
        que.append(0)
        while que:
            if check==n-1:
                break
            else:
                p=que.popleft()
                for i in range(n):
                    if michi[p][i]==1 and heya[i]==-1:
                        michi[p][i]=0
                        michi[i][p]=0
                        heya[i]=p+1
                        check+=1
                        que.append(i)
        return

    f()
    print("Yes")
    for i in heya[1:]:
        print(i)
resolve()

### FIXED CODE ###

def resolve():
    from collections import deque
    n, m = map(int, input().split())
    michi = [[] for j in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        michi[a-1].append(b-1)
        michi[b - 1].append(a - 1)
    heya=[-1]*n

    def f():
        check=0
        que = deque([])
        que.append(0)
        while que:
            p = que.popleft()
            for i in michi[p]:
                if heya[i] == -1:
                    heya[i] = p + 1
                    check += 1
                    if check == n :
                        break
                    que.append(i)

        return

    f()
    print("Yes")
    for i in heya[1:]:
        print(i)
resolve()
### BUGGY CODE ###

from itertools import permutations
import numpy as np
def read(): return list(map(int, input().split()))


INF = 114514810


def wf(d):
    N = len(d[0])
    d = np.array(d)
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
    return d


def calc_dist(p, d):
    dist = 0
    for i in range(len(p) - 1):
        if d[p[i]][p[i + 1]] >= INF:
            return INF
        dist += d[p[i]][p[i + 1]]
    return dist


def main():
    N, M, R = read()
    r = map(lambda x: x - 1, sorted(read()))
    d = [[INF for i in range(N)] for j in range(N)]

    for i in range(M):
        a, b, c, = read()
        a -= 1
        b -= 1
        d[a][b] = d[b][a] = c

    d = wf(d)

    min_dist = INF
    for p in list(permutations(r)):
        min_dist = min(min_dist, calc_dist(p, d))

    print(min_dist)


if __name__ == '__main__':
    main()

### FIXED CODE ###

from itertools import permutations
def read(): return list(map(int, input().split()))


INF = 114514810


def wf(d):
    N = len(d[0])
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
    return d


def calc_dist(p, d):
    dist = 0
    for i in range(len(p) - 1):
        if d[p[i]][p[i + 1]] >= INF:
            return INF
        dist += d[p[i]][p[i + 1]]
    return dist


def main():
    N, M, R = read()
    r = map(lambda x: x - 1, sorted(read()))
    d = [[INF for i in range(N)] for j in range(N)]

    for i in range(M):
        a, b, c, = read()
        a -= 1
        b -= 1
        d[a][b] = d[b][a] = c

    d = wf(d)

    min_dist = INF
    for p in list(permutations(r)):
        min_dist = min(min_dist, calc_dist(p, d))

    print(min_dist)


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

a, b, c, d = map(int, input().split())
cnt = []
if a == c and b == d:
    print(max(a*c, b*d))
    exit()
else:
    for i in range(a, b+1):
        for j in range(c, d+1):
            cnt.append(i*j)
            
C = sorted(cnt)
print(max(C[0],C[-1]))


### FIXED CODE ###

a, b, c, d = map(int,input().split())

if a == c and b == d:
    print(max(a*c, b*d))
    exit()
else:
    print(max(a*c, a*d,b*c,b*d))
### BUGGY CODE ###

k, s =map(int, input().split())
count=0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x + y + z == s:
                count+=1
print(count)

### FIXED CODE ###

k, s =map(int, input().split())
count=0
for x in range(k+1):
    for y in range(min(k+1, s-x+1)):
        if k >=s - x - y >= 0:
            count+=1
print(count)
### BUGGY CODE ###

s=str(input())
k=int(input())

l=len(s)
chars=set()
sub1=['']*l


for i in range(l):
    n=i+1 #length = n
    for j in range(l-i):
        chars.add(s[j:j+n])
        #print('i,j,sub',i,j,s[j:j+n])

print(sorted(chars)[k-1])

### FIXED CODE ###

s=str(input())
k=int(input())

l=len(s)
chars=set()
chars1=set()
sub1=['']*l

for j in range(l):
    chars1.add(s[j])
    min_c=sorted(chars1)[0]

def subset(st,m):
    substring=set()
    if m==0:
        lst=len(st)
    else:
        lst=m
    for i in range(lst):
        n=i+1 #length = n
        for j in range(lst-i):
            substring.add(st[j:j+n])
    return substring
    
chars=chars|subset(s[max(l-10,0):],0)
for i in range(l):
    if s[i]==min_c:
        chars=chars|subset(s[i:i+5],0)

#print(min_c,chars)

'''
for i in range(l):
    n=i+1 #length = n
    for j in range(l-i):
        chars.add(s[j:j+n])
        #print('i,j,sub',i,j,s[j:j+n])
'''

print(sorted(chars)[k-1])
### BUGGY CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10**6)

INF = 10**10


def main(input, print):
    move = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    move2 = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2),
             (-1, -2), (-1, -1),          (-1, 1), (-1, 2),
             (0,  -2),                              (0, 2),
             (1,  -2),  (1, -1),           (1, 1),  (1, 2),
             (2,  -2),  (2, -1),  (2, 0),  (2, 1),  (2, 2)]

    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    table = [input() for _ in range(H)]
    path = [[INF] * W for _ in range(H)]

    que = deque()
    path[Ch-1][Cw-1] = 0
    que.append((Ch-1, Cw-1, 0))
    while que:
        y, x, cnt = que.pop()

        for i, j in move:
            nx = x+i
            ny = y+j
            if ny < 0 or nx < 0 or ny >= H or nx >= W or table[ny][nx] == '#' or path[ny][nx] <= cnt:
                continue
            path[ny][nx] = cnt
            que.appendleft((ny, nx, cnt))

        for i, j in move2:
            nx = x+i
            ny = y+j
            if ny < 0 or nx < 0 or ny >= H or nx >= W or table[ny][nx] == '#' or path[ny][nx] <= cnt + 1:
                continue
            path[ny][nx] = cnt+1
            que.appendleft((ny, nx, cnt+1))

    if(path[Dh-1][Dw-1] == INF):
        print(-1)
    else:
        print(path[Dh-1][Dw-1])


if __name__ == '__main__':
    main(sys.stdin.readline, print)


### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10**6)


def main(input, print):
    move = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    move2 = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2),
             (-1, -2), (-1, -1), (-1, 1), (-1, 2),
             (0, -2), (0, 2),
             (1, -2), (1, -1), (1, 1), (1, 2),
             (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]

    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    table = [input() for _ in range(H)]
    path = [[-1 for _ in range(W)] for _ in range(H)]

    que = deque()
    path[Ch-1][Cw-1] = 0
    que.append((Ch-1, Cw-1))
    while que:
        y, x = que.popleft()
        cnt = path[y][x]

        for k in range(len(move)):
            i, j = move[k]
            nx = x+i
            ny = y+j
            if ny < 0 or nx < 0 or ny >= H or nx >= W:
                continue
            if table[ny][nx] == '#':
                continue
            if path[ny][nx] == -1 or path[ny][nx] > cnt:
                path[ny][nx] = cnt
                que.appendleft((ny, nx))

        for k in range(len(move2)):
            i, j = move2[k]
            nx = x+i
            ny = y+j
            if ny < 0 or nx < 0 or ny >= H or nx >= W:
                continue
            if table[ny][nx] == '#':
                continue
            if path[ny][nx] == -1 or path[ny][nx] > cnt+1:
                path[ny][nx] = cnt+1
                que.append((ny, nx))
    if(path[Dh-1][Dw-1] == -1):
        print(-1)
    else:
        print(path[Dh-1][Dw-1])


if __name__ == '__main__':
    main(sys.stdin.readline, print)
### BUGGY CODE ###

import itertools

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

ans = 0
a = list(itertools.combinations(A,2))
#print(a)
#print(a[1])
for i in range(len(a)):
    tmp = a[i]
    #print(tmp)
    ans += tmp[0]*tmp[1]

print(ans%(10**9+7))


### FIXED CODE ###

import functools
import operator

N = int(input())
A = list(map(int, input().split()))
mod = 10**9+7
ans = 0
v = sum(A)
for i in range(N-1):
    v -= A[i]
    ans += A[i]*v
print(ans%mod)
### BUGGY CODE ###

import itertools
import collections

N, K = map(int, input().split())
mod = 10**9 + 7
A = list(range(N+1))
out = 0
for i in range(N+1, K-1, -1):
  B = list(itertools.combinations(A, i))
  C = [sum(b) for b in B]
  out += len(collections.Counter(C))
print(out)

### FIXED CODE ###

N, K = map(int, input().split())
mod = 10**9 + 7
count = 0
for n in range(K, N+2):
  maxSum = (n*(N + N-n+1))//2
  minSum = (n*(n-1))//2
  count += maxSum - minSum + 1
  count %= mod

print(count)
### BUGGY CODE ###

n=int(input())
A=list(input().split())
from collections import deque
q=deque()
for a in A:
    q.append(a)
    q.reverse()
print(" ".join(list(q)))

### FIXED CODE ###

n = int(input())
a = list(input().split())
a1 = ['']*(n//2 + n%2)
a2 = ['']*(n//2)

for i in range(n):
	if i%2 == 0:
		a1[i//2] = a[i]
	else:
		a2[-i//2] = a[i]

if n%2 != 0 and n != 1:
	ans = ' '.join(a1[::-1]) + ' ' + ' '.join(a2[::-1])
elif n%2 == 0:
	ans = ' '.join(a2) + ' ' + ' '.join(a1)
else:
	ans = a[0]
print(ans)
### BUGGY CODE ###

import copy
import sys

def main():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    B = [0] * n

    for i in range(k):
        for j in range(n):
            l = max(0, j-A[j]) #座標iの電球が照らす範囲の左端
            r = min(n-1, j+A[j]) #座標iの電球が照らす範囲の右端
            B[l] += 1
            if (r+1 < n):
                B[r+1] -= 1 # 後ほど累積和にしたときに、照らす範囲の右端より外には影響が及ばないようにあらかじめ1引いておく

        for j in range(n-1):
            B[j+1] += B[j]

        A = copy.deepcopy(B)
        B = [0] * n

    print(*A)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import copy
import sys
import math

def main():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))
    B = [0] * n

    # k_max = 1 + math.ceil(math.log10(n))

    for i in range(min(k, 41)):
        for j in range(n):
            l = max(0, j-A[j]) #座標iの電球が照らす範囲の左端
            r = min(n-1, j+A[j]) #座標iの電球が照らす範囲の右端
            B[l] += 1
            if (r+1 < n):
                B[r+1] -= 1 # 後ほど累積和にしたときに、照らす範囲の右端より外には影響が及ばないようにあらかじめ1引いておく

        for j in range(n-1):
            B[j+1] += B[j]

        A = copy.deepcopy(B)
        B = [0] * n

    print(*A)

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

n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
dp=[1,1]
if 1 in a:
  dp[1]=0
for i in range(2,n+1):
  if i in a:
    dp.append(0)
  else:
    dp.append((dp[-1]+dp[-2])%1000000007)
print(dp[-1]%1000000007)

### FIXED CODE ###

n,m=map(int,input().split())
a=set([int(input()) for i in range(m)])
mod=1000000007
dp=[1,1]
if 1 in a:
  dp[1]=0
for i in range(2,n+1):
  if i in a:
    dp.append(0)
  else:
    dp.append((dp[-1]+dp[-2])%mod)
print(dp[-1]%mod)
### BUGGY CODE ###

n,m = map(int,input().split(" "))
a=[]
mod = 10 ** 9 + 7
for i in range(m):
    a.append(int(input()))

dp = [0] * (n+1)
for j in range(n+1):
    if j in a:
        dp[j] = 0
    elif j > 1:
        dp[j] = (dp[j-1] + dp[j-2]) % mod
    else:
        dp[j] = 1

print(dp[n])


### FIXED CODE ###

n,m = map(int,input().split(" "))
a=[0] * (n+1)
mod = 10 ** 9 + 7
for i in range(m):
    a[int(input())] = 1

dp = [0] * (n+1)
for j in range(n+1):
    if a[j] == 1:
        dp[j] = 0
    elif j == 1 or j == 0:
        dp[j] = 1
    else:
        dp[j] = (dp[j-1] + dp[j-2]) % mod

print(dp[n])
### BUGGY CODE ###

def main():
    input1 = input().split()
    N = int(input1[0])
    M = int(input1[1])

    H = [0]*N
    input2 = input().split()
    for i in range(N):
        H[i] = int(input2[i])
    
    A = [0]*M
    B = [0]*M
    mountain = [[0 for i in range(N)]for j in range(N)]
    for i in range(M):
        input3 = input().split()
        A[i] = int(input3[0])
        B[i] = int(input3[1])
        mountain[A[i]-1][B[i]-1] = 1
        mountain[B[i]-1][A[i]-1] = 1

    result = 0
    for i in range(N):
        error = 0
        for j in range(N):
            if mountain[i][j] == 1:
                if H[i] <= H[j] and i != j:
                    error = 1
        if error == 0:
            result += 1

    print(result)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    input1 = input().split()
    N = int(input1[0])
    M = int(input1[1])

    H = [0]*N
    input2 = input().split()
    for i in range(N):
        H[i] = int(input2[i])
    
    A = [0]*M
    B = [0]*M
    for i in range(M):
        input3 = input().split()
        A[i] = int(input3[0])
        B[i] = int(input3[1])

    mountain = [0]*N
    for i in range(M):
        if H[A[i]-1] <= H[B[i]-1]:
            mountain[A[i]-1] = 1
        if H[B[i]-1] <= H[A[i]-1]:
            mountain[B[i]-1] = 1
    result = 0
    for i in range(N):
        if mountain[i] == 0:
            result += 1
            
    print(result)

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

from bisect import bisect_left
from math import sqrt
MOD = 10**9 + 7

def main():
    lim, n = map(int, input().split())
    num, tmp = [], []
    for i in range(1, int(sqrt(lim))+1):
        num.append(i)
        if i**2 != lim:
            tmp.append(lim//i)
    while len(tmp) > 0:
        num.append(tmp.pop(-1))
    m = len(num)
    dp = [[0]*m for _ in range(n)]
    dp[0][0] = 1
    for j in range(1, m):
        dp[0][j] = num[j] - num[j-1]
    for i in range(1, n):
        for j in range(1, m):
            dp[i-1][j] += dp[i-1][j-1]
        for j in range(m):
            idx = bisect_left(num, lim//num[j])
            p = num[j]
            if j > 0:
                p -= num[j-1]
            dp[i][j] = dp[i-1][idx] * p % MOD
    print(sum(dp[-1])%MOD)

if __name__ == "__main__":
    main()

### FIXED CODE ###

from bisect import bisect_left
from math import sqrt
MOD = 10**9 + 7

def main():
    lim, n = map(int, input().split())
    num, tmp = [], []
    for i in range(1, int(sqrt(lim))+1):
        num.append(i)
        if i**2 != lim:
            tmp.append(lim//i)
    while len(tmp) > 0:
        num.append(tmp.pop(-1))
    m = len(num)
    dp = [[0]*m for _ in range(n)]
    dp[0][0] = 1
    for j in range(1, m):
        dp[0][j] = num[j] - num[j-1]
    for i in range(1, n):
        for j in range(1, m):
            dp[i-1][j] += dp[i-1][j-1]
        for j in range(m):
            idx = bisect_left(num, lim//num[j])
            p = num[j]
            if j > 0:
                p -= num[j-1]
            dp[i][j] = dp[i-1][idx] * p % MOD
    print(sum(dp[-1])%MOD)

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

# C
N, K = map(int, input().split())
h = [0]*N
for i in range(N):
    h[i] = int(input())
h.sort()
result = 1e10
for i in range(N-K+1):
    h_list = h[i:i+K]
    result = min(result, max(h_list) - min(h_list))
print(result)

### FIXED CODE ###

# C
N, K = map(int, input().split())
h = [0]*N
for i in range(N):
    h[i] = int(input())
h.sort()
result = 1e10
for i in range(N-K+1):
    result = min(result, h[i+K-1]-h[i])
print(result)
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(N):
  ans += 1
  temp = a[i]
  index = i
  while index < N - 1:
    if temp ^ a[index + 1] == temp + a[index + 1]:
      temp += a[index + 1]
      index += 1
      ans += 1
    else:
      break
print(ans)

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
ans = 0
temp = 0
l = 0
r = 0
while r < N:
  if temp ^ a[r] == temp + a[r]:
    temp += a[r]
    ans += r - l + 1
    r += 1
  else:
    temp -= a[l]
    l += 1
print(ans)
### BUGGY CODE ###

import sys
from collections import defaultdict, deque
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
N, X, Y = [int(x) for x in input().strip().split()]
D = defaultdict(int)
L = [[i-1, i+1] for i in range(1, N+1)]
L[0] = [L[0][1]]
L[-1] = [L[-1][0]]
L[X-1].append(Y)
L[Y-1].append(X)

def bfs(i):
    ni = deque(L[i-1])
    c = 1
    C = [0] * N
    C[i-1] = -1
    while ni:
        nii = ni
        ni = deque([])
        for niii in nii:
            if C[niii-1] != 0:
                continue
            C[niii-1] = c
            if niii > i:
                D[c] += 1
            ni.extend(L[niii-1])
        c += 1
    return True

for n in range(1, N+1):
    bfs(n)

for n in range(1, N):
    print(D[n])

### FIXED CODE ###

import sys
from collections import defaultdict
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
N, X, Y = [int(x) for x in input().strip().split()]
D = defaultdict(int)
for k in range(1, N):
    for k2 in range(k+1, N+1):
        D[min(k2 - k, abs(X-k) + 1 + abs(Y-k2), abs(Y-k) + 1 + abs(X-k2))] += 1

for k in range(1, N):
    print(D[k])
### BUGGY CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))
c = list(map(int,input().split()))
p = [pi-1 for pi in p]

ans = -1e18
for i in range(n):
  cur = p[i]
  loop = [c[cur]]
  cnt = 1
  ans = max(ans,c[cur])
  while cur != i and cnt<k:
    cur = p[cur]
    tmp = loop[-1]+c[cur]
    loop.append(tmp)
    ans = max(ans,tmp)
    cnt += 1
  #print(loop)
  if cnt==k or loop[-1]<=0:continue
  a = k//len(loop) * loop[-1]
  b = (k//len(loop)-1) * loop[-1]
  ans = max(ans,a,b)
  for _ in range(k%len(loop)):
    a += c[cur]
    ans = max(ans,a)
    cur = p[cur]
  cur = i
  for _ in range(len(loop)):
    b += c[cur]
    ans = max(ans,b)
    cur = p[cur]
print(ans)

### FIXED CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))
c = list(map(int,input().split()))
p = [pi-1 for pi in p]

ans = -1e18
for i in range(n):
  cur = p[i]
  loop = [c[cur]]
  cnt = 1
  ans = max(ans,c[cur])
  while cur != i and cnt<k:
    cur = p[cur]
    tmp = loop[-1]+c[cur]
    loop.append(tmp)
    ans = max(ans,tmp)
    cnt += 1
  #print(loop)
  if cnt==k or loop[-1]<=0:continue
  a = k//len(loop) * loop[-1]
  b = (k//len(loop)-1) * loop[-1]
  ans = max(ans,a,b)
  for _ in range(k%len(loop)):
    a += c[cur]
    ans = max(ans,a)
    cur = p[cur]
  cur = i
  for _ in range(len(loop)):
    b += c[cur]
    ans = max(ans,b)
    cur = p[cur]
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
a = [int(input()) for x in range(m)]
mod = 10**9 + 7

l = [0]*(n+1)
l[0] = 1

for i in range(1, n+1):
  if i in a:
    if l[i-1] == 0:
      print(0)
      exit()
  else:
    l[i] = (l[i-2] + l[i-1]) % mod

print(l[-1])


### FIXED CODE ###

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

l = [0]*(n+1)
l[0] = 1

for i in range(1, n+1):
  if i in a:
    l[i] = 0
    continue
  else:
    l[i] = l[i-2] + l[i-1]

print(l[-1] % 1000000007)
### BUGGY CODE ###

from fractions import gcd

N = int(input())
A = list(map(int, input().split()))
MOD = 10**9 + 7

lcm = 1
for a in A:
    lcm = lcm * a // gcd(lcm, a)


ans = 0
for a in A:
    # フェルマーの小定理
    ans += lcm * pow(a, MOD-2, MOD)
    ans %= MOD


print(ans)

### FIXED CODE ###

from fractions import gcd


def main():
        
    N = int(input())
    A = list(map(int, input().split())) 
    MOD = 10**9 + 7


    l = 1

    for a in A:
        l = l * a // gcd(l, a)


    ans = 0
    for a in A:
        ans += (l // a)
    ans %= MOD

    print(ans)


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

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

result = 0
for i in range(N):
    if P[i] == min(P[: i + 1]):
        result += 1
    else:
        pass
print(result)

### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, P: "List[int]"):

    result = 1
    min_num = P[0]
    for i in range(N):
        if P[i] < min_num:
            result += 1
            min_num = P[i]
        else:
            pass
    print(result)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, P)


if __name__ == "__main__":
    main()