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

n=int(input())
a=list(map(int,input().split()))
cnt=0
a.sort()
a.reverse()
for i in range(n):
    for j in range(a.index(a[i]),n):
        if(i==j):
            continue
        if(a[i]%a[j]==0):
            cnt=cnt+1
            break
print(n-cnt)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
set(a)
ans=[0]*1000005
x=1
for i in a:
    if(ans[i]!=0):
        ans[i]=2
        continue
    for j in range(i,1000005,i):
        ans[j]=ans[j]+1
cnt=0
for i in range(0,n):
    if(ans[a[i]]==1):
        cnt=cnt+1
print(cnt)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
n = int(input())

D = dict()
def dfs(a, b, c, d):
  if a == n:
    return 0
  if (a, b, c, d) in D:
    return D[(a, b, c, d)]
  rep = n
  if b != 0:
    rep += b * dfs(a+1, b-1, c, d)
  if c != 0:
    rep += c * dfs(a, b+1, c-1, d)
  if d != 0:
    rep += d * dfs(a, b, c+1, d-1)
  rep /= (n-a)
  D[(a, b, c, d)] = rep
  return rep

L = [0]*4
for a in map(int, input().split()):
  L[a] += 1
ans = dfs(*L)
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n = int(input())
A = tuple(map(int, input().split()))
C = [0]*3
for a in A:
  C[a-1] += 1
dp = [[[-1]*(n+1) for i in range(n+1)] for j in range(n+1)]
dp[0][0][0] = 0
def f(i, j, k):
  if dp[i][j][k] != -1:
    return dp[i][j][k]
  res = 1
  if i:
    res += f(i-1, j, k)*(i/n)
  if j:
    res += f(i+1, j-1, k)*(j/n)
  if k:
    res += f(i, j+1, k-1)*(k/n)
  res /= (i+j+k)/n
  dp[i][j][k] = res
  return res
ans = f(C[0], C[1], C[2])
print(ans)
### BUGGY CODE ###

n=int(input())
a=[int(input()) for i in range(n)]
for i in range(n):
    m=0
    for j in range(n):
        if j!=i and a[j]>=m:
            m=a[j]
    print(m)


### FIXED CODE ###

n=int(input())
a=[int(input()) for i in range(n)]
l=sorted(a)
m=l[-1]
n=l[-2]
for i,value in enumerate(a):
    if value!=m:
        print(m)
    else:
        print(n)
### BUGGY CODE ###

S=input()
dp=[[0]*13 for i in range(len(S)+1)]
dp[0][0]=1
mod=10**9+7
for i in range(len(S)):
  if(S[i]=='?'):
    for j in range(13):
      for k in range(10):
        dp[i+1][(j*10+k)%13]=(dp[i+1][(j*10+k)%13]+dp[i][j])%mod
  else:
    k=int(S[i])
    for j in range(13):
      dp[i+1][(j*10+k)%13]=(dp[i+1][(j*10+k)%13]+dp[i][j])%mod
print(dp[len(S)][5])

### FIXED CODE ###

S=input()
dp=[[0]*13 for i in range(len(S)+1)]
dp[0][0]=1
mod=10**9+7
for i in range(len(S)):
  if(S[i]=='?'):
    for j in range(13):
      for k in range(10):
        l=(j*10+k)%13
        dp[i+1][l]+=dp[i][j]
    for j in range(13):
      dp[i+1][j]%=mod
  else:
    k=int(S[i])
    for j in range(13):
      l=(j*10+k)%13
      dp[i+1][l]+=dp[i][j]
    for j in range(13):
      dp[i+1][j]%=mod
print(dp[len(S)][5])
### BUGGY CODE ###

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

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

for i in range(M):
    B, C = list(map(int,input().split()))
    A += [C]*B

A.sort()

print(sum(A[len(A)-N:]))

### FIXED CODE ###

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

A = [-1]
A += list(map(int,input().split()))
A.sort()

BC = [[1,-1]]

for i in range(M):
    BC.append(list(map(int,input().split())))

BC = sorted(BC, key=lambda x: x[1])


x = 0

for i in range(N):
    if A[-1] > BC[-1][1]:
        x += A.pop()
        
    else:
        x += BC[-1][1]
        BC[-1][0] -= 1
        if BC[-1][0] == 0:
            BC.pop()

print(x)
### BUGGY CODE ###

def repeatableKnapsack(n, W, weights, values):
    dp = [0 for _ in range(W+1)]
    dp[0] = 0
    # print(weights, values)
    for i in range(1,W+1):
        for j in range(n):
            if weights[j] <= i:
                dp[i] = max(dp[i], values[j]+dp[i-weights[j]])
    # print(dp)
    print(dp[-1])
    
def knapsack01(n, W, weights, values, dp, i, j):
    # i = up until item i, j = up until weight j
    if i == 0 or j <= 0:
        return 0
    
    # start with first item
    if dp[i-1][j] == -1:
        dp[i-1][j] = knapsack01(n, W, weights, values, dp, i-1, j)
    
    if weights[i-1] > j:
        # weights[i] doesn't fit in knapsack
        dp[i][j] = dp[i-1][j]
    else:
        if dp[i-1][j-weights[i-1]] == -1:
            dp[i-1][j-weights[i-1]] = knapsack01(n, W, weights, values, dp, i-1, j-weights[i-1])
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1])
        
    return dp[i][j]
    
n,W = [int(x) for x in input().split()]
weights = []
values = []
for i in range(n):
    l = [int(x) for x in input().split()]
    weights += [l[0]]
    values += [l[1]]

# repeatableKnapsack(n, W, weights, values)

dp = [[-1 for _ in range(W+1)] for _ in range(n+1)]
res = knapsack01(n, W, weights, values, dp, n, W)
# print(dp)
print(res)

### FIXED CODE ###


def knapsack01iter(n, W, weights, values, dp):
    for i in range(1,n+1):
        for j in range(0, W+1):
            if j < weights[i-1]: # if knapsack cannot fit item i
                dp[i][j] = dp[i-1][j]
            elif j >= weights[i-1]: # knapsack can fit item i
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]]+values[i-1])
    
    return dp[-1][-1]
    
    
n,W = [int(x) for x in input().split()]
weights = []
values = []
for i in range(n):
    l = [int(x) for x in input().split()]
    weights += [l[0]]
    values += [l[1]]

# repeatableKnapsack(n, W, weights, values)

# dp = [[-1 for _ in range(W+1)] for _ in range(n+1)]
# res = knapsack01rec(n, W, weights, values, dp, n, W)
# print(dp)
dp = [[0 for _ in range(W+1)] for _ in range(n+1)]
res = knapsack01iter(n, W, weights, values, dp)
# print(dp)
print(res)
### BUGGY CODE ###

N = int(input())
list = []
list.append(str(input()))

for i in range(N-1):
  s = str(input())
  for j in range(len(list)):
    if list[j]==s: break
    elif j==len(list)-1 : list.append(s)

print(len(list))

### FIXED CODE ###

N = int(input())
List = [str(input()) for i in range(N)] 
print(len(list(set(List))))
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n,a=map(int,input().split())
x=[0]+list(map(int,input().split()))
dp=[[[0 for k in range(2501)] for j in range(51)] for i in range(51)]
dp[0][0][0]=1
for i in range(1,n+1):
    for j in range(i+1):
        for k in range(n*a+1):
            if k<x[i]:
                dp[i][j][k]=dp[i-1][j][k]
            if k>=x[i] and j>=1:
                dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-x[i]]
ans=0
for t in range(1,n+1):
    ans+=dp[n][t][a*t]
print(ans)


### FIXED CODE ###

import sys
input=sys.stdin.readline
n,a=map(int,input().split())
x=[0]+list(map(int,input().split()))
su=sum(x)
maxi=max(x)
dp=[[[0 for k in range(maxi*n+1)] for j in range(51)] for i in range(51)]
dp[0][0][0]=1
for i in range(1,n+1):
    for j in range(i+1):
        for k in range(maxi*j+1):
            if k<x[i]:
                dp[i][j][k]=dp[i-1][j][k]
            if k>=x[i] and j>=1:
                dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-x[i]]
ans=0
for t in range(1,n+1):
    if a*t<=su:
        ans+=dp[n][t][a*t]
    else:
        break
print(ans)
### BUGGY CODE ###

import sys


def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    solo_invs = [0] + [f * i % MOD for f, i in zip(factorials, invs[1:])]

    return factorials, invs, solo_invs


def decompose_inverses(solo_invs, MOD):
    # 各整数 g に対して、g の約数である各 i について dcm[i] を全て足すと 1/g になるような数列を作成
    n = len(solo_invs)
    dcm = solo_invs[:]
    for i in range(1, n):
        d = dcm[i]
        for j in range(2 * i, n, i):
            dcm[j] -= d
    for i in range(1, n):
        dcm[i] %= MOD
    return dcm


n, *aaa = map(int, sys.stdin.buffer.read().split())
MOD = 998244353
LIMIT = max(aaa)
count = [0] * (LIMIT + 1)
double = [0] * (LIMIT + 1)
for a in aaa:
    count[a] += a
    double[a] += a * a
_, _, solo_invs = prepare(LIMIT, MOD)
dcm = decompose_inverses(solo_invs, MOD)

ans = 0
inv2 = solo_invs[2]
for d in range(1, LIMIT + 1):
    mulsum = sum(count[d::d]) ** 2 - sum(double[d::d]) % MOD
    if mulsum:
        ans = (ans + dcm[d] * mulsum * inv2) % MOD
print(ans)


### FIXED CODE ###

import sys


def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    solo_invs = [0] + [f * i % MOD for f, i in zip(factorials, invs[1:])]

    return factorials, invs, solo_invs


def decompose_inverses(solo_invs, MOD):
    # 各整数 g に対して、g の約数である各 i について dcm[i] を全て足すと 1/g になるような数列を作成
    n = len(solo_invs)
    dcm = solo_invs[:]
    for i in range(1, n):
        d = dcm[i]
        for j in range(2 * i, n, i):
            dcm[j] -= d
    for i in range(1, n):
        dcm[i] %= MOD
    return dcm


n, *aaa = map(int, sys.stdin.buffer.read().split())
MOD = 998244353
LIMIT = max(aaa)
count = [0] * (LIMIT + 1)
double = [0] * (LIMIT + 1)
for a in aaa:
    count[a] += a
    double[a] += a * a
_, _, solo_invs = prepare(LIMIT, MOD)
dcm = decompose_inverses(solo_invs, MOD)

ans = 0
inv2 = solo_invs[2]
for d in range(1, LIMIT + 1):
    ans = (ans + dcm[d] * (sum(count[d::d]) ** 2 - sum(double[d::d])) * inv2) % MOD
print(ans)
### BUGGY CODE ###


import sys
sys.setrecursionlimit(10 ** 7)
inp = sys.stdin.buffer.readline


def resolve():
    MOD = 10 ** 9 + 7

    # 0: white, 1: black
    def dfs(v, parent):
        vistied[v] = True
        dp[v][0] = 1
        dp[v][1] = 1
        for to in G[v]:
            if to == parent or vistied[to]:
                continue
            dfs(to, v)
            # 親が白の時は子は白黒どっちでも良い
            # 親が黒の時は子は白のみ
            dp[v][0] *= (dp[to][0] + dp[to][1]) % MOD
            dp[v][1] *= dp[to][0] % MOD

    N = int(inp())
    G = [[] for _ in range(N)]
    for _ in range(N - 1):
        x, y = map(lambda x: int(x) - 1, inp().split())
        G[x].append(y)
        G[y].append(x)
    dp = [[0] * 2 for _ in range(N)]
    vistied = [False] * N

    dfs(0, -1)
    ans = dp[0][0] + dp[0][1]
    print(ans % MOD)


if __name__ == "__main__":
    resolve()

### FIXED CODE ###


import sys
sys.setrecursionlimit(10 ** 7)
inp = sys.stdin.buffer.readline


def resolve():
    MOD = 10 ** 9 + 7

    # 0: white, 1: black
    def dfs(v, parent):
        vistied[v] = True
        dp[v][0] = 1
        dp[v][1] = 1
        for to in G[v]:
            if to == parent or vistied[to]:
                continue
            dfs(to, v)
            # 親が白の時は子は白黒どっちでも良い
            # 親が黒の時は子は白のみ
            dp[v][0] *= (dp[to][0] + dp[to][1]) % MOD
            dp[v][1] *= dp[to][0] % MOD

    N = int(inp())
    G = [[] for _ in range(N)]
    for _ in range(N - 1):
        x, y = map(lambda x: int(x) - 1, inp().split())
        G[x].append(y)
        G[y].append(x)
    dp = [[0] * 2 for _ in range(N)]
    vistied = [False] * N

    dfs(0, -1)
    ans = dp[0][0] + dp[0][1]
    print(ans % MOD)


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

n, m, r = map(int, input().split())  # n:頂点数　w:辺の数
r_list = list(map(int, input().split()))
graph = [[float('inf')]*n for i in range(n)]
for _ in range(m):
    u, v, w = map(int, input().split())
    graph[u-1][v-1] = w
    graph[v-1][u-1] = w
for i in range(n):
    graph[i][i] = 0

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


from itertools import permutations

adj_m=warshall_floyd(graph)
ans=float('inf')
for path in permutations(r_list):
    tmp_dist=0
    for i in range(r-1):
        tmp_dist+=adj_m[path[i]-1][path[i+1]-1]
    ans=min(ans, tmp_dist)
print(ans)


### FIXED CODE ###

n, m, r = map(int, input().split())  # n:頂点数　w:辺の数
r_list = list(map(int, input().split()))
graph = [[float('inf')]*n for i in range(n)]
for _ in range(m):
    u, v, w = map(int, input().split())
    graph[u-1][v-1] = w
    graph[v-1][u-1] = w
for i in range(n):
    graph[i][i] = 0

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


from itertools import permutations

adj_m=warshall_floyd(graph)
ans=float('inf')
for path in permutations(r_list):
    tmp_dist=0
    for i in range(r-1):
        tmp_dist+=adj_m[path[i]-1][path[i+1]-1]
    ans=min(ans, tmp_dist)
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))  # O(N)
p = len(format(max(A), 'b')) # O(N)
digit = ['0' + str(p) + 'b'] * N
S = list(map(format, A, digit))  # O(N)

r = [0] * p
for s in S:
  for j in range(p):
    r[j] += int(s[j])

ans = 0
for j in range(p):
  ans += r[-(j+1)] * (N - r[-(j+1)]) * (2 ** j)

print(ans % 1000000007)

### FIXED CODE ###

import numpy as np 
N = int(input())
A = np.fromstring(input(), dtype = np.int64, sep = ' ')

res = 0
for bit in range(60):
  c = int((A & 1).sum())
  res += c * (N - c) * (1 << bit)
  A >>= 1

print(res % 1000000007)
### BUGGY CODE ###

#!/usr/bin/env python

import sys

n= int(sys.stdin.readline())
ai= [ int(sys.stdin.readline()) for _ in range(n) ]
m= [ False ] * n
c= 0
for i in range(n):
    if m[i]: continue
    m[i]= True
    c+= 1
    j= i
    for k in range(j+1,n):
        if m[k]: continue
        if ai[j]<ai[k]:
            m[k]= True
            j= k
#
print( c )


### FIXED CODE ###

#!/usr/bin/env python

import sys

def DBsearch(L,x,narrow):
    n= len(L)
    if n==0: return 0
    if narrow and x in L: return L.index(x)
    last = L[-1]
    if x<last: return n
    if not narrow and x==last: return n
    #
    idx= -1
    i= 0
    j= n-1
    while j>=i:
        if i==j:
            if x>L[i]: idx= i
            break
        #
        mid= i + (j-i)//2
        if x<L[mid]:
            i= mid+1
        elif x==L[mid]:
            if narrow:
                idx= mid
                j  = mid - 1
            else:
                i = mid + 1
        else:
            idx= mid
            j= mid-1
    #
    return idx
#
def lds(L,narrow):
    seq= []
    for x in L:
        if len(seq)==0 or x<seq[-1]:
            seq.append(x)
        elif x==seq[-1]:
            if narrow:
                seq[DBsearch(seq,x,narrow)]= x
            else:
                seq.append(x)
        else:
            seq[DBsearch(seq,x,narrow)]= x
    #
    return len(seq)
#
n= int(sys.stdin.readline())
ai= [ int(sys.stdin.readline()) for _ in range(n) ]
print( lds( ai,False ) )
### BUGGY CODE ###

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

b=[]
for item in a:
    b.append(item)
    b.reverse()


for item in b:
    print(item, end=" ")


### FIXED CODE ###

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

b1=[]
b2=[]
b=[]
for i in range(0, n-1, 2):
    b1.append(a[i])
    b2.append(a[i+1])

if n%2 == 1:
    b1.append(a[n-1])
    b1.reverse()
    b.extend(b1)
    b.extend(b2)
else:
    b2.reverse()
    b.extend(b2)
    b.extend(b1)

for item in b:
    print(item, end=" ")
### BUGGY CODE ###

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

li = [[] for j in range(10**5+1)]

for _ in range(n):
  a, b = map(int, input().split())
  li[a].append(b)

ans = 0
jobs = []
for i in range(1, m+1):
  jobs.extend(li[i])
  if jobs == []:
    continue
  jobs.sort(reverse = True)
  ans += jobs.pop(0)
print(ans)

### FIXED CODE ###

def insertHeap(array, val):
    array.append(val)
    n = len(array)-1
    while n != 0:
        parent = int((n - 1) / 2)
        if array[n] > array[parent]:
            tmp = array[n]
            array[n] = array[parent]
            array[parent] = tmp
            n = parent
        else:
            break
    return array

def desertHeap(array):
    if array == []:
      return None
    array[0], array[-1] = array[-1], array[0]
    res = array.pop(-1)
    n = len(array)
    if n == 0 or n == 1: 
      return res
    parent = 0
    while True:
        child = 2 * parent + 1
        if child >= n: break
        if (child + 1 < n) and array[child] < array[child + 1]:
            child += 1
        if array[parent] < array[child]:
            array[child], array[parent] = array[parent], array[child]
            parent = child;
        else:
            break
    return res

n, m = map(int, input().split())
 
li = [[] for j in range(10**5+1)]
 
for _ in range(n):
  a, b = map(int, input().split())
  li[a].append(b)
 
ans = 0
jobsHeap = []
for i in range(1, m+1):
  for val in li[i]:
    jobsHeap = insertHeap(jobsHeap, val)
  
  if jobsHeap != []:
    res = desertHeap(jobsHeap)
    ans += res
print(ans)
### BUGGY CODE ###

import itertools

line=input()
n,k=map(int,line.split())
s=set(list(range(n+1)))
sums=list()
while k!=(n+2):
     koko=list()
     sub=list(itertools.combinations(s,k))
     #print(sub)
     for val in sub:
          soso=0
          for i in val:
               soso=(soso%((10**9)+7))+((i+(10**100))%((10**9)+7))
               #soso=(soso%((10**9)+7))
          if soso not in sums:
               sums.append(soso)
               #soso=(soso%((10**9)+7))
          
               
          
     
     
     
     k+=1
#jojo=(%((10**9)+7))
print((len(sums)))


### FIXED CODE ###

line=input()
n,k=map(int,line.split())
sums=0
while k!=(n+2):
     if k==1:
          mini=0
     if k>=2:
          mini=(((k)*(k-1))/2)#%((10**9)+7)
     maxi=( (((n+1)*(n)) - ((n+1-k)*(n-k)) )/2  )#%((10**9)+7)
     sums+=(maxi-mini+1)
     sums=sums%((10**9)+7)
     k+=1
print(int(sums))
### BUGGY CODE ###

A,B,K=input().split()
A=int(A)
B=int(B)
K=int(K)
count=0

while count < K:
    if A > 0:
        A = A - 1
    else:
        if B > 0:
            B = B - 1
        else:
            pass
    count=count+1

print(A,B)


### FIXED CODE ###

A,B,K=input().split()
A=int(A)
B=int(B)
K=int(K)

if A+B<=K:
    print(0,0)
elif A<K and A+B>K:
    B=B-(K-A)
    print(0,B)
elif A>=K:
    print(A-K,B)
### BUGGY CODE ###

h,w = map(int,input().split())
a = list(list(input())for i in range(h))
stack = []
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            stack.append((i,j))
            a[i][j] == -1
vec = ((1,0),(0,1),(-1,0),(0,-1))
move = 0
while stack:
    next = []
    move +=1
    for y,x in stack:
        for ny,nx in vec:
            ty,tx = y+ny,x+nx
            if ty>h-1 or tx>w-1 or ty<0 or tx <0:continue
            if a[ty][tx] == ".":
                a[ty][tx] = move
                next.append((ty,tx))
    stack = next

print(move-1)


### FIXED CODE ###

h,w = map(int,input().split())
a = list(list(input())for i in range(h))
stack = []
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            stack.append((i,j))
        
vec = ((1,0),(0,1),(-1,0),(0,-1))
move = 0
while stack:
    next = []
    move +=1
    for y,x in stack:
        for ny,nx in vec:
            ty,tx = y+ny,x+nx
            if ty>h-1 or tx>w-1 or ty<0 or tx <0:continue
            if a[ty][tx] == ".":
                a[ty][tx] = move
                next.append((ty,tx))
    stack = next

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

n = int(input())
a = sorted(list(map(int, input().split())), reverse=True)

#aの要素の最大公約数を求める
while len(a) != 1:
    j = a[0]
    k = a[1]
    p = 1 # 0以外である必要がある
    while p != 0:
        p = j % k
        if p != 0:
            j, k = k, p
    del a[:2]
    a.insert(0, k)
print(a[0])

### FIXED CODE ###

import fractions
from functools import reduce

n = int(input())
a = sorted(list(map(int, input().split())), reverse=True)
print(reduce(fractions.gcd, a))
### BUGGY CODE ###

# C - gacha
from bisect import *
N = int(input())
ans = []
for _ in range(N):
    S = input()
    i = bisect_left(ans,S)
    if i>=len(ans) or ans[i]!=S:
        ans.insert(i,S)
print(len(ans))

### FIXED CODE ###

# C - gacha
N = int(input())
ans = set()
for _ in range(N):
    S = input()
    ans.add(S)
print(len(ans))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

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

lang = [[] for _ in range(M)]
for i in range(N) :
    for j in KL[i][1:] :
        lang[j-1].append(i)
        
visited = [False] * N
visited[0] = True
q = [0]
while q :
    cur = q.pop()
    for l in KL[cur][1:] :
        for m in lang[l-1] :
            if not visited[m] :
                q.append(m)
                visited[m] = True
                
if sum(visited) == N :
    print('YES')
else :
    print('NO')

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

N, M = map(int, input().split())
v = [[] for _ in range(N+M)]
for i in range(N) :
    K, *L = map(int, input().split())
    for l in L :
        v[N+l-1].append(i)
        v[i].append(N+l-1)

visited = [False] * (N + M)
visited[0] = True
q = [0]

while q :
    cur = q.pop()
    for nex in v[cur] :
        if not visited[nex] :
            q.append(nex)
            visited[nex] = True

if sum(visited[:N]) == N :
    print('YES')
else :
    print('NO')
### BUGGY CODE ###

S = input()
g = 10 ** 9 + 7
x = 1
DP = [[0] * 13 for _ in range(2)]
DP[0][0] = 1
for i in range(len(S)):
    for j in range(13):
        DP[1][j] = DP[0][j] % g
        DP[0][j] = 0
    for j in range(13):
        if S[i] == "?":
            s = (j*10)%13
            e = (s+10)%13
        else:
            s = (j*10+int(S[i]))%13
            e = (s+1)%13
        DP[0][s] += DP[1][j]
        if s > e:
            DP[0][0] += DP[1][j]
        DP[0][e] -= DP[1][j]
    w = 0
    for j in range(13):
        w += DP[0][j]
        DP[0][j] = w

print(DP[0][5] % g)


### FIXED CODE ###

S = input()
g = 10 ** 9 + 7
x = 1
DP = [[0] * 13 for _ in range(2)]
DP[0][0] = 1
for i in range(len(S)):
    for j in range(13):
        DP[1][j] = DP[0][j] % g
        DP[0][j] = 0
    for j in range(13):
        if S[i] == "?":
            for k in range(10):
               DP[0][(j*10+k)%13] += DP[1][j]
        else:
            DP[0][(j*10+int(S[i]))%13] += DP[1][j]

print(DP[0][5] % g)
### BUGGY CODE ###

import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())
edges = [[] for i in range(n)]
edges_r = [[] for i in range(n)]
for i in range(n+m-1):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges_r[b].append(a)
s = 0
for i,e in enumerate(edges_r):
    if len(e) == 0:
        s = i
        break

INF = 1 << 60
ks = [-1] * n
parents = [-1] * n
q = deque([s])
ks[s] = 0
# 同じ深さのもの同士をつなぐのはありえないので
# 根の部分から徐々に掘り下げながら、真の親を探す
while len(q) > 0:
    u = q.popleft()
    for v in edges[u]:
        if ks[u] >= ks[v]:
            ks[v] = ks[u] + 1
            parents[v] = u
            q.appendleft(v)

for p in parents:
    print(p+1)

### FIXED CODE ###

"""
子孫に向かって有向辺が伸びる
⇨ ループなし
⇨ トポロジカルソート通りに並べると親がわかる
"""
from collections import deque
from collections import defaultdict
n, m = map(int, input().split())

edges = [[] for _ in range(n)]
ps = [[] for _ in range(n)]
for i in range(n+m-1):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    ps[b].append(a)

def topo(G):
    cut_in = defaultdict(int)
    for vs in G:
        for v in vs:
            cut_in[v] += 1
    res = []
    # 入次数が0のものを洗い出し
    zeros = [i for i in range(n) if cut_in[i] == 0]
    q = deque(zeros)
    # すべての入次数が0になるまでくりかえす
    while len(q) > 0:
        v = q.popleft()
        res.append(v)
        for u in G[v]:
            cut_in[u] -= 1
            if cut_in[u] == 0:
                q.append(u)
    return res

ss = topo(edges)
# print(ss,ps)
ss = {s:i for i,s in enumerate(ss)}

for i in range(n):
    mn = -1
    parent = 0
    if len(ps[i]) == 0:
        print(0)
        continue
    for p in ps[i]:
        if mn < ss[p]:
            mn = ss[p]   
            parent = p
    print(parent+1)