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

#!/usr/bin/env python3
import sys


def solve(s: str):

    res = 0

    s = list(s)

    i = 0
    endi = len(s) - 2
    while i < endi:
        if s[i] == "A" and s[i+1] =="B" and s[i+2] =="C":
            ai = -1
            for j in range(i-1,-1,-1):
                if j >=0 and s[j] == "A":
                    ai = j 
                else:
                    break
            if ai >= 0:
                s[ai]   = "B"
                s[ai+1] = "C"
                s[ai+2] = "A"

                res += 1
                for k in range(ai+3,i+3):
                    s[k] = "A"
                    res += 1
            else:
                s[i]   = "B"
                s[i+1] = "C"
                s[i+2] = "A"
                res += 1
            i += 1
        i += 1

    print(res)

    return


# Generated by 1.1.4 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()
    s = next(tokens)  # type: str
    solve(s)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

def conv2num(c):
    if c == "A":
        return 1
    elif c == "D":
        return 2
    elif c == "B":
        return 3
    else:
        return 4

def solve(s: str):

    res = 0
    s = s.replace("BC","D")
    s = [ conv2num(c) for c in s ]

    acnt = 0
    for i,c in enumerate(s):
        if c == 1:
            acnt += 1
        elif c == 2:
            res += acnt
        else:
            acnt = 0


    print(res)

    return


# Generated by 1.1.4 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()
    s = next(tokens)  # type: str
    solve(s)

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

a,b,c,d=map(int,input().split())
mod=998244353
dct=[[[-1]*3 for _ in range(d+1)] for _ in range(c+1)]
#from collections import defaultdict

import sys
sys.setrecursionlimit(10**7)
def dp(i,j,bl):
  #print(i,j,bl)
  if dct[i][j][bl]>0:
    return dct[i][j][bl]
  if (i,j)==(a,b):
    return 1 if bl==0 else 0
  if i<a or j<b:
    return 0
  if i==a:
    if bl==2:
      ret=0 if j-b<2 else pow(i,j-b)-pow(i-1,j-b-1)*(j-b)-pow(i-1,j-b)
    elif bl==1:
      ret=0 if j-b<1 else pow(i-1,j-b-1)*(j-b)
    elif bl==0:
      ret=pow(i-1,j-b)
  elif bl==2:
    ret=dp(i,j-1,1)+dp(i,j-1,2)*i
  elif bl==1:
    ret=(dp(i-1,j,0)+dp(i-1,j,1)+dp(i-1,j,2))*j
  else:
    ret=dp(i,j-1,0)*(i-1)
  ret%=mod
  dct[i][j][bl]=ret
  return ret

print((dp(c,d,0)+dp(c,d,1)+dp(c,d,2))%mod)
#print(dp(c,d,0),dp(c,d,1),dp(c,d,2))
#print(a,b,c,d)


### FIXED CODE ###

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

dp1=[[0]*(d+1) for _ in range(c+1)]
dp2=[[0]*(d+1) for _ in range(c+1)]

for i in range(b+1,d+1):
  if a==1:
    dp1[a][i]=1 if i==b+1 else 0
    dp2[a][i]=0 if i==b+1 else 1
  else:
    dp1[a][i]=(pow(a-1,i-b-1,mod)*(i-b))%mod
    dp2[a][i]=(pow(a,i-b,mod)-dp1[a][i])%mod
for i in range(a+1,c+1):
  dp1[i][b]=pow(b,i-a,mod)
  dp2[i][b]=0
dp2[a][b]=1
for i in range(a+1,c+1):
  for j in range(b+1,d+1):
    dp1[i][j]=(j*(dp1[i-1][j]+dp2[i-1][j]))%mod
    dp2[i][j]=(dp1[i][j-1]+dp2[i][j-1]*i)%mod
print((dp1[c][d]+dp2[c][d])%mod)

"""
print('dp1')
for x in dp1:
  print(x)
print('dp2')
for x in dp2:
  print(x)
"""
### BUGGY CODE ###

L,R = map(int,input().split(" "))
min = 1000000000000
for i in range(L,R+1):
  for j in range(i+1,R+1):
    tmp = (i%2019 * j%2019)%2019
    if min > tmp:
      min = tmp
print(min)


### FIXED CODE ###

L,R = map(int,input().split(" "))
min = 1000000000000
if (R-L >= 2019):
    print("0")
    quit()
for i in range(L%2019,R%2019 + 1):
  for j in range(i+1, R%2019 + 1):
    tmp = (i * j)%2019
    if min > tmp:
      min = tmp
print(min)
### BUGGY CODE ###

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

for i, v in enumerate(a):
    g[i+1] = v

def find_num(target):
    path = 1
    target_ = g[target]
    while target_ != target:
        target_ = g[target_]
        path += 1
    return path

target = 1
visited = []
flag = False
for i in range(k):
    target = g[target]
    if target not in visited:
        visited.append(target)
    else:
        p = find_num(target)
        flag = True
        break
if flag:
    for _ in range((k-1-i)%p):
        target = g[target]
    print(target)
else:
    print(target)

### FIXED CODE ###

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

for i, v in enumerate(a):
    g[i+1] = v

def find_num(target):
    path = 1
    target_ = g[target]
    while target_ != target:
        target_ = g[target_]
        path += 1
    return path

target = 1
visited = dict()
flag = False
for i in range(k):
    target = g[target]
    if target not in visited:
        visited[target] = True
    else:
        p = find_num(target)
        flag = True
        break
if flag:
    for _ in range((k-1-i)%p):
        target = g[target]
    print(target)
else:
    print(target)
### BUGGY CODE ###

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

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


for i in range(N):
    a=A[i]
    for j in range(2,a):
        temp=0
        while a%j==0:
            a=a//j
            temp+=1
        lcm[j]=max(lcm[j],temp)
        if a==1 or j*j>A[i]:
            break
    if a!=1:
        lcm[a]=max(lcm[a],1)
                
        
l=1
for d in lcm.items():
    l*=pow(d[0],d[1])
    

ans=0
mod=10**9+7

for i in range(N):
    ans+=l//A[i]
    ans%=mod
    
print(ans%mod)




### FIXED CODE ###

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

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


for i in range(N):
    a=A[i]
    for j in range(2,a):
        temp=0
        while a%j==0:
            a=a//j
            temp+=1
        lcm[j]=max(lcm[j],temp)
        if a==1 or j*j>A[i]:
            break
    if a!=1:
        lcm[a]=max(lcm[a],1)
                
        
l=1
for d in lcm.items():
    l*=pow(d[0],d[1])
    

ans=0
mod=10**9+7

for i in range(N):
    ans+=l//A[i]
    
print(ans%mod)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np 
def main():
    H, W = map(int , readline().split())
    A = np.array([1 if i == ord('.') else 0 for i in read()], np.int16).reshape(H, W+1)
    A = np.vstack((A, np.zeros(W+1, np.int16)))
    row = np.zeros((H+1, W+1), np.int16)
    clumn = np.copy(row)

    for j in range(H):
        prev = 0
        start = 0
        for i in range(W+1):
            if A[j, i] == 1:
                if prev == 0:
                    start = i 
                    prev = 1
            else:
                if prev == 1:
                    n = i - start
                    for k in range(start, i):
                        row[j, k] = n
                    prev = 0 
    

    for i in range(W):
        prev = 0
        start = 0
        for j in range(H+1):
            if A[j, i] == 1:
                if prev == 0:
                    start = j
                    prev = 1
            else:
                if prev == 1:
                    n = j - start
                    for k in range(start, j):
                        clumn[k, i] = n
                    prev = 0

    print((row+clumn).max()-1)
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np 
import itertools as it
def main():
    H, W = map(int, readline().split())
    G = np.zeros((H+2, W+2), np.int16)
    G[1:-1, 1:] = (np.frombuffer(read(H*(W+1)), dtype='B') == ord('.')).reshape((H, W+1))
    def solve(G):
        left = np.zeros(G.shape, np.int16)
        for i in range(G.shape[0]):
            left[i, ] = np.arange(G.shape[1])
        left[G>0] = 0
        np.maximum.accumulate(left, out=left, axis=1)

        rG = G[..., ::-1]
        right = np.zeros(G.shape, np.int16)
        for i in range(G.shape[0]): 
            right[i, ] = np.arange(G.shape[1])
        right[rG>0] = 0
        np.maximum.accumulate(right, out=right, axis=1)

        right = G.shape[1] - right[..., ::-1]-1
        scoreres = (right-left-1) 
        scoreres[G==0] = 0
        return scoreres

    print((solve(G)+solve(G.T).T-1).max())
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import heapq

city_num, road_num, init_silver = map(int, input().split())
init_silver  = min(2500, init_silver)

G = [[] for _ in range(city_num)]
for _ in range(road_num):
    A, B, cost, time_cost = map(int, input().split())
    A, B = A-1, B-1
    G[B].append([A, cost, time_cost])
    G[A].append([B, cost, time_cost])

for n in range(city_num):
    cost, time_cost = map(int, input().split())
    G[n].append([n, -cost, time_cost])

dp = [[float("inf")] * 2501 for _ in range(city_num)]
dp[0][init_silver] = 0
hq = [(0, 0, init_silver)]
while hq:
    time, node, silver = heapq.heappop(hq)
    for to, silver_cost, time_cost in G[node]:
        remain = min(silver - silver_cost, 2500)
        if remain < 0:
            continue
        dp_next_value = time + time_cost
        if dp[to][remain] <= dp_next_value:
            continue
        dp[to][remain] = dp_next_value
        hq.append([dp_next_value, to, remain])
print(*[min(d) for d in dp[1:]], sep="\n")

### FIXED CODE ###

import heapq
N, M, init_silver = map(int, input().split())
MAX_COST = 2500
init_silver = min(init_silver, MAX_COST)

G = [[] for _ in range(N)]
for i in range(M):
    u, v, silver_cost, time_cost = map(int, input().split())
    u, v = u - 1, v - 1
    G[u].append([v, silver_cost, time_cost])
    G[v].append([u, silver_cost, time_cost])

change_rate, change_cost = [], []
for i in range(N):
    rate, cost = map(int, input().split())
    G[i].append([i, -rate, cost])  # これを追加！
    change_rate.append(rate)
    change_cost.append(cost)


# dp[i][silver] := 頂点iにいて銀貨をsilver枚持っているような状況を作るために必要な最小時間
dp = [[float('inf')] * (MAX_COST + 1) for _ in range(N)]
dp[0][init_silver] = 0

# 優先度付きキュー: (time, node, silver)
hq = [(0, 0, init_silver)]
while hq:
    time, node, silver = heapq.heappop(hq)

    for to, silver_cost, time_cost in G[node]:
        remain_silver = min(silver - silver_cost, MAX_COST)
        if remain_silver < 0:
            continue

        dp_next_value = time + time_cost
        if dp[to][remain_silver] <= dp_next_value:
            continue

        dp[to][remain_silver] = dp_next_value
        heapq.heappush(hq, (dp_next_value, to, remain_silver))

print(*[min(d) for d in dp[1:]], sep="\n")
### BUGGY CODE ###

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

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

d = defaultdict(int)
for i in A :
    d[i] += 1

for i in A :
    d[i] -= 1
    ans = 0
    for a in d :
        ans += d.get(a)*(d.get(a)-1)//2
    print(ans)
    d[i] += 1


### FIXED CODE ###

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

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

d = defaultdict(int)
for i in A :
    d[i] += 1

ans = 0
ans2 = defaultdict(int)
for a in d :
    ans += d.get(a)*(d.get(a)-1)//2
    ans2[a] = d.get(a)*(d.get(a)-1)//2 - (d.get(a)-1)*(d.get(a)-2)//2

for i in A :
    print(ans - ans2[i])
### BUGGY CODE ###

N, M = [int(i) for i in input().split()]

PY = []
PYd = {i:[] for i in range(1, N+1)}

for i in range(M):
    x, y = [int(i) for i in input().split()]
    PYd[x].append(y)
    PY.append((x,y))
    
for i in PYd.keys():
    PYd[i].sort()
    
for p,y in PY:
    str_p = str(p).zfill(6)
    index = str(PYd[p].index(y)+1).zfill(6)
    print(str_p+index)

### FIXED CODE ###

from collections import defaultdict
import bisect

N, M = [int(i) for i in input().split()]

PY = []
PYd = defaultdict(list)

for i in range(M):
    x, y = [int(i) for i in input().split()]
    PYd[x].append(y)
    PY.append((x,y))
    
for i in PYd.keys():
    PYd[i].sort()
    
for p,y in PY:
    str_p = str(p).zfill(6)
    index = str(bisect.bisect(PYd[p], y)).zfill(6)
    print(str_p+index)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[61*[0]for _ in range(n)]
c=[0]*61
for i in range(n):
  s=bin(a[i])[2:].zfill(61)
  for j in range(61):
    if s[-j-1]=="1":
      c[j]+=1
      b[i][j]=1
ans=0
mod=10**9+7
mod*=2
for i in range(n):
  x=1
  for j in range(61):
    if b[i][j]==1:s=n-c[j]
    else:s=c[j]
    ans+=s*x
    x=(x*2)%mod
    ans%=mod
print(ans//2)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
ans=0
x=1
for i in range(60):
  z=o=0
  for j in range(n):
    if a[j]%2:o+=1
    else:z+=1
    a[j]//=2
  ans+=(x*o*z)%mod
  ans%=mod
  x=(x*2)%mod
print(ans)
### BUGGY CODE ###

n=int(input())
s=list(input())
# n=19
# s=list(str(3141592653589793238))
a=[0]*1000
s=[int(i) for i in s]
res=[0,0,0]
#print(s)
for i in range(0,n-2):
    b=100*s[i]
    for j in range(i+1,n-1):
        b2=b+10*s[j]
        for k in range(j+1,n):
            b3=b2+s[k]-1
            if a[b3]!=1:
                a[b3]+=1
print(sum(a))

### FIXED CODE ###

n=int(input())
s=list(input())
s=[int(i) for i in s]
res=[[0 for i in range(10)]for i in range(n)]
for i in range(n-1,0,-1):
    for j in range(10):
        res[i-1][j]=res[i][j]
    res[i-1][s[i]]+=1
cnt=0
#print(res)
a=[0]*10
for i in range(n-2):
    if a[s[i]]!=0:
        continue
    a[s[i]]+=1
    b=[0]*10
    for j in range(i+1,n-1):
        if b[s[j]]==0:
            b[s[j]]+=1
            cnt+=10-res[j].count(0)

print(cnt)
### BUGGY CODE ###

k,s=map(int,input().split())
cnt=0

for x in range(k+1):
  for y in range(k+1):
    for z in range(k+1):
      if x+y+z==s:
        cnt+=1
print(cnt)


### FIXED CODE ###

k,s=map(int,input().split())
cnt=0

for x in range(k+1):
  for y in range(k+1):
    z=s-x-y
    if x+y<=s and z<=k:
      cnt+=1
print(cnt)
### BUGGY CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


h,w = list(map(int, input().split()))
a = [None]*h
for i in range(h):
    a[i] = input()
    if "S" in a[i]:
        start = (i*w+a[i].index("S"))
    if "T" in a[i]:
        goal = (i*w+a[i].index("T"))
if start%w==goal%w or start//w==goal//w:
    val = -1
else:
    import scipy.sparse
    data = []
    rs = []
    cs = []
    def append(u,v):
        data.append(1)
        rs.append(u)
        cs.append(v)
        
    for i in range(h*w):
        if i not in (start, goal):
            append(2*i, 2*i+1)
    start = start*2+1
    goal = goal*2
    def add(i0,j0,i1,j1):
        u = i0*w+j0
        v = i1*w+j1
        append(2*u+1, 2*v)
#         append(2*v+1, 2*u)
    from itertools import product
    target = ("o", "S", "T")
    for i,j in product(range(h), range(w)):
        if not a[i][j] in target:
            continue
        for k in range(h):
            if a[i][j] in target and a[k][j] in target:
                add(i,j,k,j)
                add(k,j,i,j)
        for k in range(w):
            if a[i][j] in target and a[i][k] in target:
                add(i,j,i,k)
                add(i,k,i,j)
    m = scipy.sparse.csr_matrix((data, (rs, cs)), shape=(2*h*w, 2*h*w))
    val = scipy.sparse.csgraph.maximum_flow(m, start, goal).flow_value # startからの最短路木を求める
print(val)

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


h,w = list(map(int, input().split()))
data= []
rs = []
cs = []
for i in range(h):
    c = input()
    if "S" in c:
        start = (i, c.index("S"))
    if "T" in c:
        goal = (i, c.index("T"))
    for j in range(w):
        if c[j] in ("o"):#, "S", "T"):
            data.append(1)
            rs.append(i)
            cs.append(h+j)
            data.append(1)
            rs.append(h+j)
            cs.append(i)
s = h+w
t = h+w+1
V = 10**9
data.append(V)
rs.append(s)
cs.append(start[0])
data.append(V)
rs.append(start[0])
cs.append(s)

data.append(V)
rs.append(s)
cs.append(start[1]+h)
data.append(V)
rs.append(start[1]+h)
cs.append(s)

data.append(V)
rs.append(goal[0])
cs.append(t)
data.append(V)
rs.append(t)
cs.append(goal[0])

data.append(V)
rs.append(t)
cs.append(goal[1]+h)
data.append(V)
rs.append(goal[1]+h)
cs.append(t)

import scipy.sparse
m = scipy.sparse.csr_matrix((data, (rs, cs)), shape=(h+w+2,h+w+2))
val = scipy.sparse.csgraph.maximum_flow(m, s, t).flow_value
if val>=10**9:
    val = -1
print(val)
### BUGGY CODE ###

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

k = 0
while len(S) > 1:
    ss = S[0]
    n = S.count(ss)
    k += n*(n-1)//2
    S = S[n:]

print(k)


### FIXED CODE ###

N = int(input())
k = 0
h = {}
for i in range(N):
    s = input()
    ss = "".join(sorted(s))
    if ss in h:
        k += h[ss]
    else:
        h[ss] = 0
    h[ss] += 1

print(k)
### BUGGY CODE ###

def insertionSort(A,n,g):
    for i in range(g,n):
        v = A[i]
        j = i-g
        while j>= 0 and A[j] > v:
            A[j+g] = A[j]
            j = j-g
        A[j+g] = v

def shellSort(A,n):
    G=[]
    h = 1
    while h<=n:
        G.append(h)
        h += h*3
    m = len(G)
    G.reverse()
    for i in range(m):
        insertionSort(A,n,G[i])


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

R = []

for i in range(n):
    R.append(int(input()))

shellSort(R,n)

minv = 2000000000

for j in range(n-k+1):
    minv = min(minv,R[j+k-1]-R[j])

print(minv)


### FIXED CODE ###

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

R = []

for i in range(n):
    R.append(int(input()))

R = sorted(R)
minv = 2000000000

for j in range(n-k+1):
    minv = min(minv,R[j+k-1]-R[j])

print(minv)
### BUGGY CODE ###

N,M=map(int,input().split())
A=[]
for i in range(N):
    A1=[i for i in map(int,input().split())]
    if i==0:
        A+=[A1]
    else:
        for j in range(len(A)):
            if A[j][0]>A1[0]:
                A.insert(j,A1)
                break
            elif j==i-1:
                A+=[A1]

count=0
price=0
for i in range(N):
    if A[0][1]>=M-count:
        price+=A[0][0]*(M-count)
        break
    else:
        price+=A[0][0]*A[0][1]
        count+=A[0][1]
    A.pop(0)
    
print(price)

### FIXED CODE ###

import numpy as np
N,M=map(int,input().split())
A=[]
 
for i in range(N):
    A+=[[i for i in map(int,input().split())]]
A=np.array(A)
A=A[A[:,0].argsort(),:]

count=0
price=0
for i in range(N):
    if A[i,1]>=M-count:
        price+=A[i,0]*(M-count)
        break
    else:
        price+=A[i,0]*A[i,1]
        count+=A[i,1]

print(price)
### BUGGY CODE ###

N = int(input())
P = list(map(float,input().split()))
dp = [[0] * (N+2) for _ in range(N+1)]
dp[0][0] = 1


for omote in range(N+1):
    for i in range(N):
        dp[i+1][omote] += dp[i][omote] * (1 - P[i])
        dp[i+1][omote+1] += dp[i][omote] * P[i] 

ans = 0
for omote in range(N+1):
    ans += dp[N][omote] if omote > N - omote else 0
print(ans)

### FIXED CODE ###

N = int(input())
P = list(map(float,input().split()))
dp = [[0] * (N+2) for _ in range(N+1)]
dp[0][0] = 1


for omote in range(N+1):
    for i in range(N):
        dp[i+1][omote] += dp[i][omote] * (1 - P[i])
        dp[i+1][omote+1] += dp[i][omote] * P[i] 

ans = 0
for omote in range(N+1):
    ans += dp[N][omote] if omote > N - omote else 0
print(ans)
### BUGGY CODE ###

k=int(input())
flag=1
ans=1
r=7%k
p=r
if k%2==0:
    print(-1)
    exit()
while flag!=0:
    if r%k==0:
        flag=0
    else:
        ans+=1
        p=(p*10)%k
        r+=p
print(ans)


### FIXED CODE ###

k=int(input())
flag=1
ans=1
r=7%k
p=r
if k%2==0:
    print(-1)
    exit()
if k%5==0:
    print(-1)
    exit()
while flag!=0:
    if r%k==0:
        flag=0
    else:
        ans+=1
        p=(p*10)%k
        r+=p
print(ans)
### BUGGY CODE ###

import numpy as np


def is_input(node, path):
    for i in range(len(path)):
        if path[i][node]:
            return True
    return False


def topological_sort(path):
    S = []
    for i, input_nodes in enumerate(input_nodes_list):
        if len(input_nodes_list) == 0:
            S.append(i)
    path = path.copy()
    for i in range(len(path)):
        flag = True
        for j in range(len(path)):
            if path[j][i]:
                flag = False
                input_nodes_list[i].append(j)
        if flag:
            S.append(i)
    res = []
    while len(S) > 0:
        now = S.pop()
        res.append(now)
        for i, f in enumerate(path[now]):
            if f:
                path[now][i] = False
                if not is_input(i, path):
                    S.append(i)
    return res


N, M = map(int, input().split(" "))
path = np.array([[False for i in range(N)] for i in range(N)])
input_nodes_list = [[] for i in range(N)]

for i in range(N+M-1):
    a, b = map(int, input().split(" "))
    path[a-1][b-1] = True
    input_nodes_list[b-1].append(a-1)

sorted_nodes = topological_sort(path)
dict_sorted_nodes = {}
for i, v in enumerate(sorted_nodes):
    dict_sorted_nodes[v] = i


for input_nodes in input_nodes_list:
    if len(input_nodes) == 0:
        print(0)
        continue
    if len(input_nodes) == 1:
        print(input_nodes[0]+1)
        continue
    temp_i = 0
    for j in input_nodes:
        temp_i = max(temp_i, dict_sorted_nodes[j])

    print(sorted_nodes[temp_i]+1)



### FIXED CODE ###

from collections import deque
from operator import itemgetter


def topolo():
    q = deque(v1 for v1 in range(N) if ins[v1] == 0)
    res = []
    popleft, append = q.popleft, q.append
    res_append = res.append
    while q:
        v1 = popleft()
        res_append(v1)
        for v2 in edges[v1]:
            ins[v2] -= 1
            if ins[v2] == 0:
                append(v2)
    return res


N, M = map(int, input().split(" "))
edges = [[] for _ in [0]*N]
rev = [[] for _ in [0]*N]

ins = [0]*N

for a, b in (map(int, input().split(" ")) for _ in [0]*(N+M-1)):
    edges[a-1].append(b-1)
    rev[b-1].append(a-1)
    ins[b-1] += 1

sorted_nodes = topolo()
order = [i for i, v in sorted(enumerate(sorted_nodes), key=itemgetter(1))]

for input_nodes in rev:
    l = len(input_nodes)
    if l == 0:
        print(0)
        continue
    elif l == 1:
        print(input_nodes[0] + 1)
        continue
    temp = 0
    for node in input_nodes:
        temp = max(temp, order[node])
    print(sorted_nodes[temp] + 1)