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

N,K,L = map(int, input().split())

#print(N,K,L,D,T)

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

def execOne(num, uf):
    for _ in range(num):
        d0, d1 = map(int, input().split())
        d0 = d0 - 1
        d1 = d1 - 1
        uf.union(d0, d1)

uf_D = UnionFind(N)
uf_T = UnionFind(N)

execOne(K, uf_D)
execOne(L, uf_T)

res = [0] * N
for i in range(N):
    for j in range(N):
        if (uf_D.same_check(i,j) and uf_T.same_check(i,j)):
            res[i] += 1
#print(*(res[i] for i in range(N)))
print(" ".join([str(i) for i in res]))

### FIXED CODE ###

import sys
 
sys.setrecursionlimit(10000)

N,K,L = map(int, input().split())

#print(N,K,L,D,T)

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

def execOne(num, uf):
    for _ in range(num):
        d0, d1 = map(int, input().split())
        d0 = d0 - 1
        d1 = d1 - 1
        uf.union(d0, d1)

uf_D = UnionFind(N)
uf_T = UnionFind(N)

execOne(K, uf_D)
execOne(L, uf_T)


pairs = []
for i in range(N):
    pairs.append((uf_D.find(i), uf_T.find(i)))

pairs_count = {}
for p in pairs:
    if not p in pairs_count:
        pairs_count[p] = 1
    else:
        pairs_count[p] += 1

res = [0] * N
for i in range(N):
    res[i] = pairs_count[pairs[i]]
#print(*(res[i] for i in range(N)))
print(" ".join([str(i) for i in res]))
### BUGGY CODE ###

n = int(input())
A = [0]*n
for i in range(n):
    A[i] = int(input())
paper = []
for a in A:
    if a in paper:
        paper.remove(a)
    else:
        paper.append(a)
print(len(paper))

### FIXED CODE ###

n = int(input())
A = [0]*n
for i in range(n):
    A[i] = int(input())
paper = set()
for a in A:
    if a in paper:
        paper.remove(a)
    else:
        paper.add(a)
print(len(paper))
### BUGGY CODE ###

from collections import deque
N,M=list(map(int,input().split()))
even_list=[list(map(int,input().split())) for _ in range(M)]
#リストVのN番目には頂点Nがあり、そこには頂点Nとつながっている頂点が入っている。
    
#seen[i]は、頂点iを訪問済みの場合はTrue、未訪問の場合はFalse
seen=[False for i in range(N+1)]


count=0
graph=[[] for _ in range(N+1)]
for i in even_list:
    graph[i[0]].append(i[1])
    graph[i[1]].append(i[0])

def StackBFS(s):
    #graphのN番目には頂点Nがあり、そこには頂点Nとつながっている頂点が入っている。
    S=deque([s])
    C=set()
    
    while S:
        v=S.popleft()
        seen[v]=True #訪問済みの頂点をTrueにする
        if v not in C:
            C=C|{v}
            for i in graph[v]:
                S.append(i)

for i in range(1,N+1):
    if seen[i]==False:
        StackBFS(i)
        count+=1

print(count)

### FIXED CODE ###

from collections import deque


N,M=list(map(int,input().split()))
graph=[[] for _ in range(N+1)]
for _ in range(M):
    a,b,c=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
    
#seen[i]は、頂点iを訪問済みの場合はTrue、未訪問の場合はFalse
seen=[False]*(N+1)


count=0

for i in range(1,N+1):
    if seen[i]==False:
        seen[i]=True
        S=deque([i])
        
        while S:
            v=S.popleft()
            #訪問済みの頂点をTrueにする
            for i in graph[v]:
                if seen[i]==False:
                    seen[i]=True
                    S.append(i)
        count+=1

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

A,B,N=map(int,input().split())
X=B-1
ans=(A*N)//B-A*(N//B)
while X<=N:
  ans=max(ans,(A*X)//B-A*(X//B))
  X+=B
print(ans) 

### FIXED CODE ###

import sys
A,B,N=map(int,input().split())
X=B-1
ans=(A*N)//B-A*(N//B)
if B==1:
  print(0)
  sys.exit()
while X<=N:
  ans=max(ans,(A*X)//B-A*(X//B))
  X+=B
print(ans)
### BUGGY CODE ###

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

ans_list = []
for i in range(1, N + 1):
    ans_list.append(A_list.index(i) + 1)
    
print(' '.join([str(n) for n in ans_list]))


### FIXED CODE ###

N = int(input())
index_list = [int(i) - 1 for i in input().split()]
ans_list = [0] * N

num_list = [i + 1 for i in range(N)]
for i in range(N):
    ans_list[index_list[i]] = num_list[i]

print(*ans_list)
### BUGGY CODE ###


import sys

S =  sys.stdin.readline()[:-1]
l = len(S)
# S = S[::-1]
S = list(reversed(S))

dp =[[0 ] * 13 for _ in range(l + 1)]
kurai = 1
MOD = (10 ** 9) + 7
dp[0][0] = 1

for keta in range(len(S)):
    c =S[keta]

    if c == "?":
        for j in range(0,10):
            kurai %= 13
            temp = (j * kurai) % 13
            for i in range(13):
                dp[keta + 1][(temp + i) % 13] += (dp[keta][i] )
                dp[keta + 1][(temp + i) % 13] %= MOD
    else:
        kurai %= 13

        temp = (int(c) * kurai) % 13
        for i in range(13):
            dp[keta + 1][(temp + i) % 13]  += (dp[keta][i] )
            dp[keta + 1][(temp + i) % 13] %= MOD
    kurai *= 10
    keta %= MOD
print(dp[-1][5] )



### FIXED CODE ###


import sys

S =  sys.stdin.readline()[:-1]
l = len(S)
# S = S[::-1]
S = list(reversed(S))

dp =[[0 ] * 13 for _ in range(l + 1)]
kurai = 1
MOD = (10 ** 9) + 7
dp[0][0] = 1

for keta in range(len(S)):
    c =S[keta]

    if c == "?":
        for j in range(0,10):
            kurai %= 13
            temp = (j * kurai) % 13
            for i in range(13):
                dp[keta + 1][(temp + i) % 13] += (dp[keta][i] )
                dp[keta + 1][(temp + i) % 13] %= MOD
    else:
        kurai %= 13

        temp = (int(c) * kurai) % 13
        for i in range(13):
            dp[keta + 1][(temp + i) % 13]  += (dp[keta][i] )
            dp[keta + 1][(temp + i) % 13] %= MOD
    kurai *= 10
    keta %= MOD
print(dp[-1][5] )
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n=int(input())
ans=0
l=[]
for _ in range(10**6+1):
    x=n%10
    l.append(x)
    n=(n-x)//10
for i in range(10**6+1):
    if 0<=l[i]<=4:
        ans+=l[i]
    elif 6<=l[i]<=9:
        ans+=10-l[i]
        l[i+1]+=1
    elif l[i]==10:
        l[i+1]+=1
    elif l[i]==5:
        ans+=5
        if 0<=l[i+1]<=4:
            pass
        else:
            l[i+1]+=1
print(ans)








### FIXED CODE ###

import sys
input=sys.stdin.readline
ns=input().rstrip()
ans=0
l=[]
ls=len(ns)
for i in range(ls):
    l.append(int(ns[ls-1-i]))
for i in range(10**6+1-ls):
    l.append(0)
for i in range(10**6+1):
    if 0<=l[i]<=4:
        ans+=l[i]
    elif 6<=l[i]<=9:
        ans+=10-l[i]
        l[i+1]+=1
    elif l[i]==10:
        l[i+1]+=1
    elif l[i]==5:
        ans+=5
        if 0<=l[i+1]<=4:
            pass
        else:
            l[i+1]+=1
print(ans)
### BUGGY CODE ###

from collections import deque
S = deque(input())
Q = int(input())
for i in range(Q):
    Q_i = list(input().split())
    if Q_i[0] == "1":
        S.reverse()
    elif Q_i[1] == "1":
        S.appendleft(Q_i[2])
    else:
        S.append(Q_i[2])
print("".join(S))

### FIXED CODE ###

from collections import deque
S = deque(input())
Q = int(input())
reverse_count = 0
for i in range(Q):
    Q_i = list(input().split())
    if Q_i[0] == "1":
        reverse_count += 1
    elif ((Q_i[1] == "1" and reverse_count % 2 == 0) or
          (Q_i[1] == "2" and reverse_count % 2 == 1)):
        S.appendleft(Q_i[2])
    else:
        S.append(Q_i[2])
if reverse_count%2==1:
    S.reverse()
print("".join(S))
### BUGGY CODE ###

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

DPLIST=[float("inf")]*N
DPLIST[0]=0

for i in range(N-1):
    for j in range(1,K+1):
        if i+j<N:
            DPLIST[i+j]=min(DPLIST[i+j],DPLIST[i]+abs(H[i+j]-H[i]))

print(DPLIST[N-1])

### FIXED CODE ###

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

DPLIST=[float("inf")]*N
DPLIST[0]=0

for i in range(N-1):
    for j in range(1,K+1):
        if i+j<N:
            DPLIST[i+j]=min(DPLIST[i+j],DPLIST[i]+abs(H[i+j]-H[i]))

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

def lottery(a):
  return len(a)

n = int(input())
a = []
for i in range(n):
  item = input()
  if(item not in a):
    a.append(item)
print(lottery(a))


### FIXED CODE ###

n = int(input())
a = []
count = 0
for i in range(n):
  item = input()
  a.append(item)
print(len(list(set(a))))
### BUGGY CODE ###

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]

import heapq

d = dict()
key_all = []
for i in range(n):
    a = ab[i][0]
    b = ab[i][1]

    if a not in key_all:
        d[a] = [b]
        heapq.heappush(key_all, a)
    else:
        d[a].append(b)

ans = 0
l = []

for i in range(1, m+1):
    if key_all != []:
        if i == key_all[0]:
            for v in d[i]:
                heapq.heappush(l, -1 * v)

            heapq.heappop(key_all)

    if l != []:
        ans += heapq.heappop(l) * -1

print(ans)


### FIXED CODE ###

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]

import heapq
import collections

a_all = []
for i in range(n):
    a_all.append(ab[i][0])

key_all = list(set(a_all))
key_all.sort()

d = dict()
for k in key_all:
    d[k] = []

for i in range(n):
    a = ab[i][0]
    b = ab[i][1]
    d[a].append(b)

ans = 0
l = []
for i in range(1, m+1):
    if key_all != []:
        if i == key_all[0]:
            for v in d[i]:
                heapq.heappush(l, -1 * v)

            heapq.heappop(key_all)

    if l != []:
        ans += heapq.heappop(l) * -1

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

_N=input()
A=list(map(int,input().split()))
B=[i for i in range(1,len(A)+1)]
reverse_ans=[]
while len(A)!=0:
  max_a,max_i=0,0
  for i in range(0,len(A)):
    if max_a < A[i]:
      max_a = A[i]
      max_i = i
  A.pop(max_i)
  reverse_ans.append(B.pop(max_i))
reverse_ans.reverse()
print(' '.join(map(str,reverse_ans)))



### FIXED CODE ###

_N=input()
A=list(map(int,input().split()))
B=[0]*len(A)
for i in range(0,len(A)):
  B[A[i]-1]=i+1
print(' '.join(map(str,B)))
### BUGGY CODE ###

N,K=map(int,input().split())
P=list(map(int,input().split()))
A=[0]
for k in range(0,N-K+1):
  On=0
  for l in range(0,K):
    On+=P[k+l]
  A.append(On)

print((max(A)+K)/2)

### FIXED CODE ###

#模範解答の通りにやってみる
N,K=map(int,input().split())
P=list(map(int,input().split()))
if K==1:
	print((max(P)+1)/2)
elif N==K:
	print((sum(P)+N)/2)
else:
	T=sum(P[0:(K)])
	S=sum(P[0:(K)])
	for k in range(0,N-K):
		S=S-P[k]+P[k+K]
		if T<=S:
			T=S
		else:
			continue
	print((T+K)/2)
### BUGGY CODE ###

import collections

def check(A,num):
    count = 0
    for j in A:
        n = A[j]
        if j == num:
            n -= 1
#         print(n)
        count += n * (n - 1) / 2
    return int(count)
    

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

A2 = collections.Counter(A)
# print(A2)
for i in range(0,N):
    num = A[i]
    out = check(A2,num)
    print(out)

### FIXED CODE ###

import collections

def check(A):
    count = 0
    for j in A:
        n = A[j]
        if n > 1:
            count += n * (n - 1) / 2
            
    return int(count)


N = int(input())
A = list(map(int, input().split(" ")))
A2 = collections.Counter(A)
# print(A2)
Nsum = check(A2)
# print(Nsum)
for i in range(0,N):
    num = A[i]
    count = A2[num]
    out = Nsum - ( count - 1 )
    print(out)
### BUGGY CODE ###

h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I:=h*w]*I
m+=d,
q=[a:=~w+a*w+b]
d[a]=1
for s in q:
 for x in 0,1,2,3:
  for z in range(k):
   y=~z,0,z+1,0;i,j=s//w+y[x],s%w+y[~x];t=i*w+j;p=d[s]+1
   if'.'!=m[i][j]or d[t]<p:break
   if d[t]>p:q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

### FIXED CODE ###

I=9**9
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I]*h*w
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[t]<=d[s]:break
   if d[t]==I:q+=t,;d[t]=d[s]+1
print(d[~w+f*w+g]%I-1)
### BUGGY CODE ###

def main():
    MOD = 10**9 + 7
    S = input()
    N = len(S)
    dp = [[0 for _ in range(13)] for _ in range(N + 1)]
    dp[0][0] = 1
    for i, c in enumerate(S):
        for j in range(10):
            if c != '?' and c != str(j):
                continue
            for k in range(13):
                dp[i + 1][(10 * k + j) % 13] += dp[i][k]
        for k in range(13):
            dp[i + 1][k] %= MOD
    print(dp[N][5])


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    MOD = 10**9 + 7
    S = input()
    N = len(S)
    dp = [[0 for _ in range(13)] for _ in range(N + 1)]
    dp[0][0] = 1
    for i, c in enumerate(S):
        for j in range(10):
            if c != '?' and c != str(j):
                continue
            for k in range(13):
                dp[i + 1][(10 * k + j) % 13] += dp[i][k]
        for k in range(13):
            dp[i + 1][k] %= MOD
    print(dp[N][5])


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

n = int(input())
S = [None]*n
ans = 0

for i in range(n):
    s = list(input())
    s.sort()
    s_s = ''.join(s)
    S[i] = s_s
S.sort()
#print(S)
for i in range(n-1):
    f = True
    F = True
    t = 1
    while F:
        for j in range(10):
            if S[i][j] != S[i+t][j]:
                f = False
                F = False
                break
        if f:
            ans += 1
            t += 1
            if t+i >= n:
                break
print(ans)

### FIXED CODE ###

n = int(input())
S = {}
ans = 0

for i in range(n):
    s = list(input())
    s.sort()
    s_s = ''.join(s)
    if s_s in S:
        ans += S[s_s]
        S[s_s] += 1
    else:
        S[s_s] = 1

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

import numpy as np

n, m = map(int, input().strip().split())
dp = [float('inf')] * (2**n)
dp[0] = 0
for i in range(m):
    a, b = input().strip().split()
    a = int(a)
    b = int(b)
    c = input().strip().split()
    mask = 0
    for i in c:
        mask += 2**(int(i) - 1)

    for j in range(2**n):
        dp[j | mask] = min(dp[j] + a, dp[j | mask])

print(dp[2**n - 1] if dp[2**n - 1] < float('inf') else -1)

### FIXED CODE ###

n,m = input().split(' ')
n = int(n)
m = int(m)
dp = [float('inf')]*2**n
dp[0] = 0
for i in range(m):
    a,b = input().split(' ')
    a = int(a)
    b = int(b)
    ngo = 0
    for j in input().split(' '):
        ngo += 2**(int(j)-1)
    for j in range(2**n):
        if dp[j|ngo] > dp[j]+a:
            dp[j|ngo] = dp[j]+a
    
if dp[2**n-1] == float('inf'):
    print(-1)
    exit(0)
print(dp[2**n-1])
### BUGGY CODE ###

N = int(input())
A_lis = [int(input()) for i in range(N)]
for a in A_lis:
  if a ==max(A_lis):
    print(sorted(A_lis)[N-2])
  else:
    print(max(A_lis))
  

### FIXED CODE ###

N = int(input())
A_lis = [int(input()) for i in range(N)]
A_lis_sort = sorted(enumerate(A_lis),key = lambda x:x[1])
max_index = A_lis_sort[-1][0] 
for i in range(N):
  if i == max_index:
    print(A_lis_sort[-2][1])
  else:
    print(A_lis_sort[-1][1])
### BUGGY CODE ###

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

        l = []

        for i in range(N-1):
                l.append(A.count(i+1))
        l.append(0)

        ans = "\n".join([str(x) for x in l])
        print(ans)

if __name__=="__main__":
        main()

### FIXED CODE ###

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

        l = [0]*N

        for a in A:
                l[a-1] += 1

        ans = "\n".join([str(x) for x in l])
        print(ans)

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

import sys
sys.setrecursionlimit(1000)

N, W = map(int, input().split())
wv = [[int(i) for i in input().split()] for _ in range(N)]
wv.sort()

mem = dict()

def knapsack(i, w) :
    if i == N :
        return 0
    
    if (i, w) in mem :
        return mem[(i, w)]
    
    if w + wv[i][0] <= W :
        mem[(i, w)] = max(knapsack(i+1, w+wv[i][0])+wv[i][1], knapsack(i+1, w))
        return mem[(i, w)]
    else :
        return 0
        
print(knapsack(0, 0))

### FIXED CODE ###

N, W = map(int, input().split())
wv = [[int(i) for i in input().split()] for _ in range(N)]
V = max([wv[i][1] for i in range(N)]) * N

dp = [[float('inf')] * (V + 1) for _ in range(N + 1)]
dp[0][0] = 0
for i in range(N) :
    for j in range(V+1) :
        if j >= wv[i][1] :
            dp[i+1][j] = min(dp[i][j-wv[i][1]] + wv[i][0], dp[i][j])
        else :
            dp[i+1][j] = dp[i][j]

for i in range(V, -1, -1) :
    if dp[N][i] <= W :
        print(i)
        break
### BUGGY CODE ###

n,m = map(int,input().split())
list = [[int(i) for i in input().split()] for i in range(n)]
temp = [0]
ans = 0

for i in range(1,1+m):
  for j in list:
    if j[0] == i:
      temp.append(j[1])
  ans += max(temp)
  l = int(len(temp) -1)
  if l >= 1:
    temp = sorted(temp)
    temp = temp[:l]
print(ans)

### FIXED CODE ###

import heapq as hp
import sys
def input():
    return sys.stdin.readline()

n,m = map(int,input().split())
list = [[int(i) for i in input().split()] for i in range(n)]
temp = [0]
ans = 0
a = 0
j = 0
list = sorted(list)

for i in range(1,1+m):
  for j in range(a,len(list)):
    if list[j][0] == i:
      hp.heappush(temp,-list[j][1])
    else:
      a = j
      break
  if len(temp) > 0:
    ans -= hp.heappop(temp)
print(ans)
### BUGGY CODE ###

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

for i in range(N-1):
    for j in range(N-i-1):
        if A[i] == A[i+j+1]:
            print("NO")
            exit()

print("YES")

### FIXED CODE ###

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

for i in range(N-1):
    if A[i] == A[i+1]:
        print("NO")
        exit()

print("YES")
### BUGGY CODE ###

from queue import Queue

#入力
H, W = map(int, input().split())

#lst = [['a']*W for _ in range(H)]
count = 0 #白色のマスの総数
lst = []
row = []
for i in range(H):
    row = list(input())
    count += row.count('.')
    lst += [row]
 
#for i in range(H):
#    for j in range(W):
#        if lst[i][j] == '.':
#            count += 1

#sx, sy = 1, 1 #スタート位置
#gx, gy = H, W #ゴール位置

move = [[-1, 0], [1,0], [0, -1], [0, 1]]

def bfs():
    q = Queue()
    INF = 10 ** 3
    d = [[INF]* W for _ in range(H)]
    q.put(0)
    q.put(0)
    d[0][0] = 0

    while True:
        px = q.get()
        py = q.get()
        if px == H-1 and py == W-1:
            break
        else:
            for dx, dy in move:
                nx = px + dx
                ny = py + dy

                if 0 <= nx and nx < H and 0 <= ny and ny < W and lst[nx][ny] == '.' and d[nx][ny] == INF:
                    q.put(nx)
                    q.put(ny)
                    d[nx][ny] = d[px][py] + 1
    return d[H-1][W-1]

a = bfs()

if a == 10 **9:
    print (-1)
else:
    print (count - a - 1)

### FIXED CODE ###

from queue import Queue

#入力
H, W = map(int, input().split())

#lst = [['a']*W for _ in range(H)]
count = 0 #白色のマスの総数
lst = []
row = []
for i in range(H):
    row = list(input())
    count += row.count('.')
    lst += [row]
 
#for i in range(H):
#    for j in range(W):
#        if lst[i][j] == '.':
#            count += 1

#sx, sy = 1, 1 #スタート位置
#gx, gy = H, W #ゴール位置

move = [[-1, 0], [1,0], [0, -1], [0, 1]]

def bfs():
    q = Queue()
    INF = 10 ** 9
    d = [[INF]* W for _ in range(H)]
    q.put(0)
    q.put(0)
    d[0][0] = 0

    while True:
        if q.empty():
            break
        else:
            px = q.get()
            py = q.get()
            if px == H-1 and py == W-1:
                break
            else:
                for dx, dy in move:
                    nx = px + dx
                    ny = py + dy

                    if 0 <= nx and nx < H and 0 <= ny and ny < W and lst[nx][ny] == '.' and d[nx][ny] == INF:
                        q.put(nx)
                        q.put(ny)
                        d[nx][ny] = d[px][py] + 1
    return d[H-1][W-1]

a = bfs()

if a == 10 **9:
    print (-1)
else:
    print (count - a - 1)
### BUGGY CODE ###

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

v = {}
for i in range(m):
    a,b = map(int,input().split())
    if a not in v:
        v[a] = [b]
    else:
        v[a].append(b)

    if b not in v:
        v[b] = [a]
    else:
        v[b].append(a)

st = [1]

ans = [-1 for i in range(n)]
ans[0] = 0

while True:
    buf = []
    updates = {}
    for s in st:
        nex = v[s]
        for to in nex:
            if ans[to-1] != -1:
                continue
            else:
                buf.append(to)
                updates[to-1] = s
    for u in updates.keys():
        ans[u] = updates[u]
    st = buf
    if len(buf) == 0:
        break

print("Yes")
for i in range(1,n):
    print(ans[i])



### FIXED CODE ###

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

v = {}
for i in range(m):
    a,b = map(int,input().split())
    if a not in v:
        v[a] = [b]
    else:
        v[a].append(b)

    if b not in v:
        v[b] = [a]
    else:
        v[b].append(a)

st = [1]

ans = [-1 for i in range(n)]
ans[0] = 0

while True:
    buf = set()
    updates = {}
    for s in st:
        nex = v[s]
        for to in nex:
            if ans[to-1] != -1:
                continue
            else:
                buf.add(to)
                # buf.append(to)
                updates[to-1] = s
    for u in updates.keys():
        ans[u] = updates[u]
    st = buf
    # print(st)
    if len(buf) == 0:
        break

print("Yes")
for i in range(1,n):
    print(ans[i])
### BUGGY CODE ###

S=input()
# S = "??2??5"
# S= "?44"

MOD = 10**9+7
dp = {}
for i in range(13):
    dp[(-1,i)] = 0
dp[(-1,0)] = 1
for t,ss in enumerate(S[::-1]):
    for i in range(13):
        dp[(t,i)] = 0
    if ss=="?":
        for i in range(13):
            for j in range(10):
                dp[(t,(j*10**t+i)%13)] += dp[(t-1,i)]
                dp[(t,(j*10**t+i)%13)] %= MOD
    else:
        s = int(ss)
        for i in range(13):
            dp[(t,(s*10**t+i)%13)] += dp[(t-1,i)]
            dp[(t,(s*10**t+i)%13)] %= MOD


print(dp[(t,5)])

### FIXED CODE ###

S=input()
# S="".join(["?" for _ in range(10**5)])
# S = "??2??5"
# S= "?44"

MOD = 10**9+7
dp = [[0 for i in range(13)] for j in range(len(S)+1)]
dp[0][0] = 1
for t,ss in enumerate(S[::-1]):
    if t==0:
        tt = 1
    else:
        tt = (10*tt)%13
    if ss=="?":
        for i in range(13):
            for j in range(10):
                k = (j*tt+i)%13
                dp[t+1][k] += dp[t][i]%MOD
    else:
        s = int(ss)
        for i in range(13):
            k = (s*tt+i)%13
            dp[t+1][k] += dp[t][i]%MOD

print(dp[t+1][5]%MOD)