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

def turn(x):
    return 1 if x==0 else 0

input_data = input().split()
n = int(input_data[0])
m = int(input_data[1])

array = [[-1 for _ in range(m+2)] for _ in range(n+2)]

for i in range(1, n+1):
    for j in range(1, m+1):
        array[i][j] = 1

for i in range(1, n+1):
    for j in range(1, m+1):
        if array[i-1][j-1] != -1 : array[i-1][j-1] = turn(array[i-1][j-1])
        if array[i-1][j]   != -1 : array[i-1][j]   = turn(array[i-1][j])
        if array[i-1][j+1] != -1 : array[i-1][j+1] = turn(array[i-1][j+1])
        if array[i][j-1]   != -1 : array[i][j-1]   = turn(array[i][j-1])
        if array[i][j+1]   != -1 : array[i][j+1]   = turn(array[i][j+1])
        if array[i+1][j-1] != -1 : array[i+1][j-1] = turn(array[i+1][j-1])
        if array[i+1][j]   != -1 : array[i+1][j]   = turn(array[i+1][j])
        if array[i+1][j+1] != -1 : array[i+1][j+1] = turn(array[i+1][j+1])

count = 0

for i in range(1, n+1):
    for j in range(1, m+1):
        count += array[i][j]

print(count)

### FIXED CODE ###

input_data = input().split()
n = int(input_data[0])
m = int(input_data[1])

if n == 1 or m == 1:
    if n == 1 and m != 1:
        print(m-2)
    elif m == 1 and n != 1:
        print(n-2)
    elif n == 1 and m==1:
        print(1)

if n>=2 and m>=2:
    print(n*m-(2*n+2*(m-2)))
### BUGGY CODE ###

import copy

def main():
    n = int(input())
    num_list = [int(input()) for _ in range(n)]
    
    for i in range(n):
        tmp = copy.deepcopy(num_list)
        tmp.pop(i)
        print(max(set(tmp)))
        
if __name__ == '__main__':
    main()

### FIXED CODE ###

import copy

def main():
    n = int(input())
    num_list = [int(input()) for _ in range(n)]

    tmp = copy.deepcopy(num_list)
    tmp.sort()

    max_first = max(num_list)
    max_second = tmp[n-2]
    
    for num in num_list:
        if num == max_first:
            print(max_second)
            continue
        print(max_first)
        
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import numpy as np


def calc_mul4_dp(n, aaa):
    dp_base = np.arange(16, dtype=np.int64)
    dp = dp_base.copy()
    result = [0, 0]

    next_a = aaa[-1]
    for i in range(n - 2, -1, -1):
        ndp = dp_base.copy()

        a = aaa[i]
        if a > next_a:
            cnt = 0  # a[i]以上になるためにa[i+1]に4をかけなければならない最小回数
            b = next_a
            while a > b:
                b <<= 2
                cnt += 1
            ndp[:-cnt] += dp[cnt:]
            ndp[-cnt:] += dp[-1] + dp_base[1:cnt + 1] * (n - i - 1)
        else:
            cnt = 0  # a[i]に4をかけても次に影響が出ない最大回数
            b = a
            while next_a >= b:
                b <<= 2
                cnt += 1
            cnt -= 1
            ndp[:cnt] += dp[0]
            ndp[cnt:] += dp[:16 - cnt]
        next_a = a
        result.append(ndp[0])
        dp = ndp
    result.reverse()
    return np.array(result)


def solve(n, aaa):
    fdp = calc_mul4_dp(n, aaa)
    bdp = calc_mul4_dp(n, aaa[::-1])[::-1]
    mul4dp = (fdp + bdp) * 2
    return (mul4dp + np.arange(n + 1)).min()


def test():
    import random
    n = 200000
    aaa = random.choices(range(1, 10 ** 9), k=n)
    print(n)
    print(aaa)
    print(solve(n, aaa))


n = int(input())
aaa = list(map(int, input().split()))
print(solve(n, aaa))


### FIXED CODE ###

import numpy as np


def calc_mul4_dp(n, aaa):
    # dp[i] = aaa[i] 以右をascendingにするために4をかける必要のある回数

    # 「支配的」である数と位置を記録するstack
    # 支配的: それを4倍すると、それより右で次に支配的な数までは全て4倍する必要のある数
    # (支配的な数, ←をいじらなかった場合の支配区間の最後の数, 最初の数の位置)
    stack = [(10 ** 20, 10 ** 20, n), (aaa[-1], aaa[-1], n - 1)]
    INF = 10 ** 19
    result = [0, 0]

    for i in range(n - 2, -1, -1):
        a = aaa[i]
        c = a
        inc = 0
        while (c << 2) > stack[-1][0]:
            b, e, j = stack.pop()
            mul = 0
            while c > b:
                b <<= 2
                mul += 1
            inc += mul * (stack[-1][2] - j)
            c = min(e << (2 * mul), INF)
        stack.append((a, c, i))
        result.append(inc)
        # print(a, stack, result)
    result = np.add.accumulate(result, dtype=np.int64)[::-1]
    return result


def solve(n, aaa):
    fdp = calc_mul4_dp(n, aaa)
    bdp = calc_mul4_dp(n, aaa[::-1])[::-1]
    # print(fdp)
    # print(bdp)
    return ((fdp + bdp) * 2 + np.arange(n + 1, dtype=np.int64)).min()


def test():
    import random
    n = 200000
    # aaa = random.choices(range(1, 10 ** 9), k=n)
    # aaa = [1, 10 ** 9] * (n // 2)
    aaa = list(range(10 ** 9, 10 ** 9 - n, -1))
    print(n)
    # print(aaa)
    print(solve(n, aaa))


# test()

n = int(input())
aaa = list(map(int, input().split()))
print(solve(n, aaa))
### BUGGY CODE ###

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

N = int(input())
P = list(map(lambda x: int(x)-1, input().split()))

def nears(n):
    ret = []
    if n%N != 0:
        ret.append(n-1)
    if n%N != N-1:
        ret.append(n+1)
    if n//N != 0:
        ret.append(n-N)
    if n//N != N-1:
        ret.append(n+N)
    return ret

NeedS = []
for p in range(N**2):
    NeedS.append(min([p%N, p//N, N-1-p%N, N-1-p//N]))

isChecked = [False]*(N**2)
ans = 0
for p in P:
    ans += NeedS[p]
    isChecked[p] = True
    q = deque()
    q.append(p)
    while q:
        p = q.popleft()
        d = NeedS[p]
        if not isChecked[p]: d += 1
        for np in nears(p):
            if d < NeedS[np]:
                NeedS[np] = d
                q.append(np)
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
from collections import deque

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

def nears(n):
    ret = []
    if n%N != 0:
        ret.append(n-1)
    if n%N != N-1:
        ret.append(n+1)
    if n//N != 0:
        ret.append(n-N)
    if n//N != N-1:
        ret.append(n+N)
    return ret

NeedS = []
for p in range(N**2):
    NeedS.append(min([p%N, p//N, N-1-p%N, N-1-p//N]))

isChecked = [False]*(N**2)
ans = 0
for p in P:
    p -= 1
    ans += NeedS[p]
    isChecked[p] = True
    q = deque()
    q.append(p)
    while q:
        p = q.popleft()
        d = NeedS[p]
        if not isChecked[p]: d += 1
        for np in nears(p):
            if d < NeedS[np]:
                NeedS[np] = d
                q.append(np)
print(ans)
### BUGGY CODE ###

it = input()
it = it.split()
n = int(it[0])
m = int(it[1])
p1 = []
p2 = []
for _ in range(m):
    itf = input()
    itf = itf.split()
    a = int(itf[0])
    b = int(itf[1])
    p1.append(a)
    p2.append(b)
d = [1, ]
c = [0, ]
l = 0
flag = True
for _ in range(1, n):
    for i in range(m):
        if p1[i] == d[l]:
            d.append(p2[i])
            c.append(p1[i])
        if p2[i] == d[l]:
            d.append(p1[i])
            c.append(p2[i])
    if len(d) > l:
        l += 1
    else:
        flag = False
        break
con = []
for i in range(2, n+1):
    for y, j in enumerate(d):
        flfl = True
        if j == i:
            con.append(c[y])
            flfl=False
            break
    if flfl:
        con.append(0)
        break

if 0 in con:
    print('No')
else:
    print('Yes')
    for i in con:
        print(i)

### FIXED CODE ###

it = input()
it = it.split()
n = int(it[0])
m = int(it[1])
p = [[] for _ in range(n)]
for _ in range(m):
    itf = input()
    itf = itf.split()
    a = int(itf[0])
    b = int(itf[1])
    p[a-1].append(b)
    p[b-1].append(a)
d = [1, ]
con = [0] * n
while d:
    l = d.pop(0)
    for k in p[l-1]:
        if con[k-2]==0:
            d.append(k)
            con[k-2] = l
print('Yes')
for i in range(n-1):
    print(con[i])
### BUGGY CODE ###

s = list(input())
c = 0
state = 0
res = 0
stack = 0
loop = 0
while c < len(s):
    """
    loop = loop + 1
    if loop > 100:
        break
    print("c" + str(c))
    print("cur: " + "".join(s))
    print("state" + str(state))
    """
    if state == 0:
        if s[c] == "A":
            state = 1
            stack = 0
    elif state == 1:
        if s[c] == "B":
            state = 2
        else:
            if s[c] == "A":
                state = 1
                stack += 1
                #print("stack up:" + str(stack))
            else:
                state = 0
                stack = 0
    elif state == 2:
        if s[c] == "C":
            #print("hit")
            #print(" stack:" + str(stack))
            res += 1 + stack
            s[c-2-stack], s[c-1-stack], s[c-stack] = "B", "C", "A"
            for i in range(stack):
                s[c-i] = "A"
            c = c - 3 - stack
            state = 0
            stack = 0
            if s[c] == "A":
                state = 1
                stack = 0
        else:
            state = 0
            stack = 0
            if s[c] == "A":
                state = 1
                stack = 0
    c = c + 1
print(res)

### FIXED CODE ###

import re
s = input()
s = s.replace("BC", "X")
m = re.search(r"[AX]+", s)
count = 0
res = 0
for m in re.finditer(r"([AX]+)", s):
    t = str(m.groups()[0])
    t = ''.join(list(reversed(t)))
    count = 0
    for i in range(len(t)):
        if t[i] == "A":
            res += (i - count)
            count += 1
print(res)
### BUGGY CODE ###

import sys,queue,math,copy,itertools,bisect,collections
LI = lambda : [int(x) for x in sys.stdin.readline().split()]

X,Y,Z,K = LI()
A = LI()
B = LI()
C = LI()


A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

h = A[0] + B[0] + C[0]
l = 0
while h > l+1:
    m = (h+l) // 2

    num = 0
    for a in A:
        j = len(C) - 1
        for i in B:
            while i + C[j] < m - a:
                j -= 1
                if j < 0: break
            else:
                num += j + 1
                continue
            break
    if num > K:
        l = m
    else:
        h = m

ans = []
for a in A:
    j = len(C) - 1
    for i in B:
        while i + C[j] < l - a:
            j -= 1
            if j < 0: break
        else:
            for k in range(j+1):
                ans.append(a+i+C[k])
ans.sort(reverse=True)
print (*ans[:K],sep='\n')



### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections
LI = lambda : [int(x) for x in sys.stdin.readline().split()]

X,Y,Z,K = LI()
A = LI()
B = LI()
C = LI()

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

h = A[0] + B[0] + C[0]
l = 0
while h > l+1:
    m = (h+l) // 2

    num = 0
    for a in A:
        j = len(C) - 1
        for i in B:
            while i + C[j] < m - a:
                j -= 1
                if j < 0: break
            else:
                num += j + 1
                continue
            break
    if num > K:
        l = m
    else:
        h = m

ans = []
cnt = 0
for a in A:
    j = len(C) - 1
    last_cnt = cnt
    for i in B:

        while i + C[j] <= l - a:
            j -= 1
            if j < 0: break
        else:
            for k in range(j+1):
                ans.append(a+i+C[k])
                cnt += 1
            continue
        break
ans.sort(reverse=True)
for _ in range(K-len(ans)):
    ans.append(l)
print (*ans[:K],sep='\n')
### BUGGY CODE ###

import heapq
h,w,k = list(map(int, input().split()))
x1,y1,x2,y2 = list(map(int, input().split()))
x1,y1,x2,y2 = x1-1,y1-1,x2-1,y2-1
c = [[]*w for _ in range(h)]
dp = [[0]*w for _ in range(h)]
que = []
for i in range(h):
  for j,s in enumerate(input()):
    c[i].append(s)
    if s != '.':
      dp[i][j] = -1

ans = 0
dp[x1][y1] = 1
heapq.heappush(que, (dp[x1][y1], [x1,y1]))
dx = [1,0,-1,0]
dy = [0,1,0,-1]
flg = 0
while que:
  p= heapq.heappop(que)
  p = p[1]
  if (p[0] == x2) &( p[1] == y2):break
  for i in range(4):
    for ki in range(1,k+1):
      nx = p[0] + dx[i]*ki
      ny = p[1] + dy[i]*ki
      if (nx>=0) & (nx<=(h-1)) & (ny>=0) & (ny<=(w-1)):
        if dp[nx][ny] == -1:break
        while dp[nx][ny] == 0:
          dp[nx][ny] = dp[p[0]][p[1]] + 1
          if (nx == x2) &( ny == y2):exit( print(dp[x2][y2]-1))
          heapq.heappush(que, (dp[nx][ny], [nx,ny]))

if dp[x2][y2] != 0:
  print(dp[x2][y2]-1)
else:
  print(-1)

### FIXED CODE ###

#import heapq
from collections import deque
h,w,k = list(map(int, input().split()))
x1,y1,x2,y2 = list(map(int, input().split()))
x1,y1,x2,y2 = x1-1,y1-1,x2-1,y2-1
dp = [[-1]*w for _ in range(h)]
#que = []
que = deque()
c = [input() for _ in range(h)]

dp[x1][y1] = 0
#heapq.heappush(que, (dp[x1][y1], [x1,y1]))
que.append((x1,y1))
dx = [1,0,-1,0]
dy = [0,1,0,-1]
while que:
  x,y=que.popleft()
  if x==x2 and y==y2:
    exit(print(dp[x][y]))
  for dx,dy in [[1,0],[-1,0],[0,-1],[0,1]]:
    for i in range(1,k+1):
      xx=x+dx*i
      yy=y+dy*i
      if not(0<=xx<h and 0<=yy<w) or c[xx][yy]=="@":break
      if 0<=dp[xx][yy]<=dp[x][y]:break
      if dp[xx][yy]==-1:que.append((xx,yy))
      dp[xx][yy]=dp[x][y]+1
print(-1)
### BUGGY CODE ###

import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from itertools import product
def main():
    n = int(input())
    s = input()

    r = [0] * n
    g = [0] * n
    b = [0] * n
    for i, se in enumerate(s):
        if se == 'R':
            r[i] = 1
        elif se == 'G':
            g[i] = 1
        else:
            b[i] = 1

    res = sum(r) * sum(g) * sum(b)
    minus = 0
    for i1 in range(n):
        for i2 in range(n):
            for i3 in range(n):
                if r[i1] and g[i2] and b[i3]:
                    minus += i1 * 2 == (i2 + i3)
                    minus += i2 * 2 == (i1 + i3)
                    minus += i3 * 2 == (i1 + i2)
    print(res-minus)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    s = list(input())
    sr = [0] * n
    sg = [0] * n
    sb = [0] * n
    for i1 in range(n):
        ts = s[i1]
        if ts == 'R':
            sr[i1] = 1
        elif ts == 'G':
            sg[i1] = 1
        else:
            sb[i1] = 1
    if n <= 3:
        print(0)
        exit()
    r = 0
    for ia in range(0,n-3):
        ta = s[ia]
        if ta == 'R':
            r += sum(sg[ia+1:]) * sum(sb[ia+1:])
        elif ta == 'G':
            r += sum(sr[ia+1:]) * sum(sb[ia+1:])
        else:
            r += sum(sg[ia + 1:]) * sum(sr[ia + 1:])
        for ib in range((n - ia)//2+1):
            if ia + ib * 2 < n:
                if ta != s[ia + ib] and ta != s[ia + ib + ib] and s[ia+ib]!= s[ia + ib + ib]:
                    r -= 1
    print(r)

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

h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
inf=1000000000
wf=[[inf]*(h*w) for i in range(h*w)]
for i in range(h*w):
    k,l=i//w,i%w
    #print(l)
    if s[k][l]=="#":
        continue
    if k!=0:
        if s[k-1][l]==".":
            wf[i][i-w]=1
    if k!=h-1:
        if s[k+1][l]==".":
            wf[i][i+w]=1
    if l!=0:
        if s[k][l-1]==".":
            wf[i][i-1]=1
    if l!=w-1:
        if s[k][l+1]==".":
            wf[i][i+1]=1
    wf[i][i]=0
for i in range(h*w):
    for j in range(h*w):
        for k in range(h*w):
            wf[j][k]=min(wf[j][k],wf[j][i]+wf[i][k])
ans=0
for i in range(h*w):
    for j in range(h*w):
        if wf[i][j]!=inf:
            ans=max(ans,wf[i][j])
print(ans)

### FIXED CODE ###

import queue
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]

inf=100000000
ma=[]
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            x=[[inf for i_sub in range(w)] for j_sub in range(h)]
            #いまみているグリッド
            q=queue.Queue()
            d=0
            #初めのグリッド
            q.put([i,j])
            x[i][j]=0
            #次々にグリッドを辿って全部のグリッド辿ったら終わり
            while q.qsize()!=0:
                #距離を加算
                d+=1
                l=q.qsize()
                #今いるグリッドの数は数えておく
                for t in range(l):
                    I,J=q.get()
                    #今いるグリッドから次のグリッドへ
                    #その判定は"そこにグリッドがあるか","そこが辿れるのか","すでに辿っているのか"の三つです。
                    if I-1>=0 and s[I-1][J]=="." and x[I-1][J]==inf:
                        q.put([I-1,J])
                        #この更新をif文内で行わないと余計にグリッドを調べてしまう
                        x[I-1][J]=d
                    if I+1<=h-1 and s[I+1][J]=="." and x[I+1][J]==inf:
                        q.put([I+1,J])
                        x[I+1][J]=d
                    if J-1>=0 and s[I][J-1]=="." and x[I][J-1]==inf:
                        q.put([I,J-1])
                        x[I][J-1]=d
                    if J+1<=w-1 and s[I][J+1]=="." and x[I][J+1]==inf:
                        q.put([I,J+1])
                        x[I][J+1]=d
            ma_sub=0
            for k in range(h):
                for l in range(w):
                    if x[k][l]!=inf:
                        ma_sub=max(ma_sub,x[k][l])
            ma.append(ma_sub)

print(max(ma))
### BUGGY CODE ###

N, Q = map(int, input().split())
s = input()
      
for _ in range(Q):
  l, r = map(int, input().split())
  print(s[l - 1:r].count('AC'))


### FIXED CODE ###

from itertools import accumulate
from operator import add

N, Q = map(int, input().split())
S = input()
idx_list = [1 if S[i:i + 2] == 'AC' else 0 for i in range(len(S) - 1)]
idx_list_cumsum = [0] + list(accumulate(idx_list, add))

for _ in range(Q):
  l, r = map(int, input().split())
  print(idx_list_cumsum[r - 1] - idx_list_cumsum[l - 1])
### BUGGY CODE ###

from itertools import combinations

N = int(input())
S = input()
ans = set({})
lid = list(range(N))

# print(lid)
for p in combinations(lid, 3):
    ss = '_'.join([S[i] for i in lid if i in p])
    # print(p, ss)
    ans.add(ss)
print(len(ans))

### FIXED CODE ###

from itertools import combinations

N = int(input())
S = input()
count = 0

ans = set({})

for password in range(0, 1000):
    s = "{:03d}".format(password)
    s1, s2, s3 = s
    
    if s1 not in S:
        continue
    i1 = S.index(s1)
    if s2 not in S[i1+1:]:
        continue
    i2 = S[i1+1:].index(s2)
    if s3 not in S[i1+1:][i2+1:]:
        continue
    i3 = S[i1+1:][i2+1:].index(s3)
    # print(s, s1, s2, s3, "|", i1, i1 + i2, i1 + i2 + i3)
    ans.add(password)

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

memo = {}

def gcd(a, b):
    if (a, b) in memo.keys():
        return memo[(a, b)]
    if b == 0:
        return a
    return gcd(b, a % b)

n = input()
a_list = map(int, raw_input().split())
max_g = 0
for exclude in xrange(n):
    g = a_list[0] if exclude > 0 else a_list[1]
    for i in xrange(1, n):
        if i == exclude:
            continue
        g_new = gcd(g, a_list[i])
        memo[(g, a_list[i])] = g_new
        g = g_new
        if g <= max_g:
            break
    if g > max_g:
        max_g = g
print(max_g)


### FIXED CODE ###

def gcd(a, b):
    if b == 0:
        return a
    g = gcd(b, a % b)
    return g

n = input()
a_list = map(int, raw_input().split())

gs1 = [None] * n
gs1[0] = a_list[0]
for i in xrange(1, n):
    gs1[i] = gcd(gs1[i - 1], a_list[i])

gs2 = [None] * n
gs2[n - 1] = a_list[n - 1]
for i in reversed(xrange(n - 1)):
    gs2[i] = gcd(gs2[i + 1], a_list[i])

max_g = 0
for exclude in xrange(n):
    if exclude == 0:
        g = gs2[1]
    elif exclude == n - 1:
        g = gs1[n - 2]
    else:
        g = gcd(gs1[exclude - 1], gs2[exclude + 1])
    if g > max_g:
        max_g = g
print(max_g)
### BUGGY CODE ###

n = int(input())
S = input()
cnt = [0] * 1000
for i in range(1000):
    key = str(i).zfill(3)
    for j in range(n):
        if S[j] == key[0]:
            for k in range(j+1, n):
                if S[k] == key[1]:
                    for l in range(k+1, n):
                        if S[l] == key[2]:
                            cnt[int(key)] += 1
print(sum(c > 0 for c in cnt))

### FIXED CODE ###

n = int(input())
S = input()
ans = 0
def ok(i):
    pin = '{:0=3}'.format(i)
    j = 0
    for s in S:
        if s == pin[j]:
            j += 1
            if j == 3:
                return True
    else:
        return False

for i in range(1000):
    ans += ok(i)
print(ans)
### BUGGY CODE ###

import numpy as np
n = int(input())
a = np.empty((0,2),int)
for i in range(n):
    b = np.array([[int(i) for i in input().split()]])
    a = np.append(a,b,axis=0)

a = a[np.argsort(a[:, 1])]

ans = "Yes"
for i in range(len(a)):
    if sum(a[0:i+1,0]) > a[i,1]:
        ans = "No"
print(ans)

### FIXED CODE ###

import sys
from operator import itemgetter
def input():
    return sys.stdin.readline()[:-1]
n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
a.sort(key=itemgetter(1))
ans = "Yes"
k = 0
for i in range(len(a)):
    k += a[i][0]
    if k > a[i][1]:
        ans = "No"
        break
print(ans)
### BUGGY CODE ###

import copy, itertools
from scipy.sparse.csgraph import floyd_warshall

N, M, R = map(int, input().split())
r = [x-1 for x in list(map(int, input().split()))]

way_cost = [[float('inf')]*N for _ in range(N)]

for idx in range(N):
    way_cost[idx][idx] = 0

for _ in range(M):
    a, b, c = map(int, input().split())
    way_cost[a-1][b-1] = c
    way_cost[b-1][a-1] = c

# ワーシャルフロイド法で全ての街同士の最短距離を求める
shortest_path_cost = floyd_warshall(csgraph=way_cost, directed=False)

# 巡回ルートを総当りで調べ、最小コストを出力する
route_list = list(itertools.permutations(r))

for route in route_list:
    route_list.remove(route[::-1])

ans = float('inf')
for route in route_list:
    cost = 0
    for idx in range(R-1):
        cost += shortest_path_cost[route[idx]][route[idx+1]]
    ans = min(ans,cost)

print(int(ans))

### FIXED CODE ###

import copy, itertools
from scipy.sparse.csgraph import floyd_warshall

N, M, R = map(int, input().split())
r = [x-1 for x in list(map(int, input().split()))]

way_cost = [[float('inf')]*N for _ in range(N)]

for idx in range(N):
    way_cost[idx][idx] = 0

for _ in range(M):
    a, b, c = map(int, input().split())
    way_cost[a-1][b-1] = c
    way_cost[b-1][a-1] = c

# ワーシャルフロイド法で全ての街同士の最短距離を求める
shortest_path_cost = floyd_warshall(csgraph=way_cost, directed=False)

# 巡回ルートを総当りで調べ、最小コストを出力する
route_list = list(itertools.permutations(r))

ans = float('inf')
for route in route_list:
    cost = 0
    for idx in range(R-1):
        cost += shortest_path_cost[route[idx]][route[idx+1]]
    ans = min(ans,cost)

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

N = int(input())
A = list(map(int, input().split()))
ans_list = []

for i in range(N):
    num = A.index(i+1)
    ans_list.append(str(num+1))
    
print(" ".join(ans_list))

### FIXED CODE ###

N = int(input())
Ai_list = [number for number in map(int, input().split())]
Ai_And_i_list = {}
for i, Ai in enumerate(Ai_list):
    Ai_And_i_list[Ai] = i + 1
sorted_list = sorted(Ai_And_i_list.items())
for key, value in sorted_list:
    print(value)
### BUGGY CODE ###

n=int(input())
s=[]
a=[]
for i in range(0,n):
    s.append(input())
for i in range(0,n):
    if s[i] not in a:
        a.append(s[i])
print(len(a))

### FIXED CODE ###

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

inlist=input("").split(" ")
n=int(inlist[0])
m=int(inlist[1])
lista=[]
listb=[]
for i in range(n):
    lista+=[[]]
    listb+=[-1]
listb[0]=-2
listnum=[0]
for i in range(m):
    inlist=input("").split(" ")
    s=int(inlist[0])
    t=int(inlist[1])
    lista[s-1]+=[t-1]
    lista[t-1]+=[s-1]
k=0
while(k<len(listnum)):
    for i in lista[listnum[k]]:
        if not(i in listnum):
            listnum+=[i]
            listb[i]=listnum[k]
    k+=1

if (-1 in listb):
    print("No")
else:
    print("Yes")
    for i in listb[1:]:
        print(i+1)

### FIXED CODE ###

inlist=input("").split(" ")
n=int(inlist[0])
m=int(inlist[1])
lista=[]
listb=[]
for i in range(n):
    lista+=[[]]
    listb+=[-1]
listb[0]=-2

listnum=[0]
for i in range(m):
    inlist=input("").split(" ")
    s=int(inlist[0])
    t=int(inlist[1])
    lista[s-1]+=[t-1]
    lista[t-1]+=[s-1]
k=0
while(k<len(listnum)):
    for i in lista[listnum[k]]:
        
        if(listb[i]==-1):
            listb[i]=listnum[k]
            listnum+=[i]
    k+=1

if (-1 in listb):
    print("No")
else:
    print("Yes")
    for i in listb[1:]:
        print(i+1)