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

def check(bag, mtx):
    shojiki = set()
    not_shojiki = set()
    for i in range(len(bag)):
        if bag[i] == 1:
            shojiki.add(i)
    shojiki_list = list(shojiki)
 
    while True:
        if shojiki_list == []:
            break
        i = shojiki_list.pop()
        for j in range(len(mtx[i])):
            if mtx[i][j] == 0 and j in shojiki:
                return False
            if mtx[i][j] == 1:
                if j in not_shojiki:
                    return False
                if j not in shojiki:
                    shojiki_list.append(j)
                    shojiki.add(j)
            if mtx[i][j] == 0:
                not_shojiki.add(j)
    return True
 
 
n = int(input())
 
mtx = [[-1] * n for i in range(n)]
 
for i in range(n):
    a = int(input())
    for j in range(a):
        x, y = map(int, input().split())
        mtx[i][x-1] = y
 
ret = 0
 
for i in range(2 ** n):
    bag = []
    for j in range(n):
        if ((i >> j) & 1):
            bag.append(1)
        else:
            bag.append(0)
    if check(bag, mtx):
        if ret < sum(bag):
            ret = sum(bag)
 
print(ret)


### FIXED CODE ###

def check(bag, mtx):
    shojiki = set()
    not_shojiki = set()
    for i in range(len(bag)):
        if bag[i] == 1:
            shojiki.add(i)
    shojiki_list = list(shojiki)
 
    while True:
        if shojiki_list == []:
            break
        i = shojiki_list.pop()
        for j in range(len(mtx[i])):
            if mtx[i][j] == 0 and j in shojiki:
                return False
            if mtx[i][j] == 1:
                if j in not_shojiki:
                    return False
                if j not in shojiki:
                    shojiki_list.append(j)
                    shojiki.add(j)
            if mtx[i][j] == 0:
                not_shojiki.add(j)
    return True
 
 
n = int(input())
 
mtx = [[-1] * n for i in range(n)]
 
for i in range(n):
    a = int(input())
    for j in range(a):
        x, y = map(int, input().split())
        mtx[i][x-1] = y
 
ret = 0
 
for i in range(2 ** n):
    bag = []
    for j in range(n):
        if ((i >> j) & 1):
            bag.append(1)
        else:
            bag.append(0)
    if check(bag, mtx):
        if ret < sum(bag):
            ret = sum(bag)
 
print(ret)
### BUGGY CODE ###

LARGE = 10**9 + 7


def p_inv(k, p):
    return pow(k, p-2, p)


def nck_mod(n, k, m):
    res = 1
    for i in range(n, n-k, -1):
        res = res * i % m
    for i in range(1, k+1):
        res = res * p_inv(i, m) % m
    return res


def solve(n, m, k):
    res_1 = 0
    for i in range(n):
        for j in range(n):
            res_1 += abs(i - j)
    res_2 = 0
    for i in range(m):
        for j in range(m):
            res_2 += abs(i - j)
    res = (res_1 * m * m + res_2 * n * n) % LARGE

    weight = nck_mod(n * m - 1, k - 1, LARGE) * p_inv(n * m - 1, LARGE) * (k - 1) * p_inv(2, LARGE) % LARGE

    return res * weight % LARGE


if __name__ == "__main__":
    N, M, K = map(int, input().split())
    print(solve(N, M, K))
    # print(solve(2, 2, 2))
    # print(solve(4, 5, 4))
    # print(solve(100, 100, 5000))


### FIXED CODE ###

LARGE = 10**9 + 7


def p_inv(k, p):
    return pow(k, p-2, p)


def nck_mod(n, k, m):
    res = 1
    for i in range(n, n-k, -1):
        res = res * i % m
    for i in range(1, k+1):
        res = res * p_inv(i, m) % m
    return res


def solve(n, m, k):
    res_1 = 0
    r = n * (n - 1) // 2
    res_1 += r
    for i in range(1, n):
        r += i
        r -= n - i
        res_1 += r
    res_2 = 0
    r = m * (m - 1) // 2
    res_2 += r
    for i in range(1, m):
        r += i
        r -= m - i
        res_2 += r
    res = (res_1 * m * m + res_2 * n * n) % LARGE

    weight = nck_mod(n * m - 1, k - 1, LARGE) * p_inv(n * m - 1, LARGE) * (k - 1) * p_inv(2, LARGE) % LARGE

    return res * weight % LARGE


if __name__ == "__main__":
    N, M, K = map(int, input().split())
    print(solve(N, M, K))
    # print(solve(2, 2, 2))
    # print(solve(4, 5, 4))
    # print(solve(100, 100, 5000))
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    n,k = map(int, input().split())
    a = list(map(int, input().split()))
    db = [a]
    cnt = 1
    while 2**cnt <= k:
        temp = [0]*n
        for i in range(n):
            temp[i] = db[cnt-1][db[cnt-1][i]-1]
        db.append(temp)
        cnt += 1

    res = 1
    for i in range(cnt):
        if (k>>i) & 1:
            res = db[i][res-1]
    print(res)

if __name__ == '__main__':
    main()

### FIXED CODE ###

#0や1のケースに注意
#index out of range

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    n,k = map(int, input().split())
    a = list(map(int, input().split()))
    tugi = [0]*n
    tugi[0] = 1
    s = 0
    cnt = 1
    while 1:
        s = a[s] - 1
        cnt += 1
        if tugi[s] > 0:
            break
        tugi[s] = cnt
    cnt -= 1
    if cnt-1 >= k:
        for i in range(n):
            if tugi[i]==k+1:
                print(i+1)
    else:
        #s=ループスタート
        loop = [s]
        for i in range(cnt - (tugi[s]-1)-1):
            s = a[s] - 1
            loop.append(s)
        s = a[s]-1
        amari = (k-(tugi[s]-1)) % (len(loop))
        print(loop[amari]+1)

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


n,k=map(int,input().split())
x=[int(x) for x in input().split()]
ans=[1]*n
ans[0]=x[0]
for i in range(1,k):
  ans[i]=ans[i-1]*x[i]
c=0
for i in range(k,n):
  if x[c]<x[i]:
    print('Yes')
  else:print('No')
  c+=1


### FIXED CODE ###


n,k=map(int,input().split())
x=[int(x) for x in input().split()]
ans=[1]*n
ans[0]=x[0]
c=0
for i in range(k,n):

  if x[c]<x[i]:
    print('Yes')
  else:print('No')
  c+=1
### BUGGY CODE ###

import re
s = input()

while s != "":
  if len(s) < 5:
    print('NO')
    exit()
  if s.endswith('dream'):
    s = re.sub("dream$", "", s)
  elif s.endswith('dreamer'):
    s = re.sub("dreamer$", "", s)
  elif s.endswith('erase'):
    s = re.sub("erase$", "", s)
  elif s.endswith('eraser'):
    s = re.sub("eraser$", "", s)
  else:
    print('NO')
    exit()
  
print('YES')

### FIXED CODE ###

import re
s = input()

s = s.replace("eraser", "").replace("erase","")\
	.replace("dreamer", "").replace("dream","")

print('NO' if s else 'YES')
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
M = max(a)+1
t=[True]*M
a.sort()
s=set(a)
for i in a:
    if t[i] == 0:
        continue
    if a.count(i)>1:
        t[i] = False
    for j in range(2*i,M,i):
        t[j] = False
ans = 0
for k in a:
    if t[k] == True:
        ans += 1

print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
M = max(a)+1
t=[True]*M
a.sort()
s=set(a)
pre = 0
for i in a:
    if t[i] == 0:
        continue
    if pre == i:
        t[i] = False
    for j in range(2*i,M,i):
        t[j] = False
    pre = i
ans = 0
for k in a:
    if t[k] == True:
        ans += 1

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

N = int(input())
X = [int(x) for x in input().split(' ')]

for i in range(N):
    tmp = X.copy()
    tmp.pop(i)
    tmp.sort()
    print(tmp[int((N-1)/2)])

### FIXED CODE ###

N = int(input())
x = [int(x) for x in input().split()]
y = sorted(x)
l = y[len(x)//2-1]
r = y[len(x)//2]

for xi in x:
    if xi < r: print(r)
    else: print(l)
### BUGGY CODE ###

import numpy as np

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

mat = np.zeros((n, n), dtype=np.uint32)

for i in range(m):
    l, r = map(int, input().split())
    mat[l-1, r-1] += 1
mat = np.flipud(mat)
matmul = np.cumsum(mat, axis=0)
matmul = np.flipud(matmul)
matmul2 = np.cumsum(matmul, axis=1)

for i in range(q):
    p, q = map(int, input().split())
    ans = matmul2[p-1, q-1]
    print(ans)

### FIXED CODE ###

import numpy as np

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

mat = np.zeros((n, n), dtype=int)

for i in range(m):
    l, r = map(int, input().split())
    mat[l-1, r-1] += 1
mat = np.flipud(mat)
matmul = np.cumsum(mat, axis=0)
matmul = np.flipud(matmul)
matmul2 = np.cumsum(matmul, axis=1)

for i in range(q):
    p, q = map(int, input().split())
    ans = matmul2[p-1, q-1]
    print(ans)
### BUGGY CODE ###

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

def gcd(x, y):
    g = x % y
    if g == 0:
        return y
    return gcd(y, g)

sw = 0
for i in range(N):
    w = A[0 if i != 0 else 1]
    for j in range(N):
        if j != i:
            w = gcd(w, A[j])
    sw = max(sw, w)

print(sw)


### FIXED CODE ###

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

def gcd(x, y):
    if x == 0 or y == 0:
        return max(x, y)
    g = x % y
    if g == 0:
        return y
    return gcd(y, g)

R = [0] * N
R[N-1] = w = 0
for i in range(N-2, -1, -1):
    R[i] = w = gcd(w, A[i+1])

L = [0] * N
L[0] = w = 0
for i in range(1, N):
    L[i] = w = gcd(w, A[i-1])

w = 1
for i in range(N):
    w = max(w, gcd(L[i], R[i]))

print(w)
### BUGGY CODE ###

import sys,random
input = sys.stdin.readline


def main():
    n = int(input())
    
    a = list(map(int,input().split()))
    b = list(map(int,input().split()))

    for k in range(n):
        hyp = b[0]^a[k]
        judge = True
        for _ in [0]*100:
            w = random.randrange(n)
            if b[w] != a[(w+k)%n]^hyp:
                judge = False
                break
        if judge:
            print(k,hyp)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

#Z[i]:length of the longest list starting from S[i] which is also a prefix of S
def Z_algorithm(s):
    N = len(s)
    Z_alg = [0]*N

    Z_alg[0] = N
    i = 1
    j = 0
    while i < N:
        while i+j < N and s[j] == s[i+j]:
            j += 1
        Z_alg[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < N and k + Z_alg[k]<j:
            Z_alg[i+k] = Z_alg[k]
            k += 1
        i += k
        j -= k
    return Z_alg


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


BAA = []
for i in range(n-1):
    BAA.append(b[i]^b[i+1])
BAA.append(b[0]^b[-1])

BAA.append(-1)

for i in range(n-1):
    BAA.append(a[i]^a[i+1])
BAA.append(a[0]^a[-1])
for i in range(n-1):
    BAA.append(a[i]^a[i+1])
BAA.append(a[0]^a[-1])

z = Z_algorithm(BAA)

for k in range(n):
    if z[n+k+1] >= n:
        print(k,b[0]^a[k])
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
c=0
def isfactors(n):
	for i in range(1,n//2+1):
		if n%i==0 and i in l:
			return False
	return True
for i in l:
	if l.count(i)==1 and isfactors(i):
		c+=1
print(c)

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
c=0
d={}
f=[0]*(max(l)+1)
for i in l:
	if i in d:
		d[i]+=1
	else:
		d[i]=1
x=sorted(list(set(l)))
for i in x:
	if d[i]==1 and f[i]==0:
		c+=1
	for j in range(2*i,len(f),i):
		f[j]=1 

print(c)
### BUGGY CODE ###

def gcd(x, y):
    x = x % y
    if x == 0:
        return y
    return gcd(y, x)

def lcm(x, y):
    return x // gcd(x, y) * y
n = int(input())
a = list(map(int, input().split(' ')))
l = 1
for ai in a:
    l = lcm(l, ai)
mod = 1000000007
ans = 0
for ai in a:
    ans += l // ai
ans %= mod
print(ans)


### FIXED CODE ###

def gcd(x, y):
    x = x % y
    if x == 0:
        return y
    return gcd(y, x)

def lcm(x, y):
    return x // gcd(x, y) * y
n = int(input())
a = list(map(int, input().split(' ')))
l = 1
for ai in a:
    l = lcm(l, ai)
mod = 1000000007
ans = 0
for ai in a:
    ans += l // ai
ans %= mod
print(ans)
### BUGGY CODE ###

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

total = 0
for i in range(N):
    for j in range(i+1,N):
        if A[i] == A[j]:
            total += 1


for i in range(N):
    tmp = 0
    to = total
    for j in range(N):
        if i != j and A[i] == A[j]:
            tmp += 1
    
    print(to-tmp)


### FIXED CODE ###

import math
 
def permutations_count(n, r):
    if r == 2:
        return int( (n*(n-1) ) / r )
    if r == 1:
        return n
 
 
N = int(input())
A = list(map(int,input().split()))
 
data = [0] * (N+1)
 
for i in range(N):
    data[A[i]] += 1
 
total = 0
 
for i in range(N+1):
    if data[i] >= 2:
        total += permutations_count(data[i],2)
 
 
 
for i in range(N):
    if data[A[i]] - 1 > 0 :
        print( total - permutations_count(data[A[i]]-1,1) )
    else:
        print(total)
### BUGGY CODE ###

from collections import deque
N = int(input())
A = list(map(int, input().split()))

j = 0
ans = deque()
while j <= N - 1:
    stock = deque()
    for i in range(N):
        # iとjが同じとき
        if (i == j):
            continue

        if (A[j] % A[i] != 0):
            stock.append(A[i])

    if (len(stock) == len(A) - 1):
        ans.append(j)
    j += 1

print(len(ans))


### FIXED CODE ###

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

table = [0 for i in range(10**6 + 1)]
ans = 0
a.sort()
a.append(10**7)
for i in range(n):
    el = a[i]
    if table[el] != 0:
        continue
    else:
        if el != a[i + 1]:
            ans += 1
    idx = el
    while idx <= 10**6:
        table[idx] += 1
        idx += el

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

n = int(input())
a = list(map(int, input().split()))
count = []
for x in a:
  tmp = 0
  for i in a:
    if x == i or abs(x - i) == 1:
      tmp += 1
  count.append(tmp)
print(max(count))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
count = {}
for i in a:
  for j in [-1, 0, 1]:
    count.setdefault(i+j, 0)
    count[i+j] += 1
  
print(max(count.values()))
### BUGGY CODE ###

n=int(input())
a=[0]*(n-1)
a=list(map(int,input().split()))
 
for i in range(n):
    print(a.count(i+1))

### FIXED CODE ###

n=int(input())
a=[0]*(n-1)
a=list(map(int,input().split()))
a=sorted(a)
ans=0
target=1
j=0
for i in range(n):
    if (j<n-1):
        while(a[j]==target):
            ans+=1
            j+=1
            #print(j,"here")
            if (j>n-2):
                break
    print(ans)
    ans=0
    target+=1
### BUGGY CODE ###

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

for i in range(n):
  ans = max(a)
  if a[i] == ans:
    temp = ans
    a.remove(ans)
    ans = max(a)
    a.insert(i, temp)
  print(ans)



### FIXED CODE ###

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

sorted_a = sorted(a)
max_a = sorted_a[-1]
max_a_r = sorted_a[-2]

for i in range(n):
  if a[i] == max_a:
    print(max_a_r)
  else:
    print(max_a)
### BUGGY CODE ###

N, W = map(int,input().split())
dp = [-1 for i in range(W+1)]
dp[0] = 0

for _ in range(N):
    w, v = map(int, input().split())
    for i in range(0, W-w+1):
        j = W-w-i
        if dp[j] >= 0:
            dp[j+w] = max(dp[j+w], dp[j]+v)
print(max(dp))


### FIXED CODE ###

N, W = map(int,input().split())
V = [[] for _ in range(4)]

w, v = map(int,input().split())
w0 = w
V[0].append(v)

for _ in range(N-1):
    w, v = map(int,input().split())
    V[w-w0].append(v)
for i in range(4):
    V[i].sort(reverse=True)
    for j in range(1,len(V[i])):
        V[i][j] = V[i][j-1]+V[i][j]
    V[i].insert(0,0)
    V[i].append(0)

ans = 0
for i in range(len(V[0])):
    wi = w0*i
    if wi > W:
        break
    vi = V[0][i]
    for j in range(len(V[1])):
        wj = wi + (w0+1)*j
        if wj > W:
            break
        vj = vi + V[1][j]
        for k in range(len(V[2])):
            wk = wj + (w0+2)*k
            if wk > W:
                break
            vk = vj + V[2][k]

            l = min((W-wk)//(w0+3), len(V[3])-1)
            v = vk + V[3][l]
            ans = max(ans, v)
print(ans)
### BUGGY CODE ###

A,B,C,D=map(int, input().split())
List=[0 if (i%C==0 or i%D==0) else 1 for i in range(A,B+1)]
print(sum(List))


### FIXED CODE ###

import fractions

A,B,C,D = map(int, input().split())

def lcm(C,D):
  return C*D // fractions.gcd(C,D)
CD=lcm(C,D)

print(int(B-A+1-((B//C + B//D - B//CD) - ((A-1)//C + (A-1)//D - (A-1)//CD))))
### BUGGY CODE ###

from operator import itemgetter
from bisect import bisect,bisect_left,insort

def solve(n, ppp):
    q = sorted(enumerate(ppp),key=itemgetter(1),reverse=True)
    left = [-1,-1]
    right = [n,n]
    ans = 0
    for i, p in q:
        l_i = bisect(left,i)
        r_i = bisect_left(right,i)
        LL = left[l_i-2]
        LR = left[l_i-1]
        RL = right[r_i]
        RR = right[r_i+1]
        ans += p*((LR-LL)*(RL-i)+(RR-RL)*(i-LR))
        insort(left,i)
        insort(right,i)
    return ans


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

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from operator import itemgetter

n = int(readline())
ppp = list(map(int,readline().split()))

def BIT_add(i,x):
    while i <= n:
        tree[i] += x
        i += i&(-i)

def BIT_sum(i):
    s = 0
    while i:
        s += tree[i]
        i -= i&(-i)
    return s

def BIT_search(x):
    # 二分探索。和がx以上となる最小のインデックス(>= 1)を返す
      i = 0
      s = 0
      step = 1<<(n.bit_length()-1)
      while step:
          if i+step <= n and s + tree[i+step] < x:
              i += step
              s += tree[i]
          step >>= 1
      return i+1

q = sorted(enumerate(ppp,1),key=itemgetter(1),reverse=True)
tree = [0]*(n+1)

ans = 0
for i, p in q:
    L = BIT_sum(i) # 左にある既に書き込んだ数の個数
    BIT_add(i,1)
    R = n-p-L # 右にある既に書き込んだ数の個数
    LL = BIT_search(L-1) if L >= 2 else 0
    LR = BIT_search(L) if L >= 1 else 0
    RL = BIT_search(L+2) if R >= 1 else n+1
    RR = BIT_search(L+3) if R >= 2 else n+1
    ans += p*((LR-LL)*(RL-i)+(RR-RL)*(i-LR))
print(ans)
### BUGGY CODE ###

import itertools
import heapq
import sys
import functools
import operator
input = sys.stdin.readline
#-------------
n,k = map(int,input().split())
a = list(map(int,input().split()))
#-------------
comb = itertools.combinations(a,k)  
l = [list(_) for _ in comb]  
A = [functools.reduce(operator.mul,l[i]) for i in range(len(l))] 
l_max = max(A)
waru = 10**9 + 7
print(l_max % waru)

### FIXED CODE ###

import sys
 
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
mod = pow(10, 9)+7
zero = 0
plus = []
minus = []
for i in range(n):
  if a[i] == 0:
    zero += 1
  elif a[i] > 0:
    plus.append(a[i])
  else:
    minus.append(a[i])
 
P, M = len(plus), len(minus)
plus.sort(reverse=True)
minus.sort()
ans = 1
if n == k:
  for i in range(n):
    ans *= a[i]
    ans %= mod
elif P+M < k:
  ans = 0
elif P == 0:
  if zero and k%2:
    ans = 0
  else:
    if k%2:
      minus.reverse()
    for i in range(k):
      ans *= minus[i]
      ans %= mod
else:
  q = 0
  if k%2:
    ans *= plus[0]
    ans %= mod
    q = 1
  judge = []
  for i in range((len(plus)-q)//2):
    judge.append(plus[2*i+q]*plus[2*i+q+1])
  for i in range(len(minus)//2):
    judge.append(minus[2*i]*minus[2*i+1])
  judge.sort(reverse=True)
  for i in range(k//2):
    ans *= (judge[i]%mod)
    ans %= mod
 
print(ans)
### BUGGY CODE ###

N,K,Q = map(int,input().split())
A = [int(input()) for i in range(Q)]
B = [K]*N
p = 0
for i in range(N+1):
    A.append(i+1)
C = sorted(A)
for i in range(N):
    B[i] += C.index(i+2) - p - 1
    p = C.index(i+2)
for i in range(N):
    if(B[i] > Q):
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

import bisect as bi

N,K,Q = map(int,input().split())
A = [int(input()) for i in range(Q)]
B = [K]*N
p = 0
for i in range(N+1):
    A.append(i+1)
C = sorted(A)
for i in range(N):
    B[i] += bi.bisect_left(C,i+2) - p - 1
    p = bi.bisect_left(C,i+2)
for i in range(N):
    if(B[i] > Q):
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

from collections import deque
def main():
    N,M = map(int,input().split())
    G = [deque([]) for _ in range(N)]
    for _ in range(M):
        a,b = map(int,input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)

    arrive_time = [-1] * (N + 1)
    stack = deque([0])
    arrive_time[0] = 1
    sign = [0] * N
    while stack:
        v = stack.popleft()
        if G[v]:
            for w in G[v]:
                if arrive_time[w] < 0 and not w  in stack:
                    arrive_time[w] = 1
                    sign[w] = v+1
                    stack.append(w)       
    
    sign = sign[1:]
    if all(s > 0 for s in sign):
        print('Yes')
        for s in sign:
            print(s)
    else:
        print('No')
        
main()

### FIXED CODE ###

from collections import deque
def main():
    N,M = map(int,input().split())
    G = [deque([]) for _ in range(N)]
    for _ in range(M):
        a,b = map(int,input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)

    stack = deque([0])
    sign = [0] * N
    while stack:
        v = stack.popleft()
        for w in G[v]:
            if sign[w] == 0:
                sign[w] = v+1
                stack.append(w)   

    sign = sign[1:]
    if all(s > 0 for s in sign):
        print('Yes')
        for s in sign:
            print(s)
    else:
        print('No')
        
main()
### BUGGY CODE ###

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

banned_list = []*M
for i in range(M):
    banned_list.append(tuple(map(int,input().split())))

banned_list = sorted(banned_list,key=lambda x:x[1])
status = [1 for _ in range(N-1)]
counter = 0
for i in range(M):
    a = banned_list[i][0]
    b = banned_list[i][1]
    if sum(status[a-1:b-1]) ==  b-a:
        counter += 1
        status[b-2] = 0
print(counter)

### FIXED CODE ###

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

banned_list = []
for i in range(M):
    banned_list.append(tuple(map(int,input().split())))
banned_list = sorted(banned_list,key=lambda x:x[1])
#status = [1 for _ in range(N-1)]
status = set()
counter = 0
for i in range(M):
    a = banned_list[i][0]
    b = banned_list[i][1]
    if len([one for one in status if (one >= a-1 and one < b-1)]) == 0:
        status  |= {b-2}
        counter += 1
print(counter)