Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n = int(input())
    primes = get_primes_less_than(55556)
    out = []
    num = 0
    for prime in primes:
        if prime%5 == 1:
           out.append(prime)
           num += 1
        if n == num:
            print(*out)
            return

def get_primes_less_than(x):
    ans = []
    if x < 3:
        return ans
    if x == 3:
        ans.append(2)
        return ans
    else:
        for i in range(3, x, 2):
            if all([i%j for j in ans]):
                ans.append(i)
    return ans
        
if __name__ == "__main__":
    main()

Fixed submission:
n = int(input())

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

p_list = primes(55555)
p5_list = [i for i in p_list if i%5 == 1]
out = ' '.join(map(str, p5_list[:n]))
print(out)

Buggy python submission (verdict: Runtime Error):
n = int(input())

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

p_list = primes(55555)
p5_list = [i for i in p_list if i%5 == 1]
out = p5_list[:n]
print(' '.join(out))

Fixed submission:
n = int(input())

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

p_list = primes(55555)
p5_list = [i for i in p_list if i%5 == 1]
out = ' '.join(map(str, p5_list[:n]))
print(out)
Buggy python submission (verdict: Runtime Error):
n, x = map(int, input().split())
m = [int(input()) for _ in range(n)]
a = x - sum(m)
out = a//min(a)
print(out + n)

Fixed submission:
n, x = map(int, input().split())
m = [int(input()) for _ in range(n)]
a = x - sum(m)
out = a//min(m)
print(out + n)
Buggy python submission (verdict: Runtime Error):
n = int(input())
x = list(map(int,input().split()))
y = sorted(x)
x1, x2 = y[n//2-1], y[n//2]
for i, xx in enumerate(x):
    if xx<=x1:
        print(x2)
    else:
        print(x1)


Fixed submission:
a, b, x = map(int, input().split())
if a + b >= x and a <= x:
    print('YES')
else:
    print('NO')

Buggy python submission (verdict: Runtime Error):
n = int(input())
x = list(map(int,input().split()))
y = sorted(x)
x1, x2 = y[n//2-1], y[n//2]
for i, yy in enumerate(y):
    if yy<=x1:
        print(x2)
    else:
        print(x1)


Fixed submission:
a, b, x = map(int, input().split())
if a + b >= x and a <= x:
    print('YES')
else:
    print('NO')

Buggy python submission (verdict: Runtime Error):
n=int(input())
x=map(int,input().split())
y = sorted(x)
x1, x2 = y[n//2-1], y[n//2]
for i in range(n):
    if x[i]<=x1:
        print(x2)
    else:
        print(x1)


Fixed submission:
a, b, x = map(int, input().split())
if a + b >= x and a <= x:
    print('YES')
else:
    print('NO')
Buggy python submission (verdict: Runtime Error):
n=int(input())
y=sorted(list(map(int,input().split())))
x1, x2 = y[n//2-1], y[n//2]
for i in range(n):
    if x[i]<=x1:
        print(x2)
    else:
        print(x1)


Fixed submission:
n=int(input())
x=list(map(int,input().split()))
N=int(n/2)
y=sorted(x)
a=y[N-1]
b=y[N]
for j in range(n):
    if x[j]<=a:
        print(b)
    else:
        print(a)

Buggy python submission (verdict: Runtime Error):
n=int(input())
x=map(int,input().split())
y = sorted(x)
x1, x2 = y[n//2-1], y[n//2]
for i in range(n):
    if x[i]<=x1:
        print(x2)
    else:
        print(x1)


Fixed submission:
n=int(input())
x=list(map(int,input().split()))
N=int(n/2)
y=sorted(x)
a=y[N-1]
b=y[N]
for j in range(n):
    if x[j]<=a:
        print(b)
    else:
        print(a)

Buggy python submission (verdict: Runtime Error):
n=int(input())
x=map(int,input().split())
y = sorted(x)
x1, x2 = y[n//2-1], y[n//2]
for i in range(n):
    if x[i]<=x1:
        print(x2)
    else:
        print(x1)


Fixed submission:
n=int(input())
x=list(map(int,input().split()))
N=int(n/2)
y=sorted(x)
a=y[N-1]
b=y[N]
for j in range(n):
    if x[j]<=a:
        print(b)
    else:
        print(a)

Buggy python submission (verdict: Runtime Error):
n = int(input())
x = sorted(map(int, input().split()))
x1 = x[n/2-1]
x2 = x[n/2]
for i, xx in enumerate(x):
    if xx <= x1:
        print(x2)
    else:
        print(x1)


Fixed submission:
n=int(input())
x=list(map(int,input().split()))
N=int(n/2)
y=sorted(x)
a=y[N-1]
b=y[N]
for j in range(n):
    if x[j]<=a:
        print(b)
    else:
        print(a)

Buggy python submission (verdict: Runtime Error):
n = int(input())
x = sorted(map(int, input().split()))
x1, x2 = x[n//2-1], x[n//2]
for i, xx in enumerate(x):
　if xx <= x1:
　　print(x2)
　else:
　　print(x1)


Fixed submission:
n=int(input())
x=list(map(int,input().split()))
N=int(n/2)
y=sorted(x)
a=y[N-1]
b=y[N]
for j in range(n):
    if x[j]<=a:
        print(b)
    else:
        print(a)

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
n = input()
x = list(map(int, input().split()))
for i, xx in enumerate(x):
    print(int(np.median(x[:i] + x[i+1:])))

Fixed submission:
n=int(input())
x=list(map(int,input().split()))
N=int(n/2)
y=sorted(x)
a=y[N-1]
b=y[N]
for j in range(n):
    if x[j]<=a:
        print(b)
    else:
        print(a)

Buggy python submission (verdict: Runtime Error):
n = input()
x = list(map(int, input().split()))
out = [sorted(x[:i] + x[i+1:])[(len(val)-1)//2] for i, xx in enumerate(x)]
for o in out:
    print(o)

Fixed submission:
n=int(input())
x=list(map(int,input().split()))
N=int(n/2)
y=sorted(x)
a=y[N-1]
b=y[N]
for j in range(n):
    if x[j]<=a:
        print(b)
    else:
        print(a)

Buggy python submission (verdict: Time Limit Exceeded):
n = input()
x = list(map(int, input().split()))
for i, xx in enumerate(x):
    val = sorted(x[:i] + x [i+1:])
    out = val[(len(val)-1)//2]
    print(out)

Fixed submission:
n=int(input())
x=list(map(int,input().split()))
N=int(n/2)
y=sorted(x)
a=y[N-1]
b=y[N]
for j in range(n):
    if x[j]<=a:
        print(b)
    else:
        print(a)
Buggy python submission (verdict: Runtime Error):
n = int(input())
s = [input() for _ in range(n)]
m = int(input())
t = [input() for _ in range(m)]
num = {i:s.count(i) for i in set(s)}
out = [v-max(0,t.count(k)) for k, v in num.items()]
print(max(out,0))

Fixed submission:
n = int(input())
s = [input() for _ in range(n)]
m = int(input())
t = [input() for _ in range(m)]
num = {i:s.count(i) for i in set(s)}
out = [v-max(0,t.count(k)) for k, v in num.items()]
print(max(max(out),0))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int,input().split()))
SUM = 0
for i in range(1,N):
    for j in range(i):
        SUM += A[i]*A[j]
print(SUM % (10**9+7))

Fixed submission:
N = int(input())
A = list(map(int,input().split()))
sumA = sum(A)
SUM = 0
for i in range(1,N):
    sumA -= A[i]
    SUM += A[i]*sumA
print(SUM % (10**9+7))
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = sorted(list( map( int, input().split() ) ), reverse=True)
Alice = 0
Bob = 0
for i in range(0,N,2):
    Alice += A[i]
    Bob += A[i+1]
print(Alice-Bob)

Fixed submission:
N = int(input())
A = sorted(list( map( int, input().split() ) ), reverse=True)
Alice = 0
Bob = 0
for i in range(0,N,2):
    Alice += A[i]
    if i+1 <= N-1:
        Bob += A[i+1]
print(Alice-Bob)
Buggy python submission (verdict: Time Limit Exceeded):
mod = 10**9 + 7

# x ** a をmodで割った余りを、O(log(a))時間で求める。
def power(x, a):
    if a == 0:
        return 1
    elif a == 1:
        return x
    elif a % 2 == 0:
        return power(x, a//2) **2 % mod
    else:
        return power(x, a//2) **2 * x % mod

# xの逆元を求める。フェルマーの小定理より、 x の逆元は x ^ (mod - 2) に等しい。計算時間はO(log(mod))程度。
# https://qiita.com/Yaruki00/items/fd1fc269ff7fe40d09a6
def modinv(x):
    return power(x, mod-2)

def binomial_coefficients(n, k):
    numera = 1  # 分子
    denomi = 1  # 分母

    for i in range(k):
        numera *= n-i
        numera %= mod
        denomi *= i+1
        denomi %= mod
    return numera * modinv(denomi) % mod

def mypow(x, n):
    res = 1
    while n > 0:
        if n & 1 == 1:
            res *= x
        x *= x
        n >>= 1
    return res

ans = 0
N = int(input())
for i in range(1,N):
    for j in range(1,N-i+1):
        ans = ans + ((binomial_coefficients(N, i)%mod)*(binomial_coefficients(N-i, j)%mod)*(mypow(8,N-i-j)%mod))%mod

print(ans)


Fixed submission:
mod = 10**9 + 7

def modpow(x, n):
    res = 1
    while n > 0:
        if n & 1 == 1:
            res = res*x%mod
        x = x*x%mod
        n >>= 1
    return res

N = int(input())
ans = (modpow(10,N)-2*modpow(9,N)+modpow(8,N))%mod

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
As = list(map(int, input().split()))

ans = 0

for i in range(N):
    for j in range(N-i-1):
        ans += As[i]*As[j+i+1]
        if ans >= 10**9+7:
            ans = ans%(10**9+7)

print(ans)


Fixed submission:
N = int(input())
As = list(map(int, input().split()))

sum = 0
for i in range(N):
    sum += As[i]
    sum %= 10**9+7

ans = 0
for i in range(N):
    sum -= As[i]
    ans += As[i]*sum
    ans %= 10**9+7

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
As = list(map(int, input().split()))

ans = 0

for i in range(N):
    for j in range(N-i-1):
        ans += As[i]*As[j+i+1]

print(ans%(10**9+7))


Fixed submission:
N = int(input())
As = list(map(int, input().split()))

sum = 0
for i in range(N):
    sum += As[i]
    sum %= 10**9+7

ans = 0
for i in range(N):
    sum -= As[i]
    ans += As[i]*sum
    ans %= 10**9+7

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
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 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())

nm = list(map(int, input().split()))
n = nm[0]
m = nm[1]

uf = UnionFind(n)
for i in range(m):
    friends = list(map(int, input().split()))
    uf.union(friends[0]-1,friends[1]-1)

uf_list = list(uf.all_group_members().values())

ans = 0

for i in range(len(uf_list)):
    l = len(uf_list[i])
    if ans < l:
        ans = l
print(ans)


Fixed submission:
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 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())
 
nm = list(map(int, input().split()))
n = nm[0]
m = nm[1]
 
ans = 1
 
uf = UnionFind(n)
for i in range(m):
    friends = list(map(int, input().split()))
    uf.union(friends[0]-1,friends[1]-1)
    if ans < uf.size(friends[1]-1):
        ans = uf.size(friends[1]-1)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
sum = 0
while(N > 0):
    sum += N%10
    sum %= 9
    N //= 10
if(sum==0):
    print("Yes")
else:
    print("No")


Fixed submission:
N = int(input())
result = sum(list(map(int, str(N))))
if(result%9==0):
    print("Yes")
else:
    print("No")

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
sum = 0
while(N > 0):
    sum += N%10
    N //= 10
if(sum%9==0):
    print("Yes")
else:
    print("No")


Fixed submission:
N = int(input())
result = sum(list(map(int, str(N))))
if(result%9==0):
    print("Yes")
else:
    print("No")
Buggy python submission (verdict: Runtime Error):
import copy
import math

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

sorted_As = sorted(As,reverse = True)
cut_As = copy.copy(sorted_As)
count_list = [0]*len(sorted_As)

for i in range(K):
    index = cut_As.index(max(cut_As))
    count = count_list[index]
    count_list[index] += 1
    cut_As[index] = sorted_As[index] / (count+2)

'''
for i in range(K):
    count = count_list[0]
    count_list[0] += 1
    cut_As[0] = sorted_As[0] / (count+2)
    cut_As,sorted_As,count_list = (list(x) for x in zip(*sorted(zip(cut_As,sorted_As,count_list),reverse = True)))
'''

print(math.ceil(max(cut_As)))


Fixed submission:
X = int(input())
if X >= 30:
    print("Yes")
else:
    print("No")

Buggy python submission (verdict: Runtime Error):
import copy
import math

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

sorted_As = sorted(As,reverse = True)
cut_As = copy.copy(sorted_As)
count_list = [0]*len(sorted_As)

for i in range(K):
    index = cut_As.index(max(cut_As))
    count = count_list[index]
    count_list[index] += 1
    cut_As[index] = sorted_As[index] / (count+2)

'''
for i in range(K):
    count = count_list[0]
    count_list[0] += 1
    cut_As[0] = sorted_As[0] / (count+2)
    cut_As,sorted_As,count_list = (list(x) for x in zip(*sorted(zip(cut_As,sorted_As,count_list),reverse = True)))
'''

print(math.ceil(max(cut_As)))


Fixed submission:
X = int(input())
if X >= 30:
    print("Yes")
else:
    print("No")
Buggy python submission (verdict: Runtime Error):
N = int(input())
As = list(map(int,input().split()))
Q = int(input())

count_array = [0]*(10**5)
for i in range(N):
    count_array[As[i]] += 1

sum = 0
for i in range(len(As)):
    sum += As[i]

for i in range(Q):
    x,y = map(int,input().split())
    sum += count_array[x]*(y-x)
    print(sum)
    count_array[y] += count_array[x]
    count_array[x] = 0


Fixed submission:
N = int(input())
As = list(map(int,input().split()))
Q = int(input())

count_array = [0]*(10**5+1)
for i in range(N):
    count_array[As[i]] += 1

sum = 0
for i in range(len(As)):
    sum += As[i]

for i in range(Q):
    x,y = map(int,input().split())
    sum += count_array[x]*(y-x)
    print(sum)
    count_array[y] += count_array[x]
    count_array[x] = 0
Buggy python submission (verdict: Time Limit Exceeded):
N  = int(input())
As = list(map(int,input().split()))
array = []
for i in range(31):
    sum = 0
    for j in range(N):
        if As[j]>>i & 1 == 1:
            sum += 1
        if j == N-1 and sum % 2 == 0:
            array.append(0)
        if j == N-1 and sum % 2 == 1:
            array.append(1)
ans_array = []
for j in range(N):
    for i in range(31):
        if array[i] == 1 and As[j]>>i & 1 == 1:
            As[j] &= ~(1<<i)
        elif array[i] == 1:
            As[j] |= 1<<i

print(*As)

Fixed submission:
N  = int(input())
As = list(map(int,input().split()))
array = []
B = 0
for i in range(N):
    B ^= As[i]
ans_array = []
for i in range(N):
    ans_array.append(B^As[i])
print(*ans_array)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
As = list(map(int,input().split()))
As.sort()

import math
def get_prime(search_list):
    prime_list = []
    while len(search_list) != 0:
        head_num = search_list.pop(0)
        if head_num not in search_list:
            prime_list.append(head_num)
        search_list = [num for num in search_list if num % head_num != 0]
    prime_list.extend(search_list)
    return prime_list

print(len(get_prime(As)))


Fixed submission:
N = int(input())
As = list(map(int,input().split()))
As.sort()
M = 1000001
array = [0]*M
for a in As:
    if array[a] != 0:
        array[a] = 2
        continue
    for i in range(a,M,a):
        array[i] += 1

ans = 0
for a in As:
    if array[a] == 1:
        ans += 1
print(ans)
Buggy python submission (verdict: Runtime Error):
import math

def get_prime(number):
    prime_list = []
    search_list = list(range(2,number + 1))
    while search_list[0] <= math.sqrt(number):
        head_num = search_list.pop(0)
        prime_list.append(head_num)
        search_list = [num for num in search_list if num % head_num != 0]
    prime_list.extend(search_list)
    return prime_list

l = get_prime(10**6)
N = int(input())
ans = 0
k = 1
i = 0
while(l[i]**2 <= N):
    if N % (l[i]**k) == 0:
        N //= (l[i]**k)
        k += 1
        ans += 1
    else:
        i += 1
        k = 1
if N != 1 and l[i]!=N:
    ans += 1
print(ans)


Fixed submission:
import math
import random

def is_prime3(q,k=50):
    q = abs(q)
    #計算するまでもなく判定できるものははじく
    if q == 2: return True
    if q < 2 or q&1 == 0: return False

    #n-1=2^s*dとし（但しaは整数、dは奇数)、dを求める
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1

    #判定をk回繰り返す
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        #[0,s-1]の範囲すべてをチェック
        while t != q-1 and y != 1 and y != q-1:
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True

def get_prime(number):
    prime_list = []
    search_list = list(range(2,number + 1))
    while search_list[0] <= math.sqrt(number):
        head_num = search_list.pop(0)
        prime_list.append(head_num)
        search_list = [num for num in search_list if num % head_num != 0]
    prime_list.extend(search_list)
    return prime_list

l = get_prime(10**6+10)
N = int(input())
ans = 0
k = 1
i = 0
l2 = []
while(l[i]**2 <= N):
    if N % (l[i]**k) == 0:
        N //= (l[i]**k)
        l2.append(l[i]**k)
        k += 1
        ans += 1
    else:
        i += 1
        k = 1
index = 0
while(index < len(l2)):
    if N % (l2[index]) == 0:
        N //= l2[index]
    else:
        index += 1
if is_prime3(N) and N not in l2:
    ans += 1
print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
array1 = []
array2 = []
for i in range(N):
    a,b = map(int,input().split())
    array1.append(a)
    array2.append(b)

array1.sort()
array2.sort()

if N % 2 == 0:
    min = array1[N//2]+array1[N//2+1]
    max = array2[N//2]+array2[N//2+1]
    print(max-min+1)
else:
    min = array1[N//2]
    max = array2[N//2]
    print(max-min+1)


Fixed submission:
N = int(input())
array1 = []
array2 = []
for i in range(N):
    a,b = map(int,input().split())
    array1.append(a)
    array2.append(b)

array1.sort()
array2.sort()

if N % 2 == 0:
    min = array1[N//2]+array1[N//2-1]
    max = array2[N//2]+array2[N//2-1]
    print(max-min+1)
else:
    min = array1[N//2]
    max = array2[N//2]
    print(max-min+1)
Buggy python submission (verdict: Runtime Error):
import sys
from collections import deque
sys.setrecursionlimit(10 ** 6)
def input():
    return sys.stdin.readline()[:-1]

def dfs(v,prev = -1):
    for u in graph[v]:
        if u == prev:
            continue
        sign[u] = v
        dfs(u,v)

def bfs(v):
    que = deque([])
    que.append(v)
    while que:
        p = que.popleft()
        if visited[p] == 0:
            visited[p] = 1
            for u in graph[v]:
                que.append(u)

import heapq

def dijkstra(s):
    hq = [(0, s)]
    heapq.heapify(hq) # リストを優先度付きキューに変換
    cost = [float('inf')] * (M+1) # 行ったことのないところはinf
    cost[s] = 0 # 開始地点は0
    while hq:
        c, v = heapq.heappop(hq)
        if c > cost[v]: # コストが現在のコストよりも高ければスルー
            continue
        for u in graph[v]:
            tmp = 1 + cost[v]
            if tmp < cost[u]:
                cost[u] = tmp
                path[u] = v
                heapq.heappush(hq, (tmp, u))
    return path

N,M = map(int,input().split())
graph = [[] for i in range(M+1)]
for i in range(M):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
path = [0]*(N+1)
c = dijkstra(1)
print("Yes")
for i in range(2,N+1):
    print(c[i])


Fixed submission:
import sys
from collections import deque
sys.setrecursionlimit(10 ** 6)
def input():
    return sys.stdin.readline()[:-1]

def dfs(v,prev = -1):
    for u in graph[v]:
        if u == prev:
            continue
        sign[u] = v
        dfs(u,v)

def bfs(v):
    que = deque([])
    que.append(v)
    while que:
        p = que.popleft()
        if visited[p] == 0:
            visited[p] = 1
            for u in graph[v]:
                que.append(u)

import heapq

def dijkstra(s):
    hq = [(0, s)]
    heapq.heapify(hq) # リストを優先度付きキューに変換
    cost = [float('inf')] * (N+1) # 行ったことのないところはinf
    cost[s] = 0 # 開始地点は0
    while hq:
        c, v = heapq.heappop(hq)
        if c > cost[v]: # コストが現在のコストよりも高ければスルー
            continue
        for u in graph[v]:
            tmp = 1 + cost[v]
            if tmp < cost[u]:
                cost[u] = tmp
                path[u] = v
                heapq.heappush(hq, (tmp, u))
    return path

N,M = map(int,input().split())
graph = [[] for i in range(N+1)]
for i in range(M):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
path = [0]*(N+1)
c = dijkstra(1)
print("Yes")
for i in range(2,N+1):
    print(c[i])