Harryxun/stf_run huggingface dataset:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


class Node(object):

  def __init__(self, idx, color):
    self.idx = idx
    self.color = color
    self.edges = []
    self.traced = False

  def trace(self, counts, excludes):
    self.traced = True
    num = 1

    for edge in self.edges:
      if edge.traced:
        continue

      #excludes[self.color].append(0)
      n = edge.trace(counts, excludes)
      #p = n - excludes[self.color].pop()
      #counts[self.color] += p * (p - 1) // 2 + p
      num += n

    excludes[self.color][-1] = num

    return num


def main():
  N = int(input())
  nodes = [Node(i, v - 1) for i, v in enumerate(map(int, input().split()))]
  counts = [0] * N
  excludes = [[0] for _ in range(N)]

  for _ in range(N - 1):
    a, b = map(int, input().split())
    nodes[a - 1].edges.append(nodes[b - 1])
    nodes[b - 1].edges.append(nodes[a - 1])

  num = nodes[0].trace(counts, excludes)
  pair = num * (num - 1) // 2 + num

  for i in range(len(counts)):
    p = num - excludes[i][0]
    counts[i] += p * (p - 1) // 2 + p

  for c in counts:
    print(pair - c)


if __name__ == '__main__':
  main()


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
import sys

sys.setrecursionlimit(210000)


class Node(object):

  def __init__(self, idx, color):
    self.idx = idx
    self.color = color
    self.edges = []
    self.traced = False

  def trace(self, counts, excludes):
    self.traced = True
    num = 1

    for edge in self.edges:
      if edge.traced:
        continue

      excludes[self.color].append(0)
      n = edge.trace(counts, excludes)
      p = n - excludes[self.color].pop()
      counts[self.color] += p * (p - 1) // 2 + p
      num += n

    excludes[self.color][-1] += num

    return num


def main():
  N = int(input())
  nodes = [Node(i, v - 1) for i, v in enumerate(map(int, input().split()))]
  counts = [0] * N
  excludes = [[0] for _ in range(N)]

  for _ in range(N - 1):
    a, b = map(int, input().split())
    nodes[a - 1].edges.append(nodes[b - 1])
    nodes[b - 1].edges.append(nodes[a - 1])

  num = nodes[0].trace(counts, excludes)
  pair = num * (num - 1) // 2 + num

  for i in range(len(counts)):
    p = num - excludes[i][0]
    counts[i] += p * (p - 1) // 2 + p

  for c in counts:
    print(pair - c)


if __name__ == '__main__':
  main()
N,M = map(int,input().split(" "))
p = []
S = []
flag_AC = []
flag_WA = []

for i in range(M):
    inp = input().split(" ")
    p.append(int(inp[0]))
    S.append(inp[1])

for i in range(N):
    flag_AC.append(0)
    flag_WA.append(0)

# n番目の提出ステータスを取得
def Anc(n):
    L = []
    L.append(p[n])
    L.append(S[n])
    return L

AC = 0
WA = 0

for i in range(M):
    data = Anc(i)
    if data[1] == "AC":
        if flag_AC[data[0]] == 0:
            flag_AC[data[0]] = 1
            AC = AC + 1

    if data[1] == "WA":
        if flag_AC[data[0]] == 0:
            flag_WA[data[0]] = flag_WA[data[0]] + 1

for i in range(M):
    data = Anc(i)
    if flag_AC[data[0]] == 0:
        flag_WA[data[0]] = 0
    else:
        flag_WA[data[0]] = flag_WA[data[0]] + 1

print(AC,WA)

### FIXED CODE ###

N,M=map(int,input().split())
ac=[0]*N
wa=[0]*N
pena=0
acsum=0
for i in range(M):
    p,S=input().split()
    p=int(p)-1
    if S == 'AC':
        if ac[p]==0:
            ac[p]=1
            pena+=wa[p]
            acsum+=1
    else:
        wa[p]+=1
print(acsum,pena)
N=int(input())
c=c%10
if c==2 or c==4 or c==5 or c==7 or c==9:
  print('hon')
elif c==0 or c==1 or c==6 or c==8:
    print('pon')
else:
  print('bon')
    

### FIXED CODE ###

N=int(input())
c=N%10
if c==2 or c==4 or c==5 or c==7 or c==9:
  print('hon')
elif c==0 or c==1 or c==6 or c==8:
    print('pon')
else:
  print('bon')
lists = list(int, raw_input().split())
print sorted(lists) 

### FIXED CODE ###

l = map(int, raw_input().split())
a, b, c = sorted(l)
print a, b, c
s = input()
is_ok = True
for i in range(len(s)):
    if i % 2 == 0 and s[i] == "L":
        is_ok = False
        break
    if i % 2 == 1 and s[i] == "R":
        is_ok = False
        break
print("Yes" is_ok else "No")

### FIXED CODE ###

s = input()
is_ok = True
for i in range(len(s)):
    if i % 2 == 0 and s[i] == "L":
        is_ok = False
        break
    if i % 2 == 1 and s[i] == "R":
        is_ok = False
        break
print("Yes" if is_ok else "No")
N, X, Y = map(int,input().split())
a = [0 for _ in range(N - 1)]

for lt in range(1, N+1):
    for rt in range(lt+1, N+1):
        a[min(rt-lt-1, abs(X-lt) + abs(Y-rt))] += 1

print(*a, sep="\n")

### FIXED CODE ###

S = input()

if (S[2] == S[3]) and (S[4] == S[5]):
    print("Yes")
else:
    print("No")
N,M,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
booka = 0
bookb = 0
booknum = 0
time = 0
ba=0
bb=0
lim = 0
while True:
    if booka >= N:
        while time<=K and bookb<M:
            bb += 1
            time += B[bookb]
            bookb += 1
        break
    if bookb>=M:
        while time<=K and booka<N:
            ba += 1
            time += A[booka]
            booka += 1
        break
    if A[booka]<B[bookb]:
        if A[booka]+A[booka+1] > B[bookb]+B[bookb+1]:
            time += B[bookb]
            bookb += 1
        else:
            time += A[booka]
            booka += 1
    else:
        if A[booka]+A[booka+1] <= B[bookb]+B[bookb+1]:
            time += A[booka]
            booka += 1
        else:
            time += B[bookb]
            bookb += 1
    if time >K:
        break
    booknum += 1
    while (booka == N-1 or bookb == M-1):
        if A[booka]<B[bookb]:
            time += A[booka]
            booka += 1
            if time > K:
                booknum += 1
            else:
                break
        else:
            time += B[bookb]
            bookb += 1
            if time > K:
                booknum += 1
            else:
                break
if time > K and (bb!=0 or ba!=0):
    booknum-=1
booknum += (ba+bb)

print(booknum)


### FIXED CODE ###

def getmax(x,y):
    if x>y:
        return x
    else:
        return y
N,M,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

a,b = [0],[0]
for i in range(N):   #a[i]にはAの本をi冊読んだ時の時間がそれぞれ保存されている．
    a.append(a[i]+A[i])  #計算量を減らすため，a[i]（1冊前までにかかる時間）を用いる
for i in range(M):
    b.append(b[i]+B[i])

ans,j = 0,M
for i in range(N+1):
    if a[i]>K:
        break
    while b[j] > K-a[i]:    #Bの本を読んだ場合の処理はここで実行される．
        j -=1
    ans = max(ans, i+j)
print(ans)
x = int(input())
b = x - 30
if b => 0:
  print('Yes')
else:
  print("No")

### FIXED CODE ###

x = int(input())
b = x - 30
if b >= 0:
  print('Yes')
else:
  print("No")
N= int(input())
x= 800 * N
if N < 15:
    y = 0
if 15 <= N < 30:
    y = 200
if 30 <= N < 45:
    y = 400
if 45 <= N < 60:
    y = 600
if 60 <= N < 75:
    y = 800
if 75 <= N < 100:
    y = 1000

print(x-y)

### FIXED CODE ###

N= int(input())
x= 800 * N
if N < 15:
    y = 0
if 15 <= N < 30:
    y = 200
if 30 <= N < 45:
    y = 400
if 45 <= N < 60:
    y = 600
if 60 <= N < 75:
    y = 800
if 75 <= N <90:
    y = 1000
if 90 <= N <=100:
    y = 1200
print(x-y)
n, k = map(int, input().split())

if k == 0:
  print(n**2)
  exit()


ans = 0
for b in range(1, n+1):
  ans += N//b * max(0, b-k)
  ans += max(0, n%b+(1-k))
  
print(ans)

### FIXED CODE ###

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

if k == 0:
  print(n**2)
  exit()


ans = 0
for b in range(1, n+1):
  ans += n//b * max(0, b-k)
  ans += max(0, n%b+(1-k))
  
print(ans)
x,n=map(int,input().split())
if n==0:
  print(x)
else:
  a=list(map(int,input().split()))

  dtmp=100
  for i in range(1,101):
    continueflag=0
    for j in a:
      if j==i:
        continueflag=1
        break
    if continueflag==1:
      continue
    d=abs(x-i)
    if d<dtmp:
      dtmp=d
      ans=i

  print(ans)

### FIXED CODE ###

x,n=map(int,input().split())
if n==0:
  print(x)
else:
  a=list(map(int,input().split()))
  flag=0
  i=0
  while flag==0:
    continueflag=0
    for j in range(n):
      if a[j]==x-i:
        continueflag=1
        break
    if continueflag==0:
      print(x-i)
      break
      
    continueflag=0
    for j in range(n):
      if a[j]==x+i:
        continueflag=1
        break
    if continueflag==0:
      print(x+i)
      break
    i=i+1
a, b = int(input().split())
print(max(a+b, a-b, a*b))

### FIXED CODE ###

a, b = map(int, input().split())
print(max(a+b, a-b, a*b))
a = int(input())
b = input().split()
for i in range(a):
  b[i] = int(b[i])
  
for i in range(a-1):
  if (b[i] > b[i+1]):
    break
if i == a-2:
  print('YES')
else:
  for j in range(a-1,i,-1):
    if (b[j] < b[j-1]):
      break
  temp = b[i]
  b[i] = b[j]
  b[j] = temp
  for k in range(a-1):
    if (b[k] > b[k+1]):
      break
  if k == a-2:
    print('YES')
  else:
    print('NO')

### FIXED CODE ###

a, b = map(int, input().split())
if (a + b)%2 == 0:
  k = (a + b)//2
  print(k)
else:
  print('IMPOSSIBLE')
n, a, b, c, d = map(int, input().split())
s = [0 if i == "#" else 1 for i in input()]
cnt = 0
for si in range(a, max(c, d)):
    if si != 0:
        cnt = 0
    else:
        cnt += 1
        if cnt == 2:
            print("No")
            exit()
if c < d:
    print("Yes")
    exit()
idx = b - 1
cnt = 0
while idx < d:
    if s[idx] == s[idx+1] == s[idx+2] == 1:
        print("Yes")
        exit()
    else:
        idx += 1
print("No")

### FIXED CODE ###

n, a, b, c, d = map(int, input().split())
s = input()
for i in range(a, max(c, d)):
    if s[i-1:i+1] == "##":
        print("No")
        exit()
if c < d:
    print("Yes")
    exit()
for i in range(b-1, d):
    if s[i-1:i+2] == "...":
        print("Yes")
        exit()
print("No")
n = int(input())
xys = {}
xy = []
for _ in range(n):
  x, y = map(int, input().split())
  xys[(x,y)] = True
  xy.append((x,y))

scores = []

for i in range(n):
  for j in range(n):
    if i == j:
      continue
    xi, yi = xy[i]
    xj, yj = xy[j]
    p = xj-xi
    q = yj-yi
    score = n
    for k in range(n):
      xk, yk = xy[k]
      if (xk+p, yk+q) in xys:
        score -= 1
    scores.append(score)

print(min(scores))


### FIXED CODE ###

n = int(input())
xys = {}
xy = []
for _ in range(n):
  x, y = map(int, input().split())
  xys[(x,y)] = True
  xy.append((x,y))

scores = []

if n == 1:
  print(1)
  exit(0)
for i in range(n):
  for j in range(n):
    if i == j:
      continue
    xi, yi = xy[i]
    xj, yj = xy[j]
    p = xj-xi
    q = yj-yi
    score = n
    for k in range(n):
      xk, yk = xy[k]
      if (xk+p, yk+q) in xys:
        score -= 1
    scores.append(score)

print(min(scores))
A=list(map(int,input().split()))
A=sorted(A)
if A[0]==A[1] and A[1]!=A[2]:
  print('Yes')
elif if A[2]==A[1] and A[1]!=A[0]:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

A=list(map(int,input().split()))
A=sorted(A)
if A[0]==A[1] and A[1]!=A[2]:
  print('Yes')
elif A[2]==A[1] and A[1]!=A[0]:
  print('Yes')
else:
  print('No')
n,x=int(input()),input()
g=int(x,2)
c=pow(2,n-1)
j=x.count("1")

for b in x:
    if b=="1":
        p=g-c
        q=j-1
    else:
        p=g+c
        q=j+1
    p%=q
    ret=1
    while p:
        p%=bin(p).count("1")
        ret+=1
    c//=2
    print(ret)

### FIXED CODE ###

n,x=int(input()),input()
o=x.count("1")
if o==1:
    for i,v in enumerate(x):
        if v=="1":print(0)
        else:
            if i!=n-1:
                if x[-1]=="0":print(1)
                else:print(2)
            else:print(2)

else:
    m=o-1
    M=o+1
    mp,mm={0:1},{0:1}
    for i in range(1,n):
        mp[i]=mp[i-1]*2%M
        mm[i]=mm[i-1]*2%m
    A=int(x,2)
    a=A%m
    b=A%M
    rest={0:0}
    for i in range(1,o+1):
        rest[i]=1+rest[i%bin(i).count("1")]
    for i,v in enumerate(x):
        if v=="1":
            print(1+rest[(a-mm[n-i-1])%m])
        else:
            print(1+rest[(b+mp[n-i-1])%M])
import sys

def dfs(heights: int, a_index:int):
    if n < heights:
        return
    
    if m != 0 and a_index <= len(a) -1 and a[a_index] == heights:
        memo[heights] = 0
        a_index += 1
        #print("10",heights)
    else:
        memo[heights] = memo[heights-1] + memo[heights -2]
        #print("13",heights)
    dfs(heights+1,a_index)
    return
    

n,m = list(map(int, input().split()))
memo = [1]*(n+1)
a = []
a_index = 0
if m != 0:
    for i in range(m):
        tmp = int(input())
        if i >= 1 and tmp -1 == a[len(a)-1]:
            print(0)
            sys.exit()
        else:
            a.append(tmp)
            #print(i,a)

    if a[0] == 1:
        memo[1] = 0
        a_index += 1

dfs(2,a_index)
#print(memo)
print(memo[n] % (10**9+7))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

def dfs(heights: int, a_index:int, a_n_1, a_n_2):
    if n < heights:
        return
    
    if m != 0 and a_index <= len(a) -1 and a[a_index] == heights:
        memo[2] = 0
        a_index += 1
        #print("10",heights)
    else:
        memo[2] = a_n_1 + a_n_2 #memo[1] + memo[0]
        #print("13",heights)
    dfs(heights+1,a_index,memo[2],a_n_1)
    return
    

n,m = list(map(int, input().split()))
memo = [1]*(3)
a = []
a_index = 0
if m != 0:
    for i in range(m):
        tmp = int(input())
        if i >= 1 and tmp -1 == a[len(a)-1]:
            print(0)
            sys.exit()
        else:
            a.append(tmp)
            #print(i,a)

    if a[0] == 1:
        memo[1] = 0
        a_index += 1
#a = list(set(a))
#a.sort()
dfs(2,a_index,memo[1],memo[0])
#print(memo)
print(memo[2] % (10**9+7))
str_dict = [0, 0, 0] 
val1 = 0
for i in range(int(input())):
  line = input()
  val1 += line.count('AB')
  if line[0] == 'B' and line[-1] == 'A':
    str_dict[2] += 1
  elif line[0] == 'B':
    str_dict[0] += 1
  elif line[-1] == 'A':
    str_dict[1] += 1
val2 = min(str_dict[0], str_dict[1])
tmp = max(str_dict[0]-val2, str_dict[1]-val2)
val3 = min(tmp, str_dict[2])
val4 = str_dict[2]-val3
if val4 % 2 == 1:
  val4 -= 1
print(val1+val2+val3+val4

### FIXED CODE ###

str_dict = [0, 0, 0] 
val1 = 0
for i in range(int(input())):
  line = input()
  val1 += line.count('AB')
  if line[0] == 'B' and line[-1] == 'A':
    str_dict[2] += 1
  elif line[0] == 'B':
    str_dict[0] += 1
  elif line[-1] == 'A':
    str_dict[1] += 1
if str_dict[2] == 0:
  print(val1+min(str_dict[0], str_dict[1]))
else:
  if str_dict[0]+str_dict[1] > 0:
    print(val1+str_dict[2]+min(str_dict[0], str_dict[1]))
  else:
    print(val1+str_dict[2]-1)
n = 26
d = int(input())
c = list(map(int,input().split()))
s = [[] for i in range(n)]
for i in range(d):
    s[i] = list(map(int,input().split()))
a = 0
last = [0]*n
ans = []
for i in range(d):
    t = int(input())-1
    a += s[i][t]
    last[t] = i+1
    for j in range(n):
        a -= c[j]*(i-last[j]+1)
    ans.append(a)
for i in ans:
    print(i)


### FIXED CODE ###

n = 26
d = int(input())
c = list(map(int,input().split()))
s = [[] for i in range(d)]
for i in range(d):
    s[i] = list(map(int,input().split()))
a = 0
last = [0]*n
for i in range(d):
    t = int(input())-1
    a += s[i][t]
    last[t] = i+1
    for j in range(n):
        a -= c[j]*(i-last[j]+1)
    print(a)
#!/usr/bin/env python3

def main():
    N = int(input())
    def calcSumOfDigit(x,acc=0):
        if x == 0:
            return acc
        else:
            return calcSumOfDigit(x//10,acc+x%10)
    def judge(x):
        return x % 9 == 0
    print("Yes" if judge(calcSumOfDigit(N)) else "No")
    return


if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3

import sys
sys.setrecursionlimit(10**6)

def main():
    N = int(input())
    def calcSumOfDigit(x):
        str_x = str(x)
        acc = 0
        for s in str_x:
            acc += int(s)
            acc %= 9
        return acc
    
    print("Yes" if calcSumOfDigit(N)==0 else "No")
    return


if __name__ == '__main__':
    main()
import collections
import bisect

N, M = map(int, input().split())
P = [list(map(int, input().split())) for i in range(M)]

ans = collections.defaultdict(list)

for p, y in sorted(P):
    ans[p] += [y]
for p, y in P:
    print("%06d%06d"%(p, bisect.bisect(a[p], y)))

### FIXED CODE ###

import collections
import bisect

N, M = map(int, input().split())
P = [list(map(int, input().split())) for i in range(M)]

ans = collections.defaultdict(list)

for p, y in sorted(P):
    ans[p] += [y]
for p, y in P:
    print("%06d%06d"%(p, bisect.bisect(ans[p], y)))
N = int(input())
A = input().split()
A = [int(i) for i in A]

def yakusuu(p):
	A.reverse()
	for i in range(1,p):
		if A[0] % A[i] == 0:
			A.pop(0)
			return
	else:
		return
def syou(k):
	A.sort()
	if A[0] == 0:
		A.pop(0)
		if len(A) > 1:
			A[k-1] = A[k-1] % A[0]
	else:
		A[k] = A[k] % A[0]
	return A
for i in range(N):
	if len(A) >= 1:
		yakusuu(len(A))
while	len(A) > 1:
	syou(len(A)-1)
print(A[0])

### FIXED CODE ###

A,B=map(int,input().split())
if B%A==0:
	print(A+B)
else:
	print(B-A)
N = int(input())
A = list(map(int, input().split()))

import collections
dic=dict(collections.Counter(A))
li=list(dic.values())

ans='No'

if len(li)==3:
    if N%3 == 0:
        if li[0]== N/3 and li[1]==N/3 and li[2]==N/3 and li[3]==1:
            ans='Yes'           
elif len(li)==2:
    if N%3 == 0:
        if li[0]== 2*N/3 or li[1]==2*N/3:
            ans='Yes'
elif len(li)==1:
        if list(dic.keys())[0]==0:
            ans='Yes'

print(ans)

### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import Counter

def main():
    N = int(input())
    a = list(map(int, input().split()))
    l = Counter(a)
    if len(l)==1 and 0 in l:
        print('Yes')
        exit()
    if N%3==0 and len(l)==2 and 0 in l and l[0] == N//3:
        print('Yes')
        exit()
    if N%3==0 and len(l)==3:
        x,y,z = l.keys()
        if l[x] == l[y] == N//3 and x^y^z == 0:
            print('Yes')
            exit()
    print('No')

    

if __name__ == '__main__':
    main()
n = input()
max = 0
min = 0
sum = 0
a=[int(x) for x in input().split()]
for i in range(n):
    if a[i] >= max: max = a[i]
    if a[i] <= min: min = a[i]
    sum += a[i]

print(min,max,sum)


### FIXED CODE ###

n = int(input())
a = sorted([int(x) for x in input().split()])
print(a[0],a[-1],sum(a))
print(int(input()) int(input()) int(input()))

### FIXED CODE ###

X,Y,Z=input().split()
print(Z,X,Y)
from bisect import bisect_left as lower_bound
from bisect import bisect_right as upper_bound
import math
n,d,a=map(int,input().split())
X, H=[], []; ans=0; L=[]
for i in range(n):
  x,h=map(int,input().split())
  L.append((x,h))
L.sort()
for x,h in L:
  X.append(x); H.append(h)
X.append(10**9); H.append(10**9)
imos=[0]*(n+1)
de=0 # decrease count
for i in range(n):
  de+=imos[i]
  HP=H[i]-de*a
  # 右から貪欲にダメージを減らす
  # 敵の体力が残ってるとき
  # print("HP is",HP)
  if HP>0:
    atk_cnt=math.ceil(HP/a) # 何回殴る必要があるか
    de+=atk_cnt
    ans+=atk_cnt
    index=upper_bound(X,X[i]+2*d)
    # print(X,X[i]+2*d)
    # print(index, atk_cnt)
    imos[index]-=atk_cnt
print(ans)

### FIXED CODE ###

from bisect import bisect_left as lower_bound
from bisect import bisect_right as upper_bound
import math
n,d,a=map(int,input().split())
X, H=[], []; ans=0; L=[]
for i in range(n):
  x,h=map(int,input().split())
  L.append((x,h))
L.sort()
for x,h in L:
  X.append(x); H.append(h)
X.append(10**9); H.append(10**9)
imos=[0]*(n+5)
de=0 # decrease count
for i in range(n):
  de+=imos[i]
  HP=H[i]-de*a
  # 右から貪欲にダメージを減らす
  # 敵の体力が残ってるとき
  # print("HP is",HP)
  if HP>0:
    atk_cnt=math.ceil(HP/a) # 何回殴る必要があるか
    de+=atk_cnt
    ans+=atk_cnt
    index=upper_bound(X,X[i]+2*d)
    # print(X,X[i]+2*d)
    # print(index, atk_cnt)
    imos[index]-=atk_cnt
print(ans)
n,k = map(int, input().split())
a = list(map(int, input().strip().split()))
#print(a)
visited = [-1] * (n+1)


now = 0
visited[0] = 0
pre_roop = 0
pos = 0
i = 1
while i < k:
    next = a[now-1]
    #print('roop:',i,now+1,next+1)
    if visited[next] >= 0:
        r = i-visited[next]
        pre_roop = visited[next]
        pos = next
        #print(i,r,pre_roop,next)
        #print(visited)
        break
    else:
        visited[next] = i
        now = next
        #print(i,visited)
        i += 1
l = (k - pre_roop) % r
#print(l)
i = 0
p = pos
while i < l:
    p = a[p-1]
    i +=1

print(p+1)



### FIXED CODE ###

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

for i in range(len(a)):
    a[i] -= 1

visited = [-1] * n
now = 0
visited[0] = 0
pre_roop = 0
pos = 0
i = 1
r = 1
while i <= k:
    next = a[now]
    #print('roop:',i,now+1,next+1)
    if visited[next] >= 0:
        r = i-visited[next]
        pre_roop = visited[next]
        pos = next
        #print(i,r,pre_roop,next)
        #print(visited)
        break
    else:
        visited[next] = i
        now = next
        #print(i,visited)
        i += 1

if i > k:
    print(now + 1)
else:
    l = (k - pre_roop) % r
    #print(l)
    i = 0
    p = pos
    while i < l:
        p = a[p]
        i +=1

    print(p+1)
N,M = map(int,input().split())

A = [[0]]*(N+1)
B = [[0]]*M

for i in range(N):
    A[i] = input()
for j in range(M):
    B[j] = input()

judge = False 
count = 0   
for i in range(N-M+1):
    for j in range(M):
        if B[j]==A[i][i:i+M] and B[j+1]==A[i+1][i:i+M]:
            count += 1
            
            if count == M - 1:
                judge = True
                break
if judge == True:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

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

A = [[0]]*N
B = [[0]]*M

for i in range(N):
    A[i] = input()
for j in range(M):
    B[j] = input()

judge = False 

#行同士で比較していく
for k in range(N-M+1):
    for i in range(N-M+1):
        count = 0
        for j in range(M):
            if B[j]==A[j+i][k:k+M]:
                count += 1
                
                if count == M:
                    judge = True
                    break
            
if judge == True:
    print("Yes")
else:
    print("No")
from numba import njit, int32
import numpy as np


@njit(int32(int32[:], int32[:]))
def main(A, B):
    ans = 0

    for a in A:
        B[a] += 1

    for a in set(A):
        v = 2*a
        while v <= 10**6:
            B[v] += 1
            v += a

    for a in A:
        if B[a] == 1:
            ans += 1

    return ans


if __name__ == '__main__':
    N = int(input())
    A = [int(i) for i in input().split()]
    B = [0]*(10**6+1)
    ans = main(np.array(A), np.array(B))
    print(ans)


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    A = [int(i) for i in input().split()]
    A.sort()
    B = [True]*(10**6+1)

    from collections import Counter
    c = Counter(A)
    bl = set()
    for k, v in c.items():
        if v >= 2:
            bl.add(k)

    ans = 0
    for a in set(A):
        if a not in bl and B[a]:
            ans += 1
        for i in range(1, 10**6):
            if 10**6 < a*i:
                break
            B[a*i] = False
    print(ans)


if __name__ == '__main__':
    main()
import fraction
a, b, c = map(int, input().split())
print("YES" if c%(fraction.gcd(a,b)) == 0 else "NO")

### FIXED CODE ###

import fractions
a, b, c = map(int, input().split())
print("YES" if c%(fractions.gcd(a,b)) == 0 else "NO")
import sys
input = sys.stdin.readline


def main():
    n = int(input())
    A = [int(i) for i in input().split()]

    # MOD = 10 ** 9 + 7
    A.sort()
    s = set()

    ans = 0
    if A[0] != A[1]:
        ans += 1

    for i in range(1, n):
        if A[i - 1] == A[i]:
            continue

        for j in range(i):
            if j in s:
                continue
            elif A[i] % A[j] == 0:
                s.add(i)
                break
        else:
            ans += 1
            # print(f"{i = }, {j = }, {ans = }")

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import numpy as np
import sys
input = sys.stdin.readline


def main():
    n = int(input())
    A = np.array([int(i) for i in input().split()])

    max_dp = np.max(A) + 1
    dp = np.zeros(max_dp, dtype="int32")

    for a in A:
        if dp[a] >= 2:
            continue
        fancy = np.arange(a, max_dp, a)
        dp[fancy] += 2
        dp[a] -= 1
    print(np.sum(dp == 1))


if __name__ == '__main__':
    main()