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

import sys
readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readints():return list(map(int,readline().split()))

from collections import deque

h,w = readints()

start = readints()
start = (start[0]-1)*w + start[1]-1

goal = readints()
goal = (goal[0]-1)*w + goal[1]-1

maze = [readstr() for i in range(h)]

dist = [10**10]*(h*w)

dq = deque()
dq.append(start)
dist[start] = 0

while dq:
    p = dq.popleft()
    y = p//w
    x = p%w
    for dy in range(-2,3):
        for dx in range(-2,3):
            if 0<=y+dy<h and 0<=x+dx<w and maze[y+dy][x+dx]=='.':
                q = (y+dy)*w + x+dx
                if abs(dy)+abs(dx)==1:
                    if dist[q]>dist[p]:
                        dq.appendleft(q)
                        dist[q] = dist[p]
                else:
                    if dist[q]>dist[p]+1:
                        dq.append(q)
                        dist[q] = dist[p] + 1

print(-1 if dist[goal]==10**10 else dist[goal])


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

import heapq
def dijkstra(s,path):
    # 距離をinfで初期化
    d = [float('inf')]*len(path)
    d[s] = 0

    # sへの距離は0
    q = [(0,s)]
    heapq.heapify(q)

    # 距離が最小の頂点から更新していけば良い
    while q:
        c,p = heapq.heappop(q)

        # 頂点pまでの距離がheap内のpまでの距離より小さい場合、continue
        if d[p]<c:
            continue

        # 頂点pから伸びる、全ての辺の距離を確認
        for to,cost in path[p]:
            # 頂点pから行ける頂点の距離がpまでの距離とpからの距離の和より小さい場合 -> 距離を更新し、heapに追加
            if d[to] > d[p] + cost:
                d[to] = d[p] + cost
                heapq.heappush(q,(d[to], to))
    return d

h,w = readints()

start = readints()
start = (start[0]-1)*w + start[1]-1

goal = readints()
goal = (goal[0]-1)*w + goal[1]-1

maze = [readstr() for i in range(h)]

path = [[] for i in range(h*w)]
for i in range(h*w):
    y = i//w
    x = i%w
    if maze[y][x]=='#':
        continue
    for dy in range(-2,3):
        for dx in range(-2,3):
            if dy==dx==0:
                continue
            if 0<=y+dy<h and 0<=x+dx<w and maze[y+dy][x+dx]=='.':
                j = (y+dy)*w + x+dx
                if (dy==0 and abs(dx)==1) or (abs(dy)==1 and dx==0):
                    path[i].append((j,0))
                else:
                    path[i].append((j,1))

d = dijkstra(start,path)
print(-1 if d[goal]==float('inf') else d[goal])
### BUGGY CODE ###

from fractions import gcd
 
def primeNum(n):
  prime=[1]
  if n % 2 == 0:
    prime.append(2)
    while n % 2 == 0:
      n = n // 2
  for k in range(3, n+1, 2):
    if n % k == 0:
      prime.append(k)
      while n % k == 0:
        n = n // k
    if n == 1:
      return prime
  return prime
 
a,b = list(map(int, input().split()))
n=gcd(a,b)
print(len(primeNum(n)))

### FIXED CODE ###

from fractions import gcd
 
def primeNum(n):
  ans = 1
  if n == 1:
    return ans
  if n % 2 == 0:
    ans += 1
    while n % 2 == 0:
      n = n // 2
  for k in range(3, int(n**0.5)+1, 2):
    if n % k == 0:
      ans += 1
      while n % k == 0:
        n = n // k
    if n == 1:
      return ans
  if n != 1:
    ans += 1
  return ans
  
a,b = list(map(int, input().split()))
n=gcd(a,b)
print(primeNum(n))
### BUGGY CODE ###

def getinputdata():

    array_result = []    
    data = input()
    array_result.append(data.split(" "))

    flg = True

    try:
        while flg:

            data = input()

            if(data != ""):
                
                array_result.append(data.split(" "))

                flg = True

            else:

                flg = False
    finally:

        return array_result

arr_data = getinputdata()

x=arr_data[0][0]

cnt=10**10000

for i in range(cnt):

    if x.find("ST")>=0:
        
        x=x.replace("ST","",1)
        
    else:
        
        break
        
print(len(x))

### FIXED CODE ###

from collections import deque
def getinputdata():

    array_result = []    
    data = input()
    array_result.append(data.split(" "))

    flg = True

    try:
        while flg:

            data = input()

            if(data != ""):
                
                array_result.append(data.split(" "))

                flg = True

            else:

                flg = False
    finally:

        return array_result

arr_data = getinputdata()

x=arr_data[0][0]

b = deque([])

for v in x:
    
    if v=="S":
        
        b.appendleft(v)
        
    elif v=="T" and (len(b)==0 or b[0]=="T"):
        
        b.appendleft(v)
        
    else:
            
        b.popleft()
            
print(len(b))
### BUGGY CODE ###

N = int(input())
S = input()


class RollingHash(object):
    def __init__(self, S, base, mod):
        self.mod = mod
        l = len(S)

        self.hash_lst = [0] * (l + 1)
        self.pow_lst = [1] * (l + 1)

        for i in range(l):
            self.hash_lst[i + 1] = (self.hash_lst[i] * base + ord(S[i])) % mod
            self.pow_lst[i + 1] = (self.pow_lst[i] * base) % mod

    def get_hash(self, left, right):
        return (self.hash_lst[right] - self.hash_lst[left] * self.pow_lst[right - left] % self.mod) % self.mod

base = 1007
mod = pow(10, 9) + 7
rh = RollingHash(S, base, mod)

l = len(S)

res = 0
for i in range(N):
    for j in range(i + 1, N):
        min_len = min(N - j, j - i)

        left = i
        right = i + min_len

        if S[i] == S[j]:
            while left < right:
                mid = (left + right) // 2
                h1 = rh.get_hash(i, mid)
                h2 = rh.get_hash(j, j + (mid - i))

                if h1 == h2:
                    left = mid + 1
                else:
                    right = mid - 1

            res = max(res, left - i)

print(res)


### FIXED CODE ###

class RollingHash(object):
    def __init__(self, S, base, mod):
        self.mod = mod
        l = len(S)

        self.hash_lst = [0] * (l + 1)
        self.pow_lst = [1] * (l + 1)

        for i in range(l):
            self.hash_lst[i + 1] = (self.hash_lst[i] * base + ord(S[i])) % mod
            self.pow_lst[i + 1] = (self.pow_lst[i] * base) % mod

    def get_hash(self, left, right):
        return (self.hash_lst[right] - self.hash_lst[left] * self.pow_lst[right - left] % self.mod) % self.mod


N = int(input())
S = input()

base = 1007
mod = pow(10, 9) + 7
rh = RollingHash(S, base, mod)

left = 0
right = N // 2

while left <= right:
    mid = (left + right) // 2

    found_hash = {}
    found = False
    for i in range(N - mid + 1):
        h = rh.get_hash(i, i + mid)

        if h not in found_hash:
            found_hash[h] = i
        else:
            if found_hash[h] <= i - mid:
                found = True
                break

    if found:
        left = mid + 1
    else:
        right = mid - 1


print(right)
### BUGGY CODE ###

# author:  Taichicchi
# created: 27.09.2020 23:15:22

import sys

N = int(input())

s = [int(input()) for _ in range(N)]

ans = 0

for i in range(2 ** N):
    score = 0
    for j in range(N):
        if (i >> j) & 1:
            score += s[j]

    if score % 10 == 0:
        score = 0

    ans = max(ans, score)


print(ans)


### FIXED CODE ###

# author:  Taichicchi
# created: 27.09.2020 23:15:22

import sys

N = int(input())

s = [int(input()) for _ in range(N)]

ls = []

for i in range(N):
    if s[i] % 10 != 0:
        ls.append(s[i])

ls.sort()

base = sum(s)

if base % 10 != 0:
    print(base)
    exit()

if ls:
    print(base - ls[0])
else:
    print(0)
### BUGGY CODE ###

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * n

  def find(self, x):
    if self.parents[x] < 0:
      return x
    else:
      self.parents[x] = self.find(self.parents[x])
      return self.parents[x]

  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)

    if x == y:
      return

    if self.parents[x] > self.parents[y]:
      x, y = y, x

    self.parents[x] += self.parents[y]
    self.parents[y] = x

  def size(self, x):
    return -self.parents[self.find(x)]

  def same(self, x, y):
    return self.find(x) == self.find(y)

  def members(self, x):
    root = self.find(x)
    return [i for i in range(self.n) if self.find(i) == root]

  def roots(self):
    return [i for i, x in enumerate(self.parents) if x < 0]
    
  def all_group_numbers(self):
    return [-x for x in self.parents if x < -1]

  def group_count(self):
    return len(self.roots())

  def all_group_members(self):
    return {r: self.members(r) for r in self.roots()}

  def __str__(self):
    return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]
uf=UnionFind(N)
ans=[0]*(M+1)
ans[M]=N*(N-1)//2
i=M-1
for a,b in AB[::-1]:
  uf.union(a-1,b-1)
  ans[i]=ans[-1]-sum([x*(x-1)//2 for x in uf.all_group_numbers()])
  i-=1
for a in ans[1:]:
  print(a)

### FIXED CODE ###

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * n

  def find(self, x):
    if self.parents[x] < 0:
      return x
    else:
      self.parents[x] = self.find(self.parents[x])
      return self.parents[x]

  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)

    if x == y:
      return False,0,0

    if self.parents[x] > self.parents[y]:
      x, y = y, x
    nx=self.size(x)
    ny=self.size(y)
    self.parents[x] += self.parents[y]
    self.parents[y] = x
    
    return True,nx,ny

  def size(self, x):
    return -self.parents[self.find(x)]

  def same(self, x, y):
    return self.find(x) == self.find(y)

  def members(self, x):
    root = self.find(x)
    return [i for i in range(self.n) if self.find(i) == root]

  def roots(self):
    return [i for i, x in enumerate(self.parents) if x < 0]
    
  def all_group_numbers(self):
    return [-x for x in self.parents if x < -1]

  def group_count(self):
    return len(self.roots())

  def all_group_members(self):
    return {r: self.members(r) for r in self.roots()}

  def __str__(self):
    return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]
uf=UnionFind(N)
ans=[0]*(M+1)
ans[M]=N*(N-1)//2
i=M-1
for a,b in AB[::-1]:
  flg,na,nb=uf.union(a-1,b-1)
  if flg:
    ans[i]=ans[i+1]-na*nb
  else:
    ans[i]=ans[i+1]
  i-=1
for a in ans[1:]:
  print(a)
### BUGGY CODE ###

import time
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
BC = [list(map(int, input().split())) for _ in range(Q)]

num = {}
for i in A:
    if i in num:
        num[i] += 1
    else:
        num[i] = 1
for i in range(Q):
    p, n = BC[i][0], BC[i][1]
    if p in num:
        if n in num:
            num[n] += num[p]
        else:
            num[n] = num[p]
        num[p] = 0
    ans = 0
    for k, v in num.items(): ans += k * v
    print(ans)

### FIXED CODE ###

import time
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
BC = [list(map(int, input().split())) for _ in range(Q)]

num = [0] * 100010
for i in A:
    num[i] += 1
s = sum(A)

for i in range(Q):
    p, n = BC[i][0], BC[i][1]
    s += (n - p) * num[p]
    num[n] += num[p]
    num[p] = 0
    print(s)
### BUGGY CODE ###

def main():
    n = int(input())
    for i in range(n):
        a = input()
        b = input()
        na=len(a)
        nb=len(b)
        array = [[0]*nb for i in range(na)]
        #array = [[0 for i in range(nb)] for j in range(na)]
        for i in range(na):
            for j in range(nb):
                c = 0
                if i==0:
                    if a[i]==b[j]:
                        array[i][j]=1
                elif j==0:
                    if a[i]==b[j]:
                        array[i][j]=1
                else:
                    if a[i] == b[j]:
                        c = 1
                    array[i][j] = max(
                        array[i-1][j],
                        array[i][j-1],
                        array[i-1][j-1]+c)
        print(array[na-1][nb-1])
if __name__ == "__main__":
    main()



### FIXED CODE ###

#dj 16D8101012J ito jun
import sys
def search(a,b):
    na=len(a)
    nb=len(b)
    array = [[0]*(nb+1) for _ in range(na+1)]
    for i,x in enumerate(a,1):
        prerow=array[i-1]
        row=array[i]
        for j,y in enumerate(b,1):
            if x == y:
                row[j]=prerow[j-1]+1
            elif prerow[j] < row[j-1]:
                row[j] = row[j-1]
            else:
                row[j] = prerow[j]
    return array[-1][-1]

n = int(input())
strs = [list(i) for i in sys.stdin.read().splitlines()]
result = [search(strs[i*2], strs[i*2+1]) for i in range(n)]
print(*result, sep="\n")
### BUGGY CODE ###

_num = int(input())
_sumlist = []
for i in range(_num // 10, _num + 1):
    _sum = 0
    while i:
        _sum += i % 10
        i //= 10
    _sumlist.append(_sum)
print(max(_sumlist))

### FIXED CODE ###

def digit_num(_num):
    _digit = 0
    while _num:
        _digit += 1
        _num //= 10
    return _digit


_num = int(input())
_digit = digit_num(_num)
_topdig = _num // 10 ** (_digit - 1)
_sumlist = [9 * (_digit - 1)]
if (_num - _topdig * 10 ** (_digit - 1)) == 10 ** (_digit - 1) - 1:
    _sumlist.append(_topdig + 9 * (_digit - 1))
else:
    _sumlist.append(_topdig - 1 + 9 * (_digit - 1))

print(max(_sumlist))
### BUGGY CODE ###

import collections
N = int(input())
Aj = list(map(int, input().split()))
Aj_coll = collections.Counter(Aj)
ans = 1
for k, v in Aj_coll.items():
	ans *= k**v
if ans > 10**18:
	ans = -1
print(ans)


### FIXED CODE ###

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

ans = 1
ng = False
max = 10**18
for A in Aj:
	if A == 0:
		ans = 0
		break
	if ng or ans*A > max:
		ans = -1
		ng = True
	else:
		ans *= A
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)


def dfs(p):
    for edge in G[p]:
        if X[edge[0]] is not None:
            if X[edge[0]] - X[p] != edge[1]:
                print('No')
                exit()
        else:
            X[edge[0]] = X[p] + edge[1]
            dfs(edge[0])


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

for i in range(M):
    L, R, D = map(int, input().split())
    L -= 1
    R -= 1
    G[L].append((R, D))
    G[R].append((L, -D))

X = [None] * N
for i in range(N):
    if X[i] is None:
        X[i] = 0
        dfs(i)

print('Yes')


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 5+1)


def dfs(p):
    for edge in G[p]:
        if X[edge[0]] is not None:
            if X[edge[0]] - X[p] != edge[1]:
                print('No')
                exit()
        else:
            X[edge[0]] = X[p] + edge[1]
            dfs(edge[0])


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

for i in range(M):
    L, R, D = map(int, input().split())
    L -= 1
    R -= 1
    G[L].append((R, D))
    G[R].append((L, -D))

X = [None] * N
for i in range(N):
    if X[i] is None:
        X[i] = 0
        dfs(i)

print('Yes')
### BUGGY CODE ###

#!/usr/bin/env python3
#エイシングプログラミングコンテスト2019 C

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


dx,dy = [1,0,-1,0],[0,1,0,-1]
h,w = LI()
s = [input() for _ in range(h)]
que = deque()
ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            que.append((i,j))
while que:
    que2 = deque()
    y,x = que.popleft()
    que2.append((y,x))
    check = [[True]*w for _ in range(h)]
    while que2:
        y,x = que2.popleft()
        for i in range(4):
            nx,ny = x + dx[i], y + dy[i]
            if s[y][x] == '#':
                if 0 <= nx < w and 0 <= ny < h and check[ny][nx]:
                    if s[ny][nx] == '.':
                        ans += 1
                        que2.append((ny,nx))
                    check[ny][nx] = False
            else:
                if 0 <= nx < w and 0 <= ny < h and check[ny][nx]:
                    if s[ny][nx] == '#':
                        que2.append((ny,nx))
                    check[ny][nx] = False
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
#エイシングプログラミングコンテスト2019 C

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


dx,dy = [1,0,-1,0],[0,1,0,-1]
h,w = LI()
s = [input() for _ in range(h)]
que = deque()
ch = [[-1]*w for _ in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            if ch[i][j] < 0:
                ch[i][j] = 0
                que = deque()
                que.append((i,j))
                #a:= ルールを守りながら行ける#の数
                #b:= ルールを守りながら行ける.の数
                a,b = 1,0
                while que:
                    y,x = que.popleft()
                    for k in range(4):
                        nx,ny = x + dx[k], y + dy[k]
                        if 0 <= nx < w and 0 <= ny < h and ch[ny][nx] < 0:
                            if s[y][x] != s[ny][nx]:
                                if s[ny][nx] == '#':
                                    a += 1
                                else:
                                    b += 1
                                ch[ny][nx] = 0
                                que.append((ny,nx))
                ans += a*b
print(ans)
### BUGGY CODE ###

import numpy as np

h, w = map(int, input().split())
a = [input() for _ in range(h)]

a = np.array([[(ai[j] == "#") for j in range(w)] for ai in a])


ans = 0
for _ in range(3000):
    if np.all(a):
        break
    a_new = a.copy()
    a_new[1:] = a_new[1:] + a[:-1]
    a_new[:-1] = a_new[:-1] + a[1:]
    a_new[:, 1:] = a_new[:, 1:] + a[:, :-1]
    a_new[:, :-1] = a_new[:, :-1] + a[:, 1:]
    a = a_new
    ans += 1
print(ans)


### FIXED CODE ###

import numpy as np
from scipy.ndimage.morphology import distance_transform_cdt

h, w = map(int, input().split())
a = [input() for _ in range(h)]

a = np.array([[(ai[j] != "#") for j in range(w)] for ai in a])
d = distance_transform_cdt(a, metric="taxicab").max()
print(d)
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline
 
H, W = map(int, input().split())
#dist_matrix = [[-1] * W for _ in range(H)]
dist_hash = {}
#queue = []
queue = deque()
for i in range(H):
  line = input()
  for j,ch in enumerate(line):
    if ch == "#":
      #dist_matrix[i][j] = 0
      dist_hash[i*W+j] = 0
      queue.append(i*W+j)
 
#cnt = 0
#print(queue)
max_value = 0
while(True):
  #print(len(queue))
  if len(queue) == 0:
    break
  
  ij = queue.popleft()
  i = ij//W
  j = ij%W
  #max_value = dist_matrix[i][j]
  max_value = dist_hash[i*W+j]
  #cnt += 1
  #if i > 0 and dist_matrix[i-1][j] == -1:
  if i > 0 and (i-1)*W+j not in dist_hash:
    #dist_matrix[i-1][j] = max_value + 1
    dist_hash[(i-1)*W+j] = max_value + 1
    queue.append((i-1)*W+j)
  #if i < H-1 and dist_matrix[i+1][j] == -1:
  if i < H-1 and (i+1)*W+j not in dist_hash:
    #dist_matrix[i+1][j] = max_value + 1
    dist_hash[(i+1)*W+j] = max_value + 1
    queue.append((i+1)*W+j)
  #if j > 0 and dist_matrix[i][j-1] == -1:
  if j > 0 and i*W+j-1 not in dist_hash:
    #dist_matrix[i][j-1] = max_value + 1
    dist_hash[i*W+j-1] = max_value + 1
    queue.append(i*W+j-1)
  #if j < W-1 and dist_matrix[i][j+1] == -1:
  if j < W-1 and i*W+j+1 not in dist_hash:
    #dist_matrix[i][j+1] = max_value + 1
    dist_hash[i*W+j+1] = max_value + 1
    queue.append(i*W+j+1)
 
#print(cnt)
#print(dist_matrix)
print(max_value)

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline
 
H, W = map(int, input().split())
mark_matrix = [[True]*(W+2)]
#mark_matrix.extend([[True]+[False]*(W)+[True] for _ in range(H)])
mark_matrix.extend([[True]+[x!='.' for x in input()] for _ in range(H)])
mark_matrix[H].append(True)
mark_matrix.append([True]*(W+2))
#queue = []
queue = deque()
for i in range(1,H+1):
  for j in range(1,W+1):
    if mark_matrix[i][j]:
      queue.append((i,j))
#  line = input()
#  for j,ch in enumerate(line):
#    if ch == "#":
#      mark_matrix[i+1][j+1] = True
#      queue.append((i+1,j+1))
#for i in range(1,H+1):
#  mark_matrix[i][0] = True
#  mark_matrix[i][W+1] = True
#for j in range(W+2):
#  mark_matrix[0][j] = True
#  mark_matrix[H+1][j] = True
#print(mark_matrix)
 
#cnt = 0
#print(queue)
max_value = 0
while(True):
  #print(len(queue))
  if len(queue) == 0:
    break
  
  new_queue = deque()
  for i,j in queue:
  
    if not mark_matrix[i-1][j]:
      mark_matrix[i-1][j] = True
      #queue.append((i-1,j))
      new_queue.append((i-1,j))
    if not mark_matrix[i+1][j]:
      mark_matrix[i+1][j] = True
      #queue.append((i+1,j))
      new_queue.append((i+1,j))
    if not mark_matrix[i][j-1]:
      mark_matrix[i][j-1] = True
      #queue.append((i,j-1))
      new_queue.append((i,j-1))
    if not mark_matrix[i][j+1]:
      mark_matrix[i][j+1] = True
      #queue.append((i,j+1))
      new_queue.append((i,j+1))
 
  if len(new_queue) == 0:
    break
  else:
    queue = new_queue
    max_value += 1
  
#print(cnt)
#print(dist_matrix)
print(max_value)
### BUGGY CODE ###

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

import sys

input = sys.stdin.readline
R = [[]]*n
Sin = [-1]*n
Dis = [-1]*n
Sin[0] = 0
Dis[0] = 0

for _ in range(m):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  R[a] = R[a] + [b]
  R[b] = R[b] + [a]

from collections import deque

d = deque()
d.append(0)

while len(d):
  cur = d.popleft()
  for to in R[cur]:
    if to == Sin[cur] -1:
      continue
    if Dis[to]<0:
      Dis[to] = Dis[cur] + 1
      Sin[to] = cur + 1
      d.append(to)

if min(Sin)<0:
  print('No')
  sys.exit()
print('Yes')
for i in range(1,n):
  print(Sin[i])


### FIXED CODE ###

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

import sys

input = sys.stdin.readline
R = [[] for _ in range(n)]
Sin = [-1]*n
Dis = [-1]*n
Sin[0] = 0
Dis[0] = 0

for _ in range(m):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  R[a].append(b)
  R[b].append(a)

from collections import deque

d = deque()
d.append(0)

while len(d):
  cur = d.popleft()
  for to in R[cur]:
    if Dis[to]<0:
      Dis[to] = Dis[cur] + 1
      Sin[to] = cur + 1
      d.append(to)

if min(Dis)<0:
  print('No')
  sys.exit()
print('Yes')
for i in range(1,n):
  print(Sin[i])
### BUGGY CODE ###

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

for i in range(M):
    price[-1] //= 2
    price.sort()
    
print(sum(price))

### FIXED CODE ###

import heapq

def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)
    
def _heappop_max(heap):
    lastelt = heap.pop()    
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return returnitem
    return lastelt

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

heapq._heapify_max(p)

for i in range(M):
    a = _heappop_max(p)
    a //= 2
    _heappush_max(p, a)

print(sum(p))
### BUGGY CODE ###

n = int(input())
ans = 0
for i in range(n):
    ans += i
print(ans)

### FIXED CODE ###

n = int(input())
print((n*(n-1))//2)