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

from collections import deque
from itertools import chain


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

edges = [[] for _ in range(n + 1)]
for _ in range(m):
    u, v = map(int, input().split())
    edges[u].append(v)

s, t = map(int, input().split())

def find_next(pos, e):
    c1 = e[pos]
    c2 = chain.from_iterable([e[c]for c in c1])
    return list(chain.from_iterable([e[c] for c in c2]))

visited = [0 for _ in range(n + 1)]
cost = 0
st = deque([(s, 0)])
ans = -1
pre = None
while len(st):
    pos, cost = st.popleft()
    if pos == t:
        ans = cost
        break
    for n in find_next(pos, edges):
        if visited[n] == 0:
            st.append((n, cost + 1))
            visited[n] = 1

print(ans)

### FIXED CODE ###

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

class Bridge:
    def __init__(self, nodeA, nodeB):
        self.edges = [BridgeEdge(nodeA, self), BridgeEdge(nodeB, self)]
        nodeA.addEdge(self.edges[1])
        #nodeB.addEdge(self.edges[0])

class BridgeEdge:
    def __init__(self, node, edge):
        self.edge = edge
        self.node = node
        self.flag = 0

class Node:
    def __init__(self, id):
        self.id = id
        self.bridges = []
    def addEdge(self, bridgeEdge):
        self.bridges.append(bridgeEdge)
    def __repr__(self):
        return "({})".format(self.id)

nodes = [Node(i) for i in range(N+1)]

for ui, vi in (map(int, input().split()) for _ in range(M)):
    Bridge(nodes[ui], nodes[vi])

S, T = map(int, input().split())

#nodes[S].flag = 1
s = [(None, nodes[S], 0)]
idx = 0
isOK = False
while idx < len(s):
    pre, cur, level = s[idx]
    idx += 1
    nxtlevel = level + 1
    nxtflag = 1 << (nxtlevel % 3)

    for nxt in cur.bridges:
        if (nxt.flag & nxtflag) == 0:
            nxt.flag |= nxtflag 
            if nxt.node is nodes[T] and nxtflag == 1:
                isOK = True
                break
            s.append((cur, nxt.node, nxtlevel))
    else:
        continue
    break
if isOK:
    print(nxtlevel//3)
else:
    print(-1)
### BUGGY CODE ###

import sys
from collections import deque

N = int(input())
A = [deque([int(i) for i in input().split()]) for i in range(N)]

ans=0
empty = [deque() for n in range(N)]
first_fight = set([i for i in range(N)])
record = set()

#前日に試合をした選手のみにマッチングを確認する(これで最悪O(n^2))。
#そうしないと、「while True」の部分で最悪n(n-1)/2の計算量がかかり、O(n^3)となって詰む
first = True

while True:
    change=False
    stamina=[1]*N
    if first is True:
        pre_fight = first_fight
    else:
        pre_fight = record
        record = set()
    for g in pre_fight:
        if A[g]!=deque() and stamina[g]==1 and stamina[A[g][0]-1]==1:
            if g+1 == A[A[g][0]-1][0]:
                _pop = A[g].popleft()
                A[_pop-1].popleft()
                stamina[g]=0
                stamina[_pop-1]=0
                change=True
                record.add(g)
                record.add(_pop-1)
    first=False
    ans+=1
    if change is False:
        break
    if A==empty:
        print(ans)
        sys.exit()

print(-1)

### FIXED CODE ###

import sys
from collections import deque

N = int(input())
A = [deque([int(i) for i in input().split()]) for i in range(N)]

ans=0
empty = [deque() for i in range(N)]
pre_fight = set([i for i in range(N)])
record = set()

while True:
    for g in pre_fight:
        if A[g]!=deque():
            if g+1 == A[A[g][0]-1][0]:
                record.add(g)
                record.add(A[g][0]-1)
    if record==set():
        break
    else:
        for i in record:
            A[i].popleft()
    ans+=1
    pre_fight = record
    record = set()
    if A==empty:
        print(ans)
        sys.exit()

print(-1)
### BUGGY CODE ###

N,A,B=map(int,input().split())
P=[int(i) for i in input().split()]
dp=[[10**19]*(N+1) for i in range(N+1)]
dp[0][0]=0
for i in range(1,N+1):
    for j in range(N+1):
        #if dp[i-1][j]==10**19:
            #continue
        if j < P[i-1]:
            dp[i][P[i-1]]=min(dp[i][P[i-1]],dp[i-1][j])
            dp[i][j]=min(dp[i][j],dp[i-1][j]+A)
        else:
            dp[i][j]=min(dp[i][j],dp[i-1][j]+B)
#print(dp)
print(min(dp[-1]))

### FIXED CODE ###

N,A,B=map(int,input().split())
P=[int(i) for i in input().split()]
dp=[10**19]*(N+1)
dp[0]=0
for i in range(1,N+1):
    ndp=[10**19]*(N+1)
    for j in range(N+1):
        if j < P[i-1]:
            ndp[P[i-1]]=min(ndp[P[i-1]],dp[j])
            ndp[j]=min(ndp[j],dp[j]+A)
        else:
            ndp[j]=min(ndp[j],dp[j]+B)
    dp=ndp
print(min(dp))
### BUGGY CODE ###

N = int(input())
S = []
for _ in range(N):
  s = list(input())
  s.sort()
  S.append("".join(s))

s = list(set(S))
ans = 0
for i in range(len(s)):
  a = S.count(s[i])
  if a == 1: continue
  ans += a * (a-1) // 2
print(ans)

### FIXED CODE ###

N = int(input())
s = {}
for _ in range(N):
  a = "".join(sorted(input()))
  if a not in s:
    s[a] = 0
  else: s[a] += 1

import math
ans = 0
for v in s.values():
  if v < 2: ans += v
  if v > 1: ans += v*(v+1)//2
print(ans)
### BUGGY CODE ###

c=0
n=int(input())
s=input().split()
q=int(input())
t=input().split()
for i in t:
	for j in s:
		if int(i)==int(j):
			c +=1
			break
print(c)


### FIXED CODE ###

c=0
n=int(input())
s=input().split()
q=int(input())
t=input().split()
s.sort()

print(len(set(s)&set(t)))
### BUGGY CODE ###

from sys import stdin
import numpy as np

N = int(stdin.readline().rstrip().split()[0])
A = [int(x) for x in stdin.readline().rstrip().split()]
# N, X = [int(x) for x in stdin.readline().rstrip().split()]

def G(_a, _b):
  if _a>=_b:
    a, b = _a, _b
  else:
    a, b = _b, _a
  
  while True:
    c = a%b
    if c == 0:
      break
    a,b = b,c
  
  return b
L=list(set(A))
while True:
  if len(L)==1:
    ans = L[0]
    break
  elif min(L)==1:
    ans = 1
    break
  else:
    g = G(L[-2], L[-1])
    L[-2] = g
    L.pop()
    
print(ans)

### FIXED CODE ###

from sys import stdin
import numpy as np

N = int(stdin.readline().rstrip().split()[0])
A = [int(x) for x in stdin.readline().rstrip().split()]
# N, X = [int(x) for x in stdin.readline().rstrip().split()]

def G(_a, _b):
  if _a>=_b:
    a, b = _a, _b
  else:
    a, b = _b, _a
  
  while True:
    c = a%b
    if c == 0:
      break
    a,b = b,c
  
  return b

L = np.array(list(set(A)))
mini = np.min(L)
yaku = [1]
i=2
r_mini = np.sqrt(mini)
while i<=r_mini:
  if mini%i==0:
    yaku.append(i)
  i+=1
yaku2 = list(map(lambda x: int(mini/x), yaku))
yaku = yaku[::-1]
yaku2.extend(yaku)
for y in yaku2:
  if np.sum(L%y)==0:
    ans = y
    break

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

n = int(input())
l = list(100 for _ in range(n+1))
l[0] = 0
for i in range(n+1):
  for j in range(i+1,n+1):
    l[j] = min(l[j],l[i]+(j-i))
#  print(l)
  for k in range(7):
    if i+6**k<=n:
      l[i+6**k] = min(l[i+6**k],l[i]+1)
 # print(l)
  for m in range(7):
    if i+9**m<=n:
      l[i+9**m] = min(l[i+9**m],l[i]+1)
  #print(l)
print(l[-1])
      

### FIXED CODE ###

n = int(input())
l = list(i for i in range(n+1))
for i in range(n+1):
  for k in range(7):
    if i+6**k<=n:
      l[i+6**k] = min(l[i+6**k],l[i]+1)
 # print(l)
  for m in range(7):
    if i+9**m<=n:
      l[i+9**m] = min(l[i+9**m],l[i]+1)
  #print(l)
print(l[-1])
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
dp=[0,abs(a[0]-a[1])]
co=0
g=float('inf')
for i in range(2,n):
  f=g
  for j in range(max(0,i-k),i):
   f=min(f,abs(a[i]-a[j])+dp[j])
  dp.append(f)
print(dp[-1])


### FIXED CODE ###

import sys
input = sys.stdin.readline
def fun(n,a,k):
 dp=[0]*n
 for i in range(1,n):
  dp[i]=min([dp[j]+abs(a[i]-a[j]) for j in range(max(0,i-k),i)])
 print(dp[len(dp)-1])
if __name__ == '__main__':
 n,k = map(int, input().split())
 a=list(map(int,input().split()))
 fun(n,a,k)
### BUGGY CODE ###

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

#dp=[float("inf")]*N
#dp[0]=0
dp=[0]
for i in range(1,N):
  tmp=float("inf")
  for k in range(1,K+1):
    if i-k<0: break
    #dp[i]=min(dp[i],dp[i-k]+abs(h[i]-h[i-k]))
    tmp=min(tmp,dp[i-k]+abs(h[i]-h[i-k]))
  #dp[i]=tmp
  dp+=[tmp]

print(dp[N-1])

### FIXED CODE ###

import numpy as np
#https://yottagin.com/?p=1650

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

#dp=[float("inf")]*N
#dp[0]=0
#dp=[0]
dp=np.zeros(N,dtype=int)
h=np.array(h)

for i in range(1,N):
  start=max(0,i-K)
  #start~i-1
  dp[i]=min(dp[start:i]+np.abs(h[i]-h[start:i]))
  #tmp=float("inf")
  #for k in range(1,K+1):
    #if i-k<0: break
    #dp[i]=min(dp[i],dp[i-k]+abs(h[i]-h[i-k]))
    #tmp=min(tmp,dp[i-k]+abs(h[i]-h[i-k]))
  #dp[i]=tmp
  #dp+=[tmp]

print(dp[N-1])
### BUGGY CODE ###

import numpy as np

def main():
	n, m = list(map(int, input().split()))
	nums = list(map(int, input().split()))

	num2match = {key:val for key, val in {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}.items() if key in nums}
	dp = ["na" for i in range(n + 1)] # マッチをn本使った時に作れる最大の数

	dp[0] = ""
	val_set = set(num2match.values())
	match2num = {v:max([key for key, val in num2match.items() if val == v]) for v in val_set}

	for i in range(2, n + 1):
		for val in val_set:
			if i >= val and dp[i - val] != "na":
				tmp = str(match2num[val]) + str(dp[i - val])
				if dp[i] == "na" or int(tmp) >= int(dp[i]):
					dp[i] = tmp

	print(int(dp[n]))

if __name__ == '__main__':
	main()

### FIXED CODE ###

import math
def main():
	n, m = list(map(int, input().split()))
	nums = list(map(int, input().split()))
	
	d = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
	num2match = {key:val for key, val in d.items() if key in nums}
	
	dp = [-1 for i in range(n + 1)]
	dp_keta = [0 for i in range(n + 1)]

	dp[0] = 0
	val_set = list(set(num2match.values()))
	match2num = {v:max([int(key) for key, val in num2match.items() if val == v]) for v in val_set}

	cnt = 0
	for i in range(2, n + 1):
		for val in val_set:
			#print(val)
			cnt += 1
			if i >= val and dp[i - val] >= 0:
				tmp = match2num[val] * (10 ** dp_keta[i - val]) + dp[i - val]
				dp[i] = max(dp[i], tmp)
				dp_keta[i] = max(dp_keta[i], dp_keta[i - val] + 1)

	#print(num2match)
	#print(match2num)
	#print(dp)
	#print(dp)
	print(int(dp[n]))
	#print(cnt)
 
if __name__ == '__main__':
	main()
### BUGGY CODE ###

import math

while True:
    try:
        c = 0
        n = int(input())
        for i in range(n,1,-1):
            if i == 2:
                c += 1
                break
            elif i%2 == 0:
                continue
            else:
                j = 3
                while j <= math.sqrt(i):
                    if i%j == 0:
                        break
                    j += 2
                else:
                    c += 1
        print(c)
    except:
        break

### FIXED CODE ###

n = 999999
c = [1 for i in range(n)]
c[0] = 0
i = 2
while i**2 <= n:
    j = i*2
    while j <= n:
        c[j - 1] = 0
        j += i
    i += 1

while True:
    try:
        n = int(input())
        print(sum(c[:n]))
    except:
        break
### BUGGY CODE ###

n = int(input())
s = input()

rs = []
gs = []
bs = []
for i, e in enumerate(s):
  if e == 'R':
    rs.append(i)
  if e == 'G':
    gs.append(i)
  if e == 'B':
    bs.append(i)
      
saidai = len(rs) * len(gs) * len(bs)
if saidai == 0:
  print('0')
else:
  for i in rs:
    for j in gs:
      mi = i if i < j else j
      ma = j if i < j else i
      p = [mi - (ma - mi), mi + (ma - mi)/2, ma + (ma - mi)]
      for e in p:
        if e in bs:
          saidai -= 1
  print(int(saidai))

### FIXED CODE ###

n = int(input())
s = input()

rs = {}
gs = {}
bs = {}

for i, e in enumerate(s):
  if e == 'R':
    rs[i] = ''
  if e == 'G':
    gs[i] = ''
  if e == 'B':
    bs[i] = ''
    
saidai = len(rs) * len(gs) * len(bs)
if saidai == 0:
  print('0')
else:
  a = max(bs.keys())
  b = min(bs.keys())
  for i in rs.keys():
    for j in gs.keys():
      mi = i if i < j else j
      ma = j if i < j else i
      p = [mi - (ma - mi), mi + (ma - mi)/2, ma + (ma - mi)]
      for e in p:
        if e%1 != 0 or e < b or e > a:
          continue
        if e in bs:
          saidai -= 1
  print(int(saidai))
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
now=0
l=[1]
ll=[]
for i in range(n*2):
    now=a[now]
    if now not in l:
        l.append(now)
    elif now in l and now not in ll:
        ll.append(now)
    else:
        break
    now-=1

b=len(l)
c=len(ll)
num=b-c
if k>num:
    k=(k-num)%c
    print(ll[k])
else:
    k=k%b
    print(l[k])

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
l=[1]
di={}
di[1]=1
for i in a:
    b=a[l[-1]-1]
    if b in di:
        x=b
        break
    l.append(b)
    di[b]=1
t1=0
for j in l:
    if j==x:
        break
    else:
        t1+=1
t2=len(l)-t1
if k<=t1:
    print(l[k])
else:
    num=(k-t1)%t2
    print(l[t1+num])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
a.sort()

flg = [True for _ in range(10 ** 6 + 1)]
for i in range(n-1):
    if a[i] == a[i+1]:
        flg[a[i]] = False

ans = 0
for i in range(n):
    if flg[a[i]]:
        ans += 1

    tmp = 1
    while tmp * a[i] <= 10 ** 6:
        flg[tmp * a[i]] = False
        tmp += 1

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
a.sort()

flg = [True for _ in range(10 ** 6 + 1)]
for i in range(n-1):
    if a[i] == a[i+1]:
        flg[a[i]] = False

ans = 0
for x in set(a):
    if flg[x]:
        ans += 1

    tmp = 1
    while tmp * x <= 10 ** 6:
        flg[tmp * x] = False
        tmp += 1

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

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

li.sort()
move_cost = [li[i+1] - li[i] for i in range(m-1)]


for i in range(n-1):
    if len(move_cost) == 0:
        break
    move_cost.remove(max(move_cost))

print(sum(move_cost))

### FIXED CODE ###

n, m = map(int, input().split())
li = list(map(int, input().split()))
 
li.sort()
move_cost = [li[i+1] - li[i] for i in range(m-1)]
move_cost.sort()
if n > 1:
    move_cost = move_cost[:-n+1]

print(sum(move_cost))
### BUGGY CODE ###

import sys
import os

def file_input():
    f = open('ABC167/input.txt', 'r')
    sys.stdin = f

def main():
    #file_input()
    # int(input())
    A,B,C,K=map(int, input().split())

    sum=0
    for i in range(K):
        if A!=0:
            A-=1
            sum+=1
        elif B!=0:
            B-=1
        elif C!=0:
            C-=1
            sum-=1
    print(sum)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import os

def file_input():
    f = open('ABC167/input.txt', 'r')
    sys.stdin = f

def main():
    #file_input()
    # int(input())
    A,B,C,K=map(int, input().split())

    sum=0
    if K>A:
        sum+=A
        K-=A
        if K>B:
            K-=B
            sum-=K        
    else:
        sum+=K

    print(sum)

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

N = int(input())
A = [input() for i in range(N)]

prev = []
next = 0
count = 0
while(next not in prev and count <= N):
    prev.append(next)
    next = int(A[next])-1
    count += 1
    if(next == 1):
        print(count)
        break
else:
    print(-1)


### FIXED CODE ###

N = int(input())
A = [input() for i in range(N)]

prev = []
next = 0
count = 0
while(count < N):
    next = int(A[next])-1
    count += 1
    if(next == 1):
        print(count)
        break
else:
    print(-1)
### BUGGY CODE ###

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

X = set(A)
L = len(X)

S= []
for x in X:
    n = A.count(x)
    S.append(n)

S = sorted(S)

ans = sum(S[:max(0,L - K)])

print(ans)

### FIXED CODE ###

N, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

X = [0] * N

for i in range(N):
    X[A[i] - 1] += 1

X = sorted(X, reverse=True)

S = sum(X[:K])

ans = N - S

print(ans)