Harryxun/stf_run huggingface dataset:
import heapq

n, k = map(int, input().split())
a = [0] * (n + 1)
typecnt = 0
h = []
heapq.heapify(h)
for _ in range(n):
    t, d = map(int, input().split())
    if a[t] == 0:
        typecnt += 1
        a[t] = 1
    heapq.heappush(h, [-d, t])
ans = 0
mintype = 0
m = []
heapq.heapify(m)
for _ in range(k):
    d, t = heapq.heappop(h)
    if a[t] == 1:
        mintype += 1
        a[t] = 0
    else:
        heapq.heappush(m, -d)
    ans -= d
cnt = ans
ans += mintype * mintype
for j in range(mintype, typecnt):
    bonus = (j + 1) * (j + 1)
    while h:
        d, t = heapq.heappop(h)
        if a[t] == 1:
            a[t] = 0
            l = heapq.heappop(m)
            cnt -= (d + l)
            ans = max(ans, cnt + bonus)
            break
print(ans)

### FIXED CODE ###

import heapq

n, k = map(int, input().split())
a = [0] * (n + 1)
typecnt = 0
h = []
heapq.heapify(h)
for _ in range(n):
    t, d = map(int, input().split())
    if a[t] == 0:
        typecnt += 1
        a[t] = 1
    heapq.heappush(h, [-d, t])
ans = 0
mintype = 0
m = []
heapq.heapify(m)
for _ in range(k):
    d, t = heapq.heappop(h)
    if a[t] == 1:
        mintype += 1
        a[t] = 0
    else:
        heapq.heappush(m, -d)
    ans -= d
cnt = ans
ans += mintype * mintype
for j in range(mintype, typecnt):
    if not m:
        break
    bonus = (j + 1) * (j + 1)
    while h:
        d, t = heapq.heappop(h)
        if not m:
            break
        if a[t] == 1:
            a[t] = 0
            l = heapq.heappop(m)
            cnt -= (d + l)
            ans = max(ans, cnt + bonus)
            break
print(ans)
input_line= input()

if (input_line[2] == input_line[3]) & (input_line[4] == input_line[5]):
  print("Yes")
else:
  pritn("No")

### FIXED CODE ###

S = input()

if (S[2] == S[3]) and (S[4] == S[5]):
    print("Yes")
    
else:
    print("No")
# Surrounded Nodes
from collections import deque
import sys
sys.setrecursionlimit(10**7)
mod = 10**9 + 7
N = int(input())
G = [[] for i in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
S = -1
for i in range(1, N+1):
    if len(G[i]) == 1:
        S = i
        break
visited = [False for i in range(N+1)]
parent = [-1 for i in range(N+1)]
count = [1 for i in range(N+1)]

ans = N*pow(2, N-1, mod)
stack = deque()


def dfs(node):
    visited[node] = True
    for child in G[node]:
        if visited[child] == False:
            parent[child] = node
            stack.append((node, child))
            dfs(child)


dfs(S)
while stack:
    mom, child = stack.pop()
    count[mom] += count[child]
ans = 0
for i in range(1, N+1):
    if len(G[i]) > 1:
        c = 2**(N-1)
        for x in G[i]:
            if x != parent[i]:
                c -= 2**count[x]
        c -= 2**(N-count[i])
        c += len(G[i])-1
        ans += c
D = pow(2, N, mod)
print(c*pow(D, mod-2, mod) % mod)

### FIXED CODE ###

# Surrounded Nodes
from collections import deque
import sys
sys.setrecursionlimit(10**8)
mod = 10**9 + 7
N = int(input())
G = [[] for i in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
S = -1
for i in range(1, N+1):
    if len(G[i]) == 1:
        S = i
        break
visited = [False for i in range(N+1)]
parent = [-1 for i in range(N+1)]
count = [1 for i in range(N+1)]

ans = N*pow(2, N-1, mod)
stack = deque()


def dfs(node):
    visited[node] = True
    for child in G[node]:
        if visited[child] == False:
            parent[child] = node
            stack.append((node, child))
            dfs(child)


powers = [1 for i in range(2*10**5+1)]
for i in range(1, 2*10**5+1):
    powers[i] = powers[i-1]*2 % mod

dfs(S)
while stack:
    mom, child = stack.pop()
    count[mom] += count[child]
ans = 0
for i in range(1, N+1):
    if len(G[i]) > 1:
        ans += powers[N-1]
        for x in G[i]:
            if x != parent[i]:
                ans -= powers[count[x]]
        ans -= powers[N-count[i]]
        ans += len(G[i]) - 1
        ans %= mod
D = pow(2, N, mod)
print(ans*pow(D, mod-2, mod) % mod)
A,B,C = map(str,input().split("/"))
if int(A) <= 2018:
  print("Heisei")
elif int(A) = 2019 and int(B) <=4 and int(C)<=30:
  print("Heisei")
else:
print("TBD")

### FIXED CODE ###

A,B,C = map(str,input().split("/"))
if int(A) <= 2018:
  print("Heisei")
elif int(A) == 2019 and int(B) <=4 and int(C)<=30:
  print("Heisei")
else:
  print("TBD")
n,m=map(int,input().split())
l=[int(i) for i in input().split()]
d=[0]*m 
sm=0 
d[0]=1 
ans=0 
for i in l: 
    sm+=i 
    sm%=m 
    ans+=d[sm]
    d[sm]+=1 
print(ans)

### FIXED CODE ###

from collections import defaultdict
n,m=map(int,input().split())
l=[int(i) for i in input().split()]
d=defaultdict(int)
sm=0 
d[0]=1 
ans=0 
for i in l: 
    sm+=i 
    sm%=m 
    ans+=d[sm]
    d[sm]+=1 
print(ans)
N, K = map(int, input().split())
P = list(map(lambda a: int(a) - 1, input().split()))
C = list(map(int, input().split()))
INF = 10**18

grp = []
visited = [False] * N

for i in range(N):
    if visited[i]:
        continue
    V = []
    while not visited[i]:
        V.append(i)
        visited[i] = True
        i = P[i]
    grp.append(V)

def solve(V, K):
    N = len(V)

    sumC = 0
    for v in V:
        sumC += C[v]

    ans = 0
    if sumC >= 0:
        q, K = divmod(K, N)
        ans = q * sumC
    else:
        K = min(K, N)
        1 / 0

    if K == 0:
        return ans

    def calc(now, K):
        ret = -INF
        acc = 0
        for _ in range(K):
            now = P[now]
            acc += C[now]
            ret = max(ret, acc)
        return ret

    mx = -INF
    for start in V:
        mx = max(mx, calc(start, K))

    return ans + mx

ans = max(C)
for V in grp:
    ans = max(ans, solve(V, K))
print(ans)


### FIXED CODE ###

N, K = map(int, input().split())
P = list(map(lambda a: int(a) - 1, input().split()))
C = list(map(int, input().split()))
INF = 10**18

grp = []
visited = [False] * N

for i in range(N):
    if visited[i]:
        continue
    V = []
    while not visited[i]:
        V.append(i)
        visited[i] = True
        i = P[i]
    grp.append(V)

def solve(V, K):
    N = len(V)
    sumC = 0
    for v in V:
        sumC += C[v]

    ans = 0
    if sumC > 0 and K >= N:
        q, K = divmod(K, N)
        K += N
        ans = sumC * (q - 1)
    else:
        K = min(K, N)

    if K == 0:
        return ans

    def calc(now):
        acc = C[now]
        ret = acc
        for _ in range(K - 1):
            now = P[now]
            acc += C[now]
            ret = max(ret, acc)
        return ret

    mx = -INF
    for start in V:
        mx = max(mx, calc(start))

    return mx + ans

ans = max(C)
for V in grp:
    ans = max(ans, solve(V, K))
print(ans)
V,E,r = map(int, input().split())
edges = []
for _ in range(E):
    tmp = [int(x) for x in input().split()]
    edges.append(tmp)

d = [float('inf') for _ in range(V)]
d[r] = 0

for _ in range(V-1):
    count = 0
    for x in edges:
        s,t,d = x
        if d[t] > d[s] + d:
            count += 1
            d[t] = d[s] + d
    if count == 0:
        break

for x in d:
    if x == float('inf'):
        print('INF')
    else:
        print(x)


### FIXED CODE ###


#Bellman-FordだとTLEになる(はず)
V,E,r = map(int, input().split())
edges = []
for _ in range(E):
    tmp = [int(x) for x in input().split()]
    edges.append(tmp)

d = [float('inf') for _ in range(V)]
d[r] = 0

for _ in range(V-1):
    count = 0
    for x in edges:
        s,t,w = x
        if d[t] > d[s] + w:
            count += 1
            d[t] = d[s] + w
    if count == 0:
        break

for x in d:
    if x == float('inf'):
        print('INF')
    else:
        print(x)
N, K = map(int, input().split())
A_i = list(map(int, input().split()))

place = 1
road = [0 for i in range(N)]
cycle = 0

road[0] = 1

while K != 0:
    place = A_i[place - 1]
    K -= 1

    if road[place - 1] == 1:
        loop_place = place
        break
    road[place - 1] = 1

while K != 0:
    loop_place = A_i[loop_place - 1]
    cycle += 1

    if place == loop_place:
        break

K = K % cycle

while K != 0:
    place = A_i[place - 1]
    K -= 1

print(place)


### FIXED CODE ###

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

place = 1
road = [0 for i in range(N)]
cycle = 0

road[0] = 1

while K != 0:
    place = A_i[place - 1]
    K -= 1
    if road[place - 1] == 1:
        loop_place = place
        break
    road[place - 1] = 1

while K != 0:
    loop_place = A_i[loop_place - 1]
    cycle += 1

    if place == loop_place:
        break

if cycle != 0:
    K = K % cycle

while K != 0:
    place = A_i[place - 1]
    K -= 1

print(place)
import numpy as np
#def replace_RL(RL_str,word):
#    buf = []
#    for s in RL_str:
#        if s == word:
#            buf.append(1)
#        else:
#            buf.append(0)
#    return np.array(buf)

RL_str =np.array(list(input()))
#menber = np.ones(RL_str.size)

R_list = np.where(RL_str=='R',1,0)#replace_RL(RL_str,'R')
L_list = np.where(RL_str=='L',1,0)##replace_RL(RL_str,'L')

for n in range(1000):
    men_R = menber*R_list
    men_L = menber*L_list

    #shift
    men_R = np.roll(men_R, 1)
    men_L = np.roll(men_L, -1)

    menber = men_R + men_L

print(" ".join(menber.astype(int).astype(str).tolist()))

### FIXED CODE ###

import re
RL_list = input()
RL_list = re.findall(r'R*L*',RL_list)
buf = []

for lis in RL_list:
    if len(lis)==2:
        buf.extend([1,1])
    if len(lis)>2:
        r_cnt = lis.count('R')
        l = len(lis) - r_cnt
        if (len(lis) % 2 == 1) & (r_cnt % 2 == 1):
            r = len(lis) // 2 + 1
        #elif (len(lis) % 2 == 1) & (r_cnt % 2 == 0):
        else:
            r = int(len(lis) / 2)
        
        buf.extend([0]*(r_cnt-1))
        buf.extend([r,len(lis)-r])
        buf.extend([0]*(len(lis)-r_cnt-1))
        
print(" ".join(map(str,buf)))
N, M = map(int, input().split())

used = [False] * (N + 1)
ans = []
cur = 1
for i in range(1, M + 1):
    while used[cur]:
        cur += 1
    l = cur
    r = cur + i
    if (r - l) == (N - r + l):
        r += 1
    ans.append((l, r))
    used[cur] = True
    used[l] = True
    used[r] = True
    cur += 1

for l, r in ans:
    print(l, r)

### FIXED CODE ###

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

if N % 2 == 1:
    for i in range(1, M + 1):
        l = i
        r = N - i
        print(l, r)
else:
    flag = False
    l = 1
    r = N - 1
    cnt = 0
    while cnt < M:
        if not flag and r - l <= N // 2:
            r -= 1
            flag = True
        print(l, r)
        l += 1
        r -= 1
        cnt += 1
n = int(input())
links = [[] for _ in range(n)]
colors = [0] * (n - 1)

for i in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    links[a].append((b, i))

def dfs(a, color):
    c = 1
    for b, i in links[a]:
        if c == color:
            c += 1
        colors[i] = c
        dfs(b, c)
        c += 1


dfs(0, 0)
print(max(colors))
for color in colors:
    print(color)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)

n = int(input())
links = [[] for _ in range(n)]
colors = [0] * (n - 1)

for i in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    links[a].append((b, i))

def dfs(a, color):
    c = 1
    for b, i in links[a]:
        if c == color:
            c += 1
        colors[i] = c
        dfs(b, c)
        c += 1


dfs(0, 0)
print(max(colors))
for color in colors:
    print(color)
# -*- coding: utf-8 -*-

def insertionSort(A, n, g):
    global cnt
    for i in range(g, n):
        v = A[i]
        j = i - g
        while j >= 0 and A[j] > v:
            A[j+g] = A[j]
            j -= g
            cnt += 1
        A[j+g] = v


def shellSort(A, n):
    
    def func(m):
        if m == 0:
            return 1
        else:
            return func(m-1)*3 + 1
    
    G = []
    i = 0
    
    while True:
        gi = func(i)
        if gi <= n:
            G.append(gi)
            i += 1
        else:
            break
    
    G = G[::-1]
    for g in G:
        insertionSort(A, n , g)
    
    return A, G


if __name__ == '__main__':

    n = int(input())
    A = [int(input()) for i in range(n)]

    cnt = 0
    A, G = shellSort(A, n)
    
    print(len(G))
    print(" ".join(map(str, G)))
    print(cnt)
    for i in range(n):
        print(A[i])




### FIXED CODE ###

# -*- coding: utf-8 -*-

def insertionSort(A, n, g):
    global cnt
    for i in range(g, n):
        v = A[i]
        j = i - g
        while j >= 0 and A[j] > v:
            A[j+g] = A[j]
            j -= g
            cnt += 1
        A[j+g] = v


def shellSort(A, n):
    
    def func(m):
        if m == 0:
            return 1
        else:
            return func(m-1)*3 + 1
    
    G = []
    i = 0
    
    while True:
        gi = func(i)
        if gi <= n:
            G.append(gi)
            i += 1
        else:
            break
    
    G = G[::-1]
    for g in G:
        insertionSort(A, n , g)
    
    return A, G


if __name__ == '__main__':

    n = int(input())
    A = [int(input()) for i in range(n)]

    cnt = 0
    A, G = shellSort(A, n)
    
    print(len(G))
    print(" ".join(map(str, G)))
    print(cnt)
    for i in range(n):
        print(A[i])
n=int(input())
l=[]
j=0
for i in range(n):
  a=list(map(int,input().split()))
  l.append(a)
for k in range(n-2):
  if l[k+2][0]==l[k+2][1] and l[k+3][0]==l[k+1][1] and l[k+4][0]==l[k+4][1]:
    j+=1
    break
if j==1:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

n=int(input())
l=[]
j=0
for i in range(n):
  a=list(map(int,input().split()))
  l.append(a)
for k in range(n-2):
  if l[k][0]==l[k][1] and l[k+1][0]==l[k+1][1] and l[k+2][0]==l[k+2][1]:
    j+=1
    break
if j==1:
  print('Yes')
else:
  print('No')
S = int(input())

flag = False
ans = 0
for i in range(len(S)):
    if S[i] == 'R':
        ans += 1
        flag = True
    elif S[i] == 'S' ans flag:
        break

print(ans)


### FIXED CODE ###

S = input()

flag = False
ans = 0
for i in range(len(S)):
    if S[i] == 'R':
        ans += 1
        flag = True
    elif S[i] == 'S' and flag:
        break

print(ans)
#input
x,y,z,k=[int(i) for i in input().split()]
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
c=[int(i) for i in input().split()]

#sort
a=sorted(a,reverse=True)
b=sorted(b,reverse=True)
c=sorted(c,reverse=True)

q=[]
heappush(q,(-(a[0]+b[0]+c[0]),0,0,0))
s={(0,0,0)}

for n in range(k):
    p,h,i,j=heappop(q)
    
    if  (h+1<x) and ((h+1,i,j) not in s):
        heappush(q,(-(a[h+1]+b[i]+c[j]),h+1,i,j))
        s.add((h+1,i,j))
        
    if  (i+1<y) and ((h,i+1,j) not in s):
        heappush(q,(-(a[h]+b[i+1]+c[j]),h,i+1,j))
        s.add((h,i+1,j))
        
    if  (j+1<z) and ((h,i,j+1) not in s):
        heappush(q,(-(a[h]+b[i]+c[j+1]),h,i,j+1))        
        s.add((h,i,j+1))
        
    print(-p)
         
for j in range(1,k):
  q_value=q[-1][0]
  q_x=q[-1][1]
  q_y=q[-1][2]
  q_z=q[-1][3]
  new=max(

### FIXED CODE ###

from heapq import heappop, heappush

#input
x,y,z,k=[int(i) for i in input().split()]
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
c=[int(i) for i in input().split()]

#sort
a=sorted(a,reverse=True)
b=sorted(b,reverse=True)
c=sorted(c,reverse=True)

q=[]
heappush(q,(-(a[0]+b[0]+c[0]),0,0,0))
s={(0,0,0)}

for n in range(k):
    p,h,i,j=heappop(q)
    
    if  (h+1<x) and ((h+1,i,j) not in s):
        heappush(q,(-(a[h+1]+b[i]+c[j]),h+1,i,j))
        s.add((h+1,i,j))
        
    if  (i+1<y) and ((h,i+1,j) not in s):
        heappush(q,(-(a[h]+b[i+1]+c[j]),h,i+1,j))
        s.add((h,i+1,j))
        
    if  (j+1<z) and ((h,i,j+1) not in s):
        heappush(q,(-(a[h]+b[i]+c[j+1]),h,i,j+1))        
        s.add((h,i,j+1))
        
    print(-p)
N,M=map(int,input().split())
S=[list(map(int,input().split())) for i in range(M)]
for i in range(M):
    S[i].sort()
    for j in range(2):
        S[i][j]=str(S[i][j])
    S[i]=''.join(S[i])
S=list(set(S))
R=[0]*N
for i in range(N):
    n=i+1
    for j in range(M):
        for k in range(2):
            if S[j][k]==str(n):
                R[i]+=1
for i in range(N):
    print(R[i])


### FIXED CODE ###

N,M=map(int,input().split())
S=[list(map(int,input().split())) for i in range(M)]
c=[0]*N
for i in range(M):
    for j in range(2):
        c[S[i][j]-1]+=1
for i  in range(N):
    print(c[i])
import sys
n = int(input())
s = input()
ans = s
while True:
    visited = [0]*(len(s))
    t = ""
    for i in range(len(s)-1):
        if not visited[i]:
            if s[i:i+2] == "()":
                visited[i+1] = 1
            else:
                t += s[i]
    if not visited[len(s)-1]:
        t += s[-1]
    s = t
    if not s:
        print(ans)
        sys.exit()
    if not "(" in s or not ")" in s:
        break
    for i in range(s.index(")(")+1,len(s)):
        if s[i] != "(":
            break
    else:
        break
print("("*s.count(")")+ans+")"*s.count("("))

### FIXED CODE ###

n = int(input())
s = input()
d = [0]
cnt = 0
for i in range(n):
    if s[i] == "(":
        cnt += 1
    else:
        cnt -= 1
    d.append(cnt)
x = min(d)
print("("*(-x)+s+")"*(d[-1]-x))
N=int(input())
A=list(map(int,input().split()))
Aabs=map(abs,A)

fu=0
for i in range(N):
  if A[i]<0:
    fu+=1
if fu % 2 == 0:
  print(sum(Aabs))
else:
  print(sum(Aabs)-2*min(Aabs))

### FIXED CODE ###

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

fu=0
for i in range(N):
  if A[i]<0:
    fu+=1
if fu % 2 == 0:
  print(sum(Aabs))
else:
  print(sum(Aabs)-2*min(Aabs))
a, b = map( long, input().split() )

if ((a+b)%2==0):
  print( int((a+b)/2) )
else:
  print("IMPOSSIBLE")

### FIXED CODE ###

a, b = map( int, input().split() )

if ((a+b)%2==0):
  cnt = int((a+b)/2)
  print( cnt )
else:
  print("IMPOSSIBLE")
from collections import defaultdict
from operator import sub

def main():
    N = int(input())
    balls = [tuple(map(int,input().split())) for _ in range(N)]
    d = defaultdict(int)
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            d[tuple(map(sub, balls[i], balls[j]))] += 1
    mmax = max(d.values())
    mmax = int(N - mmax)
    try:
        print(mmax)
    except RuntimeError:
        print(100)


if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import defaultdict
from operator import sub

def main():
    N = int(input())
    balls = [tuple(map(int,input().split())) for _ in range(N)]
    d = defaultdict(int)
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            d[tuple(map(sub, balls[i], balls[j]))] += 1
    try:
        mmax = N - max(d.values(), default=0)
        print(mmax)
    except ValueError:
        print(100)

if __name__ == '__main__':
    main()
i = 0

while i == 0:
    x = raw_input()
    a, op, b = x.split()
    a = int(a)
    b = int(b)
    
    if "op" == "+":
        print ("%d" &(a+b))
    elif "op" == "-":
        print ("%d" &(a-b))
    elif "op" == "*":
        print ("%d" &(a*b))
    elif "op" == "/":
        print ("%d" &(a/b))
    elif "op" == "?":
        i == 1

### FIXED CODE ###

i = 1

while i == 1:
    x = raw_input()
    a, op, b = x.split(" ")
    a = int(a)
    b = int(b)
    
    if op == "?":
        i = 0
    elif op == "+":
        print ("%d" %(a+b))
    elif op == "-":
        print ("%d" %(a-b))
    elif op == "*":
        print ("%d" %(a*b))
    else:
        print("%d" %(a/b))
s = input()

i = 0
while i < len(s):
    if(s[i] == 'h' and s[i+1] == 'i'):
        ans = "Yes"
    else:
        ans = "No"
    i += 2

print(ans)

### FIXED CODE ###

s = input()

i = 0

if(len(s) % 2 != 0):
    ans = "No"
else:
    while i < len(s):
        if(s[i] == 'h' and s[i+1] == 'i'):
            ans = "Yes"
        else:
            ans = "No"
            break
        i += 2

print(ans)
import numpy as np
N = int(input())

x = np.empty(N, dtype=np.longlong)
y = np.empty(N, dtype=np.longlong)

for i in range(N):
    x[i], y[i] = (int(t) for t in input().split())

ind = np.argsort(x)
X = x[ind]
Y = y[ind]

# max_dist = [0]
# for i in range(1, N):
#     max_dist.append(np.max(-X[:i] - Y[:i]) + X[i] + Y[i])
#     max_dist.append(np.max(-X[:i] + Y[:i]) + X[i] - Y[i])

# print(max(max_dist))


dist = np.abs(x.reshape([-1, 1]) - x.reshape([1, -1])) + np.abs(y.reshape([-1, 1]) - y.reshape([1, -1]))

print(dist.max())


### FIXED CODE ###

import numpy as np
N = int(input())

x = []
y = []
xy1 = []
xy2 = []

for i in range(N):
    a, b = (int(t) for t in input().split())
    x.append(a)
    y.append(b)
    xy1.append(a + b)
    xy2.append(a - b)

max1 = max(xy1) - min(xy1)
max2 = max(xy2) - min(xy2)
print(max((max1, max2)))
B = int(input())
C = int(input())
D = int(input())

if A <= B:
    densya = A

else:
    densya = B

if C <= D:
    bus = C

else:
    bus = D

untin = densya + bus

print(untin)


### FIXED CODE ###

A = int(input())
B = int(input())
C = int(input())
D = int(input())

if A <= B:
    densya = A

else:
    densya = B

if C <= D:
    bus = C

else:
    bus = D

untin = densya + bus

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

from collections import deque
q = deque([0])
p = [0]*n
while len(q)>0:
  v = q.popleft()
  for i in g[v]:
    if p[i]==0:p[i]=v+1;q.append(i)
if 0 in p: print('No')
else:
  print('Yes')
  for v in p[1:]:print(v)

### FIXED CODE ###

f=lambda:map(int,input().split())
n,m=f()
g=[[] for _ in range(n)]
for _ in range(m):
  a,b=f()
  g[a-1]+=[b-1]
  g[b-1]+=[a-1]
p=[0]*n
from collections import*
q=deque([0])
while q:
  v=q.popleft()
  for c in g[v]:
    if p[c]<1: p[c]=v+1; q.append(c)
if 0 in p: print('No')
else: print('Yes',*p[1:],sep='\n')
N, M = map(int, input().split())
A = list(map(int,input().split()))
B = 0
for i in A:
  if(A[i] >= 1/(4*M)):
    B += 1
if(B >= M):
  print('Yes')
else:
  print('No')

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int,input().split()))
B = 0
for i in range(N):
  if(A[i] >= sum(A)/(4*M)):
    B += 1
if(B >= M):
  print('Yes')
else:
  print('No')
d,g=map(int,input().split())
g//=100
l=[]
ans=1000
for i in range(d):
  p,c=map(int,input().split())
  l+=[[p,c,i*p,i*p+c]]
#dp[c][i]
dp=[0for i in range(2**d-1)]
for i in range(2**d-1):
  a=1
  b,c=i,0
  d=0
  while b:
    if b%2>0:
      dp[i]+=l[c][3]
      d+=l[c][0]
    else:
      a=c+1
    b//=2
    c+=1
  if dp[i]>=g:
    ans=min(ans,d)
  elif dp[i]+l[a][2]>=g:
    ans=min(ans,d+(g-dp[i])//a+((g-dp[i])%a))
print(ans)
      


### FIXED CODE ###

d,g=map(int,input().split())
g//=100
l=[]
ans=1000
for i in range(1,d+1):
  p,c=map(int,input().split())
  c//=100
  l+=[[p,c,i*p,i*p+c]]
for i in range(2**d):
  score=0
  a=0
  b=1
  c=0
  if not i:
    b=d
  while i:
    if i%2>0:
      score+=l[a][3]
      c+=l[a][0]
    else:
      b=a+1
    a+=1
    i//=2
  if score>=g:
    ans=min(ans,c)
  elif score+l[b-1][2]>=g:
    ans=min(ans,c+(g-score)//b+((g-score)%b>0))
print(ans)
r, D, x = map(int, input().split())

for i in range(10) :
  x = rx + D
  print(x)

### FIXED CODE ###

r, D, x = map(int, input().split())

for i in range(10) :
  x = r*x - D
  print(x)
import sys
n = int(input())
a = list(map(int, input().split()))

total = 1
a.sort()
if a[0] == 0:
	print(0)
	sys.exit(1)
for i in range(n):
	total *= a[i]
	if total > 10**18:
		print('-1')
		sys.exit(1)
print(total)
	

### FIXED CODE ###

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

total = 1
a.sort()
if a[0] == 0:
	print(0)
	sys.exit()
for i in range(n):
	total *= a[i]
	if total > 10**18:
		print('-1')
		sys.exit()
print(total)
import math

N,X = map(int,input().split())
x = list(map(int,input().split()))
distance = []

for i in x:
    distance.append(abs(i-X))

while True:
    if len(distance) > 1:
        cd = math.gcd(distance[0],distance[1])
        del distance[0]
        del distance[0]
        distance.append(cd)
        if len(distance) == 1:
            print(distance[0])
            exit()
    else:
        print(distance[0])
        break


### FIXED CODE ###

from functools import reduce
import fractions

N, X = map(int,input().split())
x = list(map(int,input().split()))
x = list(map(lambda x:abs(x-X), x))
x = reduce(lambda a,b: fractions.gcd(a,b), x)
print(x)