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

import numpy as np
from collections import deque

H, W = map(int, input().split())
maze = [input() for _ in range(H)]


def bfs(sty, stx):
    visited = [[-1 for _ in range(W)] for _ in range(H)]
    q = deque()
    q.append([sty, stx, 0])


    def is_ok(y, x):
        if not 0 <= y <= H - 1:
            return False
        if not 0 <= x <= W - 1:
            return False
        if visited[y][x] != -1:
            return False
        if maze[y][x] == '#':
            return False
        return True


    while q:
        y, x, lv = q.popleft()
        visited[y][x] = lv
        for i in (-1, 1):
            if is_ok(y+i, x):
                q.append([y+i, x, lv+1])
            if is_ok(y, x+i):
                q.append([y, x+i, lv+1])

    visited = np.array(visited)
    return np.max(visited)

res = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == '.':
            steps = bfs(i, j)
            if steps > res:
                res = steps

print(res)

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
maze = [input() for _ in range(H)]


def bfs(sty, stx):
    visited = [[-1]*W for _ in range(H)]
    q = deque()
    visited[sty][stx] = 0
    q.append((sty, stx, 0))


    def is_ok(y, x):
        if not 0 <= y <= H - 1:
            return False
        if not 0 <= x <= W - 1:
            return False
        if visited[y][x] != -1:
            return False
        if maze[y][x] == '#':
            return False
        return True


    while q:
        y, x, lv = q.popleft()
        for i in (-1, 1):
            if is_ok(y+i, x):
                visited[y+i][x] = lv+1
                q.append((y+i, x, lv+1))
            if is_ok(y, x+i):
                visited[y][x+i] = lv + 1
                q.append((y, x+i, lv+1))

    return max(max(r) for r in visited)

res = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == '.':
            res = max(res, bfs(i, j))

print(res)
### BUGGY CODE ###

from collections import Counter, defaultdict

n, k, q = map(int, input().split())
A = [int(input()) for _ in range(q)]
C = Counter(A)
d = defaultdict(int)
for key, val in C.items():
    d[key] = k + val - q
for i in range(1, n+1):
    if i not in A:
        d[i] = k-q
for i in range(1, n+1):
    if d[i] <= 0:
        print('No')
    else:
        print('Yes')


### FIXED CODE ###

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

menber = [0]*n
if q-k >= 0:
    for i in range(q):
        ans = int(input())
        menber[ans-1] += 1
else:
    menber = [1000000]*n

for j in menber:
    if j > q-k:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

import copy

n = int(input())
x = list(map(int,input().split()))


for i in range(n):
  xx = copy.deepcopy(x)
  xx.pop(i)
  xx.sort()
  print(xx[(len(xx) + 1) // 2 - 1])

### FIXED CODE ###

import copy

n = int(input())
x = list(map(int,input().split()))

xx= sorted(x)
L_x = xx[n//2 - 1]
R_x = xx[n//2]

for arr in x:
  print(L_x if R_x <= arr else R_x)
### BUGGY CODE ###

input()
s = input()

def f(i):
  return s[0:i].count('W') + s[i:].count('E')

arr = []

for i in range(len(s)):
  arr.append(f(i))

print(min(arr))

### FIXED CODE ###

input()
s = input()

l = 0
r = s[1:].count('E')
x = l + r

for i in range(1, len(s)):
  if s[i - 1] == 'W':
    l += 1

  if s[i] == 'E':
    r -= 1
  x = min(x, l + r)

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

S = list(map(str,input()))

counter = 0

for i in range(len(S)):
    for j in range(i,len(S)):
        s = int("".join(S[i:j+1]))
        if s % 2019 == 0:
            counter += 1

print(counter)


### FIXED CODE ###

S = list(map(int,input()))[::-1] #逆順

counter = 0
amari = [0]*2019
amari[0] = 1

s,d = 0,1

for i in S:
    s += i *d
    amari[s%2019] += 1
    d *= 10
    d %= 2019


for i in range(2019):
    counter += amari[i] * (amari[i]-1) / 2


print(int(counter))
### BUGGY CODE ###

s=input()
n=int(input())
l=[]
r=[]
cnt=0
for i in range(n):
    e=list(map(str,input().split()))
    q=int(e[0])
    if len(e)!=1:
        f=int(e[1])
        c=e[2]
    if q==2:
        if (f==1 and cnt%2==0) or (f==2 and cnt%2!=0):
            s=c+s
        else:
            s=s+c
    else:
        cnt+=1
if cnt%2==0:
    print(s)
else:
    print(s[::-1])

### FIXED CODE ###

s=input()
n=int(input())
cnt=0
l=[]
r=[]
for i in range(n):
    e=list(map(str,input().split()))
    q=int(e[0])
    if len(e)!=1:
        f=int(e[1])
        c=e[2]
    if q==2:
        if (f==1 and cnt%2==0) or (f==2 and cnt%2!=0):
            l.append(c)
        else:
            r.append(c)
    else:
        cnt+=1
if cnt%2==0:
    print(''.join(l[::-1])+s+''.join(r))
else:
    print(''.join(r[::-1])+s[::-1]+''.join(l))
### BUGGY CODE ###

X, K, D = map(int, input().split())
X=abs(X)
if X==0 and K%2==0:
    ans=0
elif X==0 and K%2==1:
    ans=D
elif D>=X and K%2==0:
    ans=X
elif D>=X and K%2==1:
    ans=D-X
elif X>0 and D<X :
    if K*D<X:
        ans=X-K*D
    else:
        ans=X
        for i in range(0,K):
            ans=ans-D
            if ans<0:
                if (K-i)%2==0:
                    ans=ans+D
                    break
                else:
                    ans=-ans
                    break
print(ans)

### FIXED CODE ###

X, K, D = map(int, input().split())
X=abs(X)
if D>=X and K%2==0:
    ans=X
elif D>=X and K%2==1:
    ans=D-X
elif D<X and K*D<X:
    ans=X-K*D
else:
    ans=X%D
    if (X-ans)%2!=K%2:
        ans=D-ans
print(ans)
### BUGGY CODE ###

input();ans,limit=1,10**18
for i in map(int,input().split()):
  ans*=i
print([ans,-1][ans>limit])

### FIXED CODE ###

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

  if 0 in A:
    print(0)
    return
  
  num = 1
  max_num = 10**18
  for i in A:
    num *= i
    
    if num > max_num:
      print(-1)
      return
  
  print(num)
  
main()
### BUGGY CODE ###

import itertools

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

dist = [[float('inf')] * N for _ in range(N)]
for _ in range(M):
	a, b, c = map(int, input().split())
	a -= 1
	b -= 1
	dist[a][b] = dist[b][a] = c

for k in range(N):
	for i in range(N):
		for j in range(N):
			dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

ans = float('inf')
k = list(itertools.permutations(r))
for i in k:
	sumDist = 0
	for j in range(len(i) - 1):
		sumDist += dist[i[j]][i[j+1]]
	ans = min(ans, sumDist)
print(ans)

### FIXED CODE ###

import itertools
 
N, M, R = map(int, input().split())
r = [int(x) - 1 for x in input().split()]
 
dist = [[float('inf')] * N for _ in range(N)]
for _ in range(M):
	a, b, c = map(int, input().split())
	a -= 1
	b -= 1
	dist[a][b] = dist[b][a] = c
 
for k in range(N):
	for i in range(N):
		for j in range(N):
			dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
 
ans = float('inf')
k = list(itertools.permutations(r))
for i in k:
	sumDist = 0
	for j in range(len(i) - 1):
		sumDist += dist[i[j]][i[j+1]]
	ans = min(ans, sumDist)
print(ans)
### BUGGY CODE ###

import itertools

d,g=map(int,input().split())
p=[0 for _ in range(d)]
c=[0 for _ in range(d)]
l=[[] for _ in range(d)]

for i in range(d):#値を取得！
	p[i],c[i]=map(int,input().split())

for i in range(d):#リストつくる！
	for j in range(p[i]+1):
		l[i].append((i+1)*100*j)
	l[i][p[i]] += c[i]

r = list(itertools.product(*l))
m = len(r)
for i in r:
	if sum(i)>=g:
		count = 0
		for j in range(d):
			count += l[j].index(i[j])
		if count <= m:
			m = count
print(m)

### FIXED CODE ###

d,g=map(int,input().split())
p=[0 for _ in range(d)]
c=[0 for _ in range(d)]
ans = 100**10

for i in range(d):#値を取得！
	p[i],c[i]=map(int,input().split())

for i in range(2**d):
	score = 0
	count = 0
	horyu = 0
	for j in range(d):
		if ((i >> j) & 1):
			score += (j+1)*p[j]*100 + c[j]
			count += p[j]
		else:
			horyu = j #あとまわし(最高点数の1種類)
	for i in range(p[horyu]):
		if score >= g and count < ans:
			ans = count
		score += (horyu + 1) * 100
		count += 1

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

n=int(input())
outp=[]
for i in range(n):
  outp.append(int(input()))
num=0
for j in list(set(outp)):
  num+=outp.count(j)%2
print(num)


### FIXED CODE ###

n=int(input())
outp=set()
for i in range(n):
  a=int(input())
  if(a in outp):outp.remove(a)
  else:outp.add(a)
print(len(outp))
### BUGGY CODE ###

n=int(input())
sum=0
a=list(map(int, input().split()))
for i in range(n):
  for j in range(i+1, n):
    #print(i,j)
    sum+=a[i]*a[j]
    sum = sum%((10**9)+7)

print(sum)

### FIXED CODE ###

n=int(input())
sums=0
a=list(map(int, input().split()))
b = sum(a)
for i in range(n):
  b -= a[i]
  sums += a[i]*b
  sums = sums%((10**9)+7)
print(sums)
### BUGGY CODE ###

n = int(input())
X = list(map(int,input().split()))
for i in range(n) :
  Y = X[:]
  Y.pop(i)
  Y.sort()
  medIndex = int((n-1)/2)
  print(Y[medIndex])

### FIXED CODE ###

n = int(input())
X = list(map(int,input().split()))
medIndex = int((n-1)/2)
Z = sorted(X[:])
c1 = Z[int(n/2-1)]
c2 = Z[int(n/2)]
for i in range(n) :
  if (X[i] <= c1) :
    print(c2)
  else :
    print(c1)
### BUGGY CODE ###

import copy

h, w = map(int, input().split())
s = [input() for _ in range(h)]
canlight = [[int(c == '.') for c in s[y]] for y in range(h)]
leftbeam = copy.deepcopy(canlight)
rightbeam = copy.deepcopy(canlight)
downbeam = copy.deepcopy(canlight)
upbeam = copy.deepcopy(canlight)

for y in range(h):
    for x in range(w - 1):
        leftbeam[y][x + 1] = (leftbeam[y][x] + 1) * canlight[y][x + 1]
    for x in range(1, w):
        rightbeam[y][-(x + 1)] = (rightbeam[y][-x] + 1) * canlight[y][-(x + 1)]

for x in range(w):
    for y in range(h - 1):
        downbeam[y + 1][x] = (downbeam[y][x] + 1) * canlight[y + 1][x]
    for y in range(1, h):
        upbeam[-(y + 1)][x] = (upbeam[-y][x] + 1) * canlight[-(y + 1)][x]

ans = 0
for y in range(h):
    for x in range(w):
        ans = max(ans, leftbeam[y][x] + rightbeam[y][x]
                     + downbeam[y][x] + upbeam[y][x] - 3)
print(ans)

### FIXED CODE ###

h, w = map(int, input().split())
s = [input() for _ in range(h)]
leftbeam = [[0 for _ in range(w)] for _ in range(h)]
rightbeam = [[0 for _ in range(w)] for _ in range(h)]
downbeam = [[0 for _ in range(w)] for _ in range(h)]
upbeam = [[0 for _ in range(w)] for _ in range(h)]

def can_light(y, x):
    return (0 <= y < h) and (0 <= x < w) and s[y][x] == '.'

for y in range(h):
    beamlen = 0
    for x in range(w):
        if can_light(y, x):
            beamlen += 1
        else:
            beamlen = 0
        leftbeam[y][x] = beamlen

for y in range(h):
    beamlen = 0
    for x in range(w):
        if can_light(y, w - x - 1):
            beamlen += 1
        else:
            beamlen = 0
        rightbeam[y][w - x - 1] = beamlen


for x in range(w):
    beamlen = 0
    for y in range(h):
        if can_light(y, x):
            beamlen += 1
        else:
            beamlen = 0
        downbeam[y][x] = beamlen

for x in range(w):
    beamlen = 0
    for y in range(h):
        if can_light(h - y - 1, x):
            beamlen += 1
        else:
            beamlen = 0
        upbeam[h - y - 1][x] = beamlen

ans = 0
for y in range(h):
    for x in range(w):
        ans = max(ans, leftbeam[y][x] + rightbeam[y][x]
                     + downbeam[y][x] + upbeam[y][x] - 3)

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

h, w = map(int, input().split())
n = (h + w) * 80
diff = [list(map(int, input().split())) for _ in range(h)]
for i in range(h):
    for j, b in enumerate(list(map(int, input().split()))):
        diff[i][j] = abs(diff[i][j] - b)
dp = [[0] * (w+1) for i in range(h+1)]
for i in range(h+1): dp[i][0] = -1
for i in range(w+1): dp[0][i] = -1
dp[1][1] = 1 << diff[0][0]

for i in range(1, h+1):
    for j in range(1, w+1):
        d = diff[i-1][j-1]
        for k in range(n):
            if (dp[i-1][j] != -1 and dp[i-1][j] >> k & 1) or (dp[i][j-1] != -1 and dp[i][j-1] >> k & 1):
                dp[i][j] |= 1 << abs(k+d)
                dp[i][j] |= 1 << abs(k-d)

ans = float("inf")
for i in range(n):
    if dp[h][w] >> i & 1:
        ans = min(ans, i)
print(ans)


### FIXED CODE ###

tdlist = lambda i, j, value=0: [[value] * j for _ in range(i)]

h, w = map(int, input().split())
D = 160*80
D2 = D*2+1

diff = [list(map(int, input().split())) for _ in range(h)]
for i in range(h):
    for j, b in enumerate(list(map(int, input().split()))):
        diff[i][j] = abs(diff[i][j] - b)

dp = tdlist(h, w)
dp[0][0] |= 1 << D+diff[0][0]
dp[0][0] |= 1 << D-diff[0][0]

for i in range(h):
    for j in range(w):
        if j:
            dp[i][j] |= dp[i][j-1] << diff[i][j]
            dp[i][j] |= dp[i][j-1] >> diff[i][j]
        if i:
            dp[i][j] |= dp[i-1][j] << diff[i][j]
            dp[i][j] |= dp[i-1][j] >> diff[i][j]

ans = float("inf")
for i in range(D2):
    if dp[h-1][w-1] >> i & 1:
        ans = min(ans, abs(i-D))
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
n,m,k = map(int,input().split())
f = []
h = []
t = [[] for _ in range(n)]
for _ in range(m):
  a,b = map(lambda x:int(x)-1,input().split())
  f.append((a,b))
  t[a].append(b)
  t[b].append(a)
for _ in range(k):
  a,b = map(lambda x:int(x)-1,input().split())
  h.append((a,b))
ans = [0]*n
c = [False]*n

def dfs(d):
  c[d] = True
  ret=[]
  for i in t[d]:
    if not c[i]:
      ret += dfs(i)
  return [d] + ret
m = []
for i in range(n):
  if not c[i]:
    e = dfs(i)
    g = len(e)-1
    if g > 1:
      m.append(set(e))
    for j in e:
      ans[j] = g
for i,j in f:
  ans[i]-=1
  ans[j]-=1
for i,j in h:
  for k in m:
    o = len(k & set((i,j)))
    if o == 2:
      ans[i]-=1
      ans[j]-=1
      break
    elif o == 1:
      break
print(*ans)

### FIXED CODE ###

n,m,k = map(int,input().split())
root = [i for i in range(n)]
height = [1 for i in range(n)]
def find(n):
  sn = n
  while n != root[n]:
    n = root[n]
  root[sn] = n
  return n
def union(a,b):
  a = find(a)
  b = find(b)
  if a==b:
    return
  elif height[a]>=height[b]:
    height[a] += height[b]
    height[b] = 0
    root[b] = a
  else:
    height[b] += height[a]
    height[a] = 0
    root[a] = b
l = [set() for _ in range(n)]
for i in range(m):
  a,b = map(lambda x:int(x)-1,input().split())
  union(a,b)
  l[a].add(b)
  l[b].add(a)
for i in range(k):
  a,b = map(lambda x:int(x)-1,input().split())
  if find(a)==find(b):
    l[a].add(b)
    l[b].add(a)
print(*[height[find(i)]-len(l[i])-1 for i in range(n)])
### BUGGY CODE ###

from collections import deque

n = int(input())
output = deque()
for i in range(n):
    li = input().split(' ')
    if(li[0] == 'insert'):
        output.appendleft(int(li[1]))
    elif(li[0] == 'delete'):
        try:
            output.remove(int(li[1]))
        except:
            pass
    elif(li[0] == 'deleteFirst'):
        output.popleft()
    elif(li[0] == 'deleteLast'):
        output.pop()
str_l = [str(o) for o in output]
print(' '.join(str_l))



### FIXED CODE ###

from collections import deque
n = int(input())
output = deque()
for i in range(n):
    li = input().split(' ')
    if(li[0] == 'insert'):
        output.appendleft(li[1])
    elif(li[0] == 'deleteFirst'):
        output.popleft()
    elif(li[0] == 'deleteLast'):
        output.pop()
    elif(li[0] == 'delete'):
        try:
            output.remove(li[1])
        except:
            pass
print(' '.join(output))
### BUGGY CODE ###

N,K=map(int,input().split())
c=[ [0 for _ in range(4000+1)] for _ in range(4000+1)]
mod=10**9+7
c[1][1]=1
c[1][0]=1
for n in range(2,4001):
    c[n][0]=1
    c[n][1]=n
    for r in range(2,n+1):
        c[n][r]=(c[n-1][r]+c[n-1][r-1])%mod
#print(c[4][0],c[4][1],c[4][2],c[4][3],c[4][4])
ans=0
for i in range(1,K+1):
    ans=(c[N-K+1][i]*c[K-1][i-1])%mod
    print(ans)



### FIXED CODE ###

N,K=map(int,input().split())
sz=max(N-K+2,K)
c=[ [0 for _ in range(K+1)] for _ in range(sz)]
mod=10**9+7
c[1][1]=1
c[1][0]=1
for n in range(2,sz):
    c[n][0]=1
    c[n][1]=n
    for r in range(2,K+1):
        c[n][r]=(c[n-1][r]+c[n-1][r-1])%mod
#print(c[4][0],c[4][1],c[4][2],c[4][3],c[4][4])
c[0][0]=1
ans=0
for i in range(1,K+1):
    ans=0 
    #print(i,N-K+1,i,c[N-K+1][i],c[K-1][i-1])
    if i<=N-K+1:
        ans=(c[N-K+1][i]*c[K-1][i-1])%mod
    print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
s = str(input())
r = []
g = []
b = []
for i in range(n):
  if s[i] == "R":
    r.append(i)
  elif s[i] == "G":
    g.append(i)
  else:
    b.append(i)
c = len(r)*len(g)*len(b)
for ri in r:
  for gi in g:
    for bi in b:
      if 3*(max(ri,gi,bi)+min(ri,gi,bi)) == 2*sum([ri,gi,bi]):
        c -= 1
print(c)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
s = str(input())
r = 0
g = 0
for i in range(n):
  if s[i] == "R":
    r += 1
  elif s[i] == "G":
    g += 1
c = r*g*(n-r-g)
for j in range(1,n-1):
  for i in range(1,min(n-j-1,j)+1):
    if (s[j-i] != s[j]) and (s[j] != s[j+i]) and (s[j+i] != s[j-i]):
      c -= 1
print(c)
### BUGGY CODE ###

n,k = map(int,input().split())
if n%k==0:
    print(0)
else:
    while(n > abs(n-k)):
        if k == 1:
            n=0
            break
        n=abs(n-k)
    print(n)

### FIXED CODE ###

n,k = map(int,input().split())
ans = min(n%k,k-(n%k))
print(ans)
### BUGGY CODE ###

N,M=map(int,input().split())
PS=[input().split() for i in range(M)]
ACzumi=[]
WA_count=[]
for i in range(M):
    if not PS[i][0] in ACzumi:
        if PS[i][1]=="AC":
            ACzumi.append(PS[i][0])
        else:
            WA_count.append(PS[i][0])
yokei=0            
for i in range(len(WA_count)):
    if not WA_count[i] in ACzumi:
        yokei+=1
        
#print(ACzumi)
print(len(ACzumi),len(WA_count)-yokei)

### FIXED CODE ###

N,M=map(int,input().split())
PS=[input().split() for i in range(M)]
ACzumi=set()
WA_count=[]
for i in range(M):
    if not PS[i][0] in ACzumi:
        if PS[i][1]=="AC":
            ACzumi.add(PS[i][0])
        else:
            WA_count.append(PS[i][0])
yokei=0            
for i in range(len(WA_count)):
    if not WA_count[i] in ACzumi:
        yokei+=1
        
#print(ACzumi)
print(len(ACzumi),len(WA_count)-yokei)
### BUGGY CODE ###

N, Ma, Mb = [int(i) for i in input().split()]
medic = [0] * N
for i in range(N):
    medic[i] = [int(i) for i in input().split()]
cost = [[float('inf')] * 401 for _ in range(401)]


def solve(a, b, num, c):
    if num is N:
        return 0
    for i in range(2):
        if i is 0:
            cost[a + medic[num][0]][b + medic[num][1]] = min(cost[a + medic[num][0]][b + medic[num][1]],
                                                             c + medic[num][2])
            solve(a + medic[num][0], b + medic[num][1], num + 1, cost[a + medic[num][0]][b + medic[num][1]])
        else:
            solve(a, b, num + 1, c)

    return 0


solve(0, 0, 0, 0)
ans = float('inf')
for i in range(400 // max(Ma, Mb)):
    ans = min(ans, cost[Ma * i][Mb * i])
if ans > 1000:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

N, Ma, Mb = [int(i) for i in input().split()]
a, b, c = [], [], []
for i in range(N):
    a_, b_, c_ = [int(i) for i in input().split()]
    a.append(a_)
    b.append(b_)
    c.append(c_)
cost = [[float('inf')] * 401 for _ in range(401)]


def solve():
    max_a, max_b = 1, 1
    for num in range(N):
        for ca in range(max_a, -1, -1):
            for cb in range(max_b, -1, -1):
                cost[ca + a[num]][cb + b[num]] = min(cost[ca][cb] + c[num], cost[ca + a[num]][cb + b[num]])
        cost[a[num]][b[num]] = min(cost[a[num]][b[num]], c[num])
        max_a += a[num]
        max_b += b[num]


solve()
ans = float('inf')
most = ans
for i in range(1, 401):
    for n in range(1, 401):
        if i * Mb is n * Ma:
            ans = min(ans, cost[i][n])
if ans is most:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

L,R = list(map(int,input().split()))

min = 20000000

for i in range(L,R):
    for j in range(i+1,R+1):
        if min > (i * j) % 2019 :
            min = (i * j) % 2019
            if min == 0:
                break

print(min)

### FIXED CODE ###

L,R = list(map(int,input().split()))
 
min = 20000000
 
#探索範囲決め
for i in range(L,R+1):
    tmp = i
    if tmp % 2019 == 0:
        break

for i in range(L,tmp+2):
    for j in range(i + 1,tmp+2):
        if min > (i * j) % 2019 and i <= R and j <= R and L <= i:
            min = (i * j) % 2019
            if min == 0:
                break
    if min == 0:
        break
 
print(min)
### BUGGY CODE ###

n, m = [int(v) for v in input().split()]
a, b = [], []
d = {}
for i in range(m):
    ai, bi = [int(v) for v in input().split()]
    a.append(ai)
    b.append(bi)
    d[ai] = d.get(ai, [])
    d[ai].append(bi)
    d[bi] = d.get(bi, [])
    d[bi].append(ai)

r = {}
def trace():
    tasks = [(1, 0)]
    while tasks:
        no, lv = tasks.pop()
        for c in d[no]:
            if c != 1:
                if c not in r or (r[c][1] > lv and r[c][1] != 0):
                    r[c] = (no, lv)
                    tasks.append((c, lv + 1))
trace()

for i in range(2, n):
    if i not in r:
        print('No')
        break
else:
    print('Yes')
    for i in range(2, n +1):
        print(r[i][0])

### FIXED CODE ###

n, m = [int(v) for v in input().split()]
a, b = [], []
d = {}
for i in range(m):
    ai, bi = [int(v) for v in input().split()]
    a.append(ai)
    b.append(bi)
    d[ai] = d.get(ai, [])
    d[ai].append(bi)
    d[bi] = d.get(bi, [])
    d[bi].append(ai)

r = {}
def trace():
    tasks = [(1, 0)]
    i = 0
    while i < len(tasks):
        no, lv = tasks[i]
        for c in d[no]:
            if c != 1:
                if c not in r or (r[c][1] > lv and r[c][1] != 0):
                    r[c] = (no, lv)
                    tasks.append((c, lv + 1))
        i += 1
trace()

for i in range(2, n):
    if i not in r:
        print('No')
        break
else:
    print('Yes')
    for i in range(2, n +1):
        print(r[i][0])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
def dfs(i,we):
    global adj,co,res,vis
    we+=co[i]
    res[i]=we
    for j in adj[i]:
        if vis[j]==0:
            vis[j]=1
            adj[j].remove(i)
            dfs(j,we)
            
    
n,q=map(int,input().split())
adj=[set() for i in range(n)]
for _ in range(n-1):
    a,b=map(int,input().split())
    adj[a-1].add(b-1)
    adj[b-1].add(a-1)
co=[0]*n
for i in range(q):
    a,b=map(int,input().split())
    co[a-1]+=b
res=[0]*n
vis=[0]*n
vis[0]=1
dfs(0,0)
for i in range(n):
    print(res[i],end=" ")
print()



### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
def dfs(i,we,par):
    global adj,co,res
    we+=co[i]
    res[i]=we
    for j in adj[i]:
        if j!=par:
            dfs(j,we,i)
            
input = sys.stdin.readline
n,q=map(int,input().split())
adj=[set() for i in range(n)]
for _ in range(n-1):
    a,b=map(int,input().split())
    adj[a-1].add(b-1)
    adj[b-1].add(a-1)
co=[0]*n
for i in range(q):
    a,b=map(int,input().split())
    co[a-1]+=b
res=[0]*n
dfs(0,0,None)
for i in range(n):
    print(res[i],end=" ")
print()
### BUGGY CODE ###

s = input()
q = int(input())

t = [0] * q
f = [0] * q
c = [""] * q

for i in range(q):
    lis = list(input().split())
    t[i] = int(lis[0])
    if t[i] == 2:
        f[i] = int(lis[1])
        c[i] = lis[2]

idx = 0
while idx < q:
    if t[idx] == 1:
        flip = True
        while idx + 1 < q and t[idx + 1] == 1:
            idx += 1
            flip = not flip
        if flip:
            s = s[::-1]
    else:
        if f[idx] == 1:
            s = c[idx] + s
        else:
            s = s + c[idx]
    idx += 1

print(s)



### FIXED CODE ###

s = input()
q = int(input())

t = [0] * q
f = [0] * q
c = [""] * q

for i in range(q):
    lis = list(input().split())
    t[i] = int(lis[0])
    if t[i] == 2:
        f[i] = int(lis[1])
        c[i] = lis[2]

idx = 0

p = ""
while idx < q:
    if t[idx] == 1:
        s, p = p, s
    else:
        if f[idx] == 1:
            p += c[idx]
        else:
            s += c[idx]
    idx += 1

p = p[::-1]
s = p + s
print(s)