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

import re

def main():
    s = list(input())
    sr = ''.join(list(reversed(s)))
    t = ['dream', 'dreamer', 'erase', 'eraser']
    tr = list()
    for i in t:
        tr.append(''.join(list(reversed(i))))
    flag = False
    while True:
        for i in tr:
            sr_split = re.split('^' + i, sr ,1)
            if len(sr_split) == 2:
                flag = True
                sr = sr_split[1]
                break
        if not flag:
            print('NO')
            break
        if sr == '':
            print('YES')
            break
if __name__ == '__main__':
    main()

### FIXED CODE ###

import re

def main():
    s = list(input())
    sr = ''.join(list(reversed(s)))
    t = ['dream', 'dreamer', 'erase', 'eraser']
    tr = list()
    for i in t:
        tr.append(''.join(list(reversed(i))))
    while sr:
        flag = False
        for i in tr:
            if sr.startswith(i):
                sr = sr.replace(i ,'', 1)
                flag = True
        if not flag:
            print('NO')
            break
        if sr == '':
            print('YES')
            break
if __name__ == '__main__':
    main()
### BUGGY CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000



d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

n, a, b = LI()


n_ = n# まで対応
fun = [1 for i in range(n_+1)]
for i in range(1, n_ + 1):
    fun[i] = fun[i-1] * i % mod

rev = [1 for i in range(n_+1)]
rev[n_] = pow(fun[n_], mod-2, mod)
for i in range(n_-1,0,-1):
    rev[i] = rev[i+1]*(i+1) % mod

def nCr(n,r):
    if n <= 0 or r < 0 or r> n:return 0
    
    return fun[n]*rev[r]%mod*rev[n-r]%mod

ans = pow(2, n, mod) - 1
ans -= nCr(n, a)
ans -= nCr(n, b)

print(ans % mod)

### FIXED CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000



d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

n, a, b = LI()


ans = pow(2, n, mod) - 1
# math.factorial()

# print(ans % mod)

def fur(n,r):
    p,q = 1,1
    for i in range(r):
        p = p*(n-i)%mod
        q = q*(i+1)%mod
    return p * pow(q,mod-2,mod) % mod

print((ans - fur(n, a) - fur(n, b)) % mod)
### BUGGY CODE ###

from fractions import Fraction
from math import ceil
from heapq import heappush, heappop

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

A_queue = []
for a in input().split():
	a = Fraction(int(a), 1)
	heappush(A_queue, (-a, a, 1))

def calc(K):
	while K > 0:
		length, a, div = heappop(A_queue)
		div += 1
		K -= 1
		heappush(A_queue, (-a / div, a, div))
	return -A_queue[0][0]

print(ceil(calc(K)))


### FIXED CODE ###

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

A_list = list(map(int, input().split()))

# search smallest i such that f(i) == True
def auto_bisearch_smallest(f, s = None):
	if s == None:
		s = 0
		w = -1
		while f(s) == True:
			s = w
			w *= 2
	e = s
	w = 1
	while f(e) == False:
		e = s + w
		w *= 2
	
	return bisearch_smallest(f, s, e + 1)

# search smallest i ( s <= i < e ) such that f(i) == True
def bisearch_smallest(f, s, e = None):
	if e == None:
		e = s - 1
		s = 0
	else:
		e -= 1
	
	while s < e:
		m = (s + e) // 2
		if f(m):
			e = m
		else:
			s = m + 1
	
	if s == e and f(s):
		return s
	else:
		return -1

def calc(length):
	count = 0
	for a in A_list:
		if a > length:
			if a % length == 0:
				count += (a // length) - 1
			else:
				count += a // length
	return count

print(auto_bisearch_smallest(lambda length: calc(length) <= K, 1))
### BUGGY CODE ###

N=int(input())
H=[int(s) for s in input().split()]

count_max=0
for j in range(N):
    count=0
    for i in range(j,N-1):
        if H[i] >= H[i+1]:
            count+=1
            #print(j,H[i],H[i+1],count)
        else:
            break
        if count > count_max:
                count_max=count
                X=j

print(count_max)
            

### FIXED CODE ###

N=int(input())
H=[int(s) for s in input().split()]

count_max=0
count=0
for i in range(N-1):
    if H[i]-H[i+1] >= 0:
        count+=1
        if count > count_max:
            count_max=count
    else:
        count=0

print(count_max)
### BUGGY CODE ###

N = int(input())
S = input()
min = min(S[1:].count("E"), S[:N-1].count("W"))

for i in range(1,N-1):
  p = S[:i].count("W") + S[i + 1:].count("E")
  if p < min:
    min = p
print(min)

### FIXED CODE ###

N = int(input())
S = input()
Lw = [0]*N
Le = [0]*N

cw = 0
ce = 0
for i in range(N):
  if S[i] == "W":
    cw += 1
  Lw[i] = cw
  if S[N - 1 - i] == "E":
    ce += 1
  Le[N-1-i] = ce

min = min(Le[1], Lw[N-2])
for i in range(1, N-1):
  p = Le[i + 1] + Lw[i - 1]
  if p < min:
    min = p

print(min)
### BUGGY CODE ###

S = list(input())
Q = int(input())


flg = True
for i in range(Q):
    que = input()
    if que == "1":
        if flg:
            flg = False
        else:
            flg = True
    else:
        j, F, C = que.split()
        if int(F) == 1:
            if flg:
                S = [C] + S
            else:
                S = S + [C]
        else:
            if flg:
                S = S + [C]
            else:
                S = [C] + S

if flg:
    for s in S:
        print(s, end="")
else:
    for s in reversed(S):
        print(s, end="")

### FIXED CODE ###

from collections import deque

S = input()
Q = int(input())

Sq = deque(S)


flg = True
for i in range(Q):
    que = input()
    if que == "1":
        if flg:
            flg = False
        else:
            flg = True
    else:
        j, F, C = que.split()
        if int(F) == 1:
            if flg:
                Sq.appendleft(C)
            else:
                Sq.append(C)
        else:
            if flg:
                Sq.append(C)
            else:
                Sq.appendleft(C)

if flg:
    for i in Sq:
        print(i, end="")
else:
    Sq.reverse()
    for i in Sq:
        print(i, end="")
### BUGGY CODE ###

S = input()
Q = int(input())

S_list = list(S)

for i in range(Q):
    Query = input()
    Query = Query.replace(' ', '')
    Query = list(Query)
    T, F, C = 0, 0, ''
    if len(Query) == 3:
        T = int(Query[0])
        F = int(Query[1])
        C = Query[2]
    else:
        T = int(Query[0])
    
    if T == 1:
        S_list = S_list[::-1]
        
    if T == 2:
        if F == 1:
            S_list = S_list[::-1]
            S_list.append(C)
            S_list = S_list[::-1]
        else:
            S_list.append(C)
            
print(''.join(S_list))

### FIXED CODE ###

from collections import deque

S = input()
Q = int(input())

S_list = list(S)

r = 1
a = []
b = []
d = deque(a)

for i in range(Q):
    q = input().split()
    if q[0] == '1':
        r *= -1
        continue
    elif len(q) == 3:
        if q[1] == '1':
            if r == -1:
                b.append(q[2])
            else:
                d.appendleft(q[2])
        else:
            if r == -1:
                d.appendleft(q[2])
            else:
                b.append(q[2])
                
answer = list(d) + S_list + b

if r == -1:
    answer = answer[::-1]
    
print(''.join(answer))
### BUGGY CODE ###

import numpy as np

N = int(input())
A_list = list(map(int, input().split()))
A_np_list = np.array(A_list)
for i in range(1, N):
    print(np.count_nonzero(A_np_list == i))
print(0)


### FIXED CODE ###

N = int(input())
A_list = list(map(int, input().split()))
ans_list = [0] * (N + 1)
for i in range(N-1):
    ans_list[A_list[i]] += 1
for j in range(N):
    print(ans_list[j + 1])
### BUGGY CODE ###

MOD = 10**9+7
h, w = map(int, input().split())
S = [input() for _ in range(h)]
L = [[0]*w for _ in range(h)]
R = [[0]*w for _ in range(h)]
U = [[0]*w for _ in range(h)]
D = [[0]*w for _ in range(h)]
for i in range(h):
  for j in range(w):
    if j > 0:
      if S[i][j-1] == ".":
        L[i][j] = L[i][j-1]+1
      if S[i][w-j] == ".":
        R[i][w-1-j] = R[i][w-j]+1
    if i > 0:
      if S[i-1][j] == ".":
        U[i][j] = U[i-1][j]+1
      if S[h-i][j] == ".":
        D[h-1-i][j] = D[h-i][j]+1
ans = 0
for i in range(h):
  for j in range(w):
    if S[i][j] == ".":
      temp = L[i][j]+R[i][j]+U[i][j]+D[i][j]+1
      ans = max(ans, temp)
print(ans)

### FIXED CODE ###

MOD = 10**9+7
h, w = map(int, input().split())
S = [input() for _ in range(h)]
L = [[0]*w for _ in range(h)]
R = [[0]*w for _ in range(h)]
U = [[0]*w for _ in range(h)]
D = [[0]*w for _ in range(h)]
for i in range(h):
  for j in range(w):
    if j > 0:
      if S[i][j-1] == ".":
        L[i][j] = L[i][j-1]+1
      if S[i][w-j] == ".":
        R[i][w-1-j] = R[i][w-j]+1
    if i > 0:
      if S[i-1][j] == ".":
        U[i][j] = U[i-1][j]+1
      if S[h-i][j] == ".":
        D[h-1-i][j] = D[h-i][j]+1
ans = 0
for i in range(h):
  for j in range(w):
    if S[i][j] == ".":
      temp = L[i][j]+R[i][j]+U[i][j]+D[i][j]+1
      ans = max(ans, temp)
print(ans)
### BUGGY CODE ###

url = "https://atcoder.jp/contests/abc089/tasks/abc089_c"
import itertools
import math

def main():
    mojiretu = ('M', 'A', 'R', 'C', 'H')
    t = input()
    ttt = []
    for i in range(int(t)):
        tmp = input()
        if tmp[0] in mojiretu:
            ttt.append(tmp)
    if len(ttt) < 3:
        print(0)
        exit()
    li = list(itertools.combinations([v[0] for v in ttt], 3))
    count = 0
    for s in li:
        if len(set(s)) == 3:
            count += 1
    print(count)





if __name__ == '__main__':
    main()





### FIXED CODE ###

url = "https://atcoder.jp/contests/abc089/tasks/abc089_c"
import itertools
import math

def main():
    mojiretu = ('M', 'A', 'R', 'C', 'H')
    dic = {'M': 0, 'A': 0, 'R': 0, 'C': 0, 'H': 0}
    t = input()
    count = 0
    for i in range(int(t)):
        tmp = input()
        if tmp[0] in mojiretu:
            dic[tmp[0]] += 1
    for l in itertools.combinations(mojiretu, 3):
        count += dic[l[0]] * dic[l[1]] * dic[l[2]]
    print(count)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import itertools
N = int(input())
A=list(map(int, input().split()))
total=0

for v in itertools.combinations(A, 2):
    total += v[0]*v[1]
    #print(v)
print(total%(10**9+7))

### FIXED CODE ###

N = int(input())
A=list(map(int, input().split()))
B=[A[N-1]]
#print(B[0])
for i in range(len(A)-2):
    #print(i)
    b=B[i]+A[N-2-i]
    B.append(b)
#print(B)
total=0
for i in range(len(B)):
    total += A[i]*B[len(B)-1-i]

print(total%(10**9+7))
### BUGGY CODE ###

s = str(input())
x,y = map(int,input().split())
x_list,y_list = [],[]
l = s.split('T')

for i in range(0,len(l),2):
  x_list.append(len(l[i]))
for i in range(1,len(l),2):
  y_list.append(len(l[i]))

ans_x,ans_y = [],[]

if s[0]=='F':
  ans_x.append(x_list[0])
  x_list=x_list[1:]
else:
  ans_x.append(0)
ans_y.append(0)

for i in x_list:
  ans = []
  for j in ans_x:
    ans.append(i+j)
    ans.append(j-i)
  ans_x = ans
for i in y_list:
  ans = []
  for j in ans_y:
    ans.append(i+j)
    ans.append(j-i)
  ans_y = ans
if x in ans_x and y in ans_y:
  print("Yes")
else:
  print("No")


### FIXED CODE ###

s = str(input())
x,y = map(int,input().split())
x_list,y_list = [],[]
l = s.split('T')

for i in range(0,len(l),2):
  x_list.append(len(l[i]))
for i in range(1,len(l),2):
  y_list.append(len(l[i]))

ans_x,ans_y = set(),set()

if s[0]=='F':
  ans_x.add(x_list[0])
  x_list=x_list[1:]
else:
  ans_x.add(0)
ans_y.add(0)

for i in x_list:
  ans = set()
  for j in ans_x:
    ans.add(i+j)
    ans.add(j-i)
  ans_x = ans
for i in y_list:
  ans = set()
  for j in ans_y:
    ans.add(i+j)
    ans.add(j-i)
  ans_y = ans
if x in ans_x and y in ans_y:
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left
import sys


N = int(input())
Pn = [[i,j] for i,j in enumerate(list(map(int, sys.stdin.readline().rstrip().split())))]
Pn = sorted(Pn,key=lambda x:-x[1])

In = [Pn[0][0]]
ans = 0
for i,p in Pn[1:]:
  cnt = 0
  c = bisect_left(In,i)
  In.insert(c,i)

  # Choose leftside bigger
  if c > 0:
    l,r = 0,0
    if c == 1:
      l = In[c-1]+1
    elif c > 1:
      l = In[c-1]-In[c-2]
    if c == len(In)-1:
      r = N-In[c]
    elif c < len(In)-1:
      r = In[c+1]-In[c]
    cnt += l*r

  # Choose rightside bigger
  if c < len(In)-1:
    l,r = 0,0
    if c == len(In)-2:
      r = N-In[c+1]
    elif c < len(In)-2:
      r = In[c+2]-In[c+1]
    if c == 0:
      l = In[c]+1
    elif c > 0:
      l = In[c]-In[c-1]
    cnt += l*r
  ans += cnt*p

print(ans)

### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-



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

In = [0] * (N+1)
for i in range(N):
  In[Pn[i]] = i+1

cnt = 0
l = [0] + [i for i in range(N+1)]
r = [i+1 for i in range((N+1))] + [N+1]

for v in range(1, N+1):
  i = In[v]
  
  l1 = l[i]
  l2 = l[l1]
  r1 = r[i]
  r2 = r[r1]
  cnt += ((l1-l2) * (r1-i) + (i-l1) * (r2-r1)) * v
  
  l[r1] = l1
  r[l1] = r1
    
print(cnt)
### BUGGY CODE ###

n,k = map(int,input().split())
a = [int(i) for i in input().split()]
s = 1
for i in range(k): s *= a[i]
for i in range(k,n):
    tmp = s
    s //= a[i-k]
    s *= a[i]
    if tmp < s: ans = "Yes"
    else: ans = "No"
    print(ans)

### FIXED CODE ###

n,k = map(int,input().split())
a = [int(i) for i in input().split()]
for i in range(k,n):
    if a[i-k] < a[i]: ans = "Yes"
    else: ans = "No"
    print(ans)
### BUGGY CODE ###

def solve(N, TAs):
    T, A = 1, 1
    for t, a in TAs:
        m = (t * A) % a
        y = 0
        while True:
            if (m + (y * t)) % a == 0 and (t * A + t * y) // a >= T:
                break
            y += 1
        x = (t * A + t * y) // a - T

        T += x
        A += y
    return T + A

#        T + x : A + y = t : a
#       <=> t * A + y * t = a * T + x * a
#       <=> x =  (t * A + y * t) / a -  T => 整数
# 　　　<=> y =  (a * T + x * a) / t -  A => 整数
# 以下二つが両方とも整数
# (a * T + x * a) / t
# (t * A + y * t) / a
#  t - (a * T mod t) = (x * a) mod t

if __name__ == "__main__":
    N = int(input())
    TAs = [(tuple)(map(int, input().split(" "))) for l in range(N)]
    print(solve(N, TAs))


### FIXED CODE ###

def solve(N, TAs):
    T, A = 1, 1
    for t, a in TAs:
        m = (t * A) % a
        y = max(0, (T * a - t * A) // t)
        while True:
            if (m + (y * t)) % a == 0:
                break
            y += 1
        x = (t * A + t * y) // a - T

        T += x
        A += y
    return T + A


#        T + x : A + y = t : a
#       <=> t * A + y * t = a * T + x * a
#       <=> x =  (t * A + y * t) / a -  T => 整数
# 　　　<=> y =  (a * T + x * a) / t -  A => 整数
# 以下二つが両方とも整数
# (a * T + x * a) / t
# (t * A + y * t) / a
#  t - (a * T mod t) = (x * a) mod t

if __name__ == "__main__":
    N = int(input())
    TAs = [(tuple)(map(int, input().split(" "))) for l in range(N)]
    print(solve(N, TAs))
### BUGGY CODE ###

from collections import deque
n, m = map(int, input().split())
x = deque()
y = deque()
for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        x.append(b)
    elif b == n:
        y.append(a)
for i in x:
    if i in y:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')


### FIXED CODE ###

n, m = map(int, input().split())
x = [[0] * 2 for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        x[b - 1][0] = 1
    elif b == n:
        x[a - 1][1] = 1
if [1, 1] in x:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def lm(a, b):
    if a > b:
        a, b = b, a
    while b % a:
        a, b = b % a, a
    return a


def gm(a, b):
    return a * b // lm(a, b)


def Prim(N):
    P = []
    F = [False, False] + [True] * (N + 1)
    for n in range(2, N + 1):
        if not F[n]:
            continue
        P.append(n)
        for i in range(n, len(F), n):
            F[i] = False
    
    return P


def main():
    mod = 10 ** 9 + 7
    N = int(input())
    A = read_list()
    P = Prim(max(A))

    l = 1
    res = 0
    for a in A:
        if l % a == 0:
            res = (res + l // a) % mod
            continue
        
        if a in P:
            l2 = l * a
        else:
            l2 = gm(a, l)
        res = (res * l2 // l) % mod
        res = (res + l2 // a) % mod
        l = l2
    print(res)


if __name__ == "__main__":
    main()



### FIXED CODE ###

def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def g(a, b):
    if a > b:
        a, b = b, a
    while b % a:
        a, b = b % a, a
    return a


def main():
    mod = 10 ** 9 + 7
    N = int(input())
    A = read_list()

    B = 1
    for a in A:
        B *= a // g(B, a)
    
    print(sum(B // a for a in A) % mod)


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

n = int(input())
s = list(input())

ans = 0
for i in range(1000):
    key = str(i).zfill(3)
    k = 0
    t = key[k]
    for j in range(len(s)):
        if t == s[j]:
            k += 1
            if k == 3:
                ans += 1
                break
            t = key[k]
print(ans)


### FIXED CODE ###

n = int(input())
s_list = list(input())

ans = 0
for i in range(1000):
    key = str(i).zfill(3)
    k = 0
    t = key[k]
    for s in s_list:
        if t == s:
            k += 1
            if k == 3:
                ans += 1
                break
            t = key[k]
print(ans)
### BUGGY CODE ###

k, s = map(int, input().split())

ret = 0
for x in range(k + 1):
    for y in range(k + 1):
        for z in range(k + 1):
            if x + y + z == s:
                ret += 1
print(ret)                

### FIXED CODE ###

k, s = map(int, input().split())
ret = 0

for x in range(k + 1):
    for y in range(k + 1):
        if x + y <= s and x + y + k >= s:
            ret += 1
print(ret)
### BUGGY CODE ###

#!/usr/bin/env python3
# %%
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


# %%
import numpy as np
from scipy.optimize import fmin


# %%
N, K = map(int, readline().split())
XYZ = np.array(read().split(), np.int64)
X = XYZ[::3]
Y = XYZ[1::3]
Z = XYZ[2::3]

# %%


def f(pt):
    x, y = pt
    cost = Z * ((x - X) ** 2 + (y - Y) ** 2) ** .5
    cost.sort()
    return cost[K - 1]


def calc(x0):
    opt_pt = fmin(f, x0, disp=False, ftol=1e-7)
    return f(opt_pt)


# %%
answer = 10 ** 18
for x, y, z in zip(X, Y, Z):
    f_value = calc([x, y])
    if answer > f_value:
        answer = f_value
    for n in np.random.randint(0, N, 3):
        x1, y1, z1 = X[n], Y[n], Z[n]
        f_value = calc([(x * z1 + x1 * z) / (z + z1), (y * z1 + y1 * z) / (z + z1)])
        if answer > f_value:
            answer = f_value

# %%
print(answer)


# %%


### FIXED CODE ###

import sys
from cmath import rect
import numpy as np
import numba
from numba import njit
i8 = numba.int64

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

eps = 1e-9

@njit((numba.complex128, numba.float64) * 2, cache=True)
def cross_circles(c1, r1, c2, r2):
    d = abs(c1 - c2)
    if d <= abs(r1 - r2) or r1 + r2 <= d:
        return None
    cos_theta = (r1 * r1 + d * d - r2 * r2) / (2 * r1 * d)
    theta = np.arccos(cos_theta)
    z1 = (c2 - c1) * rect(r1 / d, theta)
    z2 = (c2 - c1) * rect(r1 / d, -theta)
    return (c1 + z1, c1 + z2)

@njit
def test(Z, C, t):
    R = t / C
    cand = list(Z)
    for j in range(len(Z)):
        for i in range(j):
            points = cross_circles(Z[i], R[i], Z[j], R[j])
            if points is not None:
                for p in points:
                    cand.append(p)
    cand = np.array(cand)
    cnt = np.zeros(len(cand), np.int64)
    for i in range(len(Z)):
        cnt += np.abs(cand - Z[i]) <= R[i] + eps
    return np.any(cnt >= K)

N, K = map(int, readline().split())
nums = np.array(read().split(), np.float64)

Z = nums[::3] + 1j * nums[1::3]
C = nums[2::3]

l = 0
r = 10**9
for _ in range(100):
    m = (l + r) / 2
    if test(Z, C, m):
        r = m
    else:
        l = m

print(r)
### BUGGY CODE ###

import heapq
n, m = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(n)]
heapq.heapify(lst)
r = []
heapq.heapify(r)
ans = 0
d = 1

while True:
    while True:
        if len(lst) != 0:
            p_lst = heapq.heappop(lst)
            if p_lst[0] <= d:
                heapq.heappush(r, - p_lst[1])
            else:
                heapq.heappush(lst, p_lst)
                break
        else:
            break
    if len(r) != 0:
        ans += - heapq.heappop(r)
    d += 1
    if d > m:
        print(ans)
        exit()



### FIXED CODE ###

import heapq
n, m = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(n)]
heapq.heapify(lst)
r = []
heapq.heapify(r)
ans = 0
d = 1

while True:
    while True:
        if len(lst) != 0:
            p_lst = heapq.heappop(lst)
            if p_lst[0] <= d:
                heapq.heappush(r, - p_lst[1])
            else:
                heapq.heappush(lst, p_lst)
                break
        else:
            break
    if len(r) != 0:
        ans += - heapq.heappop(r)
    d += 1
    if d > m:
        print(ans)
        exit()
### BUGGY CODE ###

N, M = map(int, raw_input().split())
paths = {}
for m in range(M):
	path = map(int, raw_input().split())
	a_p = paths.get(path[0],[])
	b_p = paths.get(path[1],[])
	a_p.append(path[1])
	b_p.append(path[0])
	paths[path[0]] = a_p
	paths[path[1]] = b_p

visited = [False] * (N+1)

visited[0] = True
to_visit = [1]
signposts = [None] * (N+1)
while len(to_visit) > 0:
	curr = to_visit.pop(0)
	if visited[curr]:
		continue
	else:
		path = paths[curr]
		for p in path:
			if signposts[p] == None:
				signposts[p] = curr
				to_visit.append(p)
		visited[curr] = True
all_visited = all(visited)

if all_visited:
	print 'Yes'
	for s in range(2,len(signposts)):
		print signposts[s]
else:
	print 'No'




### FIXED CODE ###

N, M = map(int, raw_input().split())
paths = {}
for m in range(M):
	path = map(int, raw_input().split())
	a_p = paths.get(path[0],[])
	b_p = paths.get(path[1],[])
	a_p.append(path[1])
	b_p.append(path[0])
	paths[path[0]] = a_p
	paths[path[1]] = b_p

visited = [False] * (N+1)

visited[0] = True
to_visit = [1]
signposts = [None] * (N+1)
i = 0
while len(to_visit) > i:
	curr = to_visit[i]
	if visited[curr]:
		i += 1
	else:
		path = paths[curr]
		for p in path:
			if signposts[p] == None:
				signposts[p] = curr
				to_visit.append(p)
		visited[curr] = True
		i += 1
all_visited = all(visited)

if all_visited:
	print 'Yes'
	for s in range(2,len(signposts)):
		print signposts[s]
else:
	print 'No'
### BUGGY CODE ###

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

ans = 0
for i in range(60):
  num_one = len([1 for x in A if x & (1 << i)])
  ans = (ans + (1 << i) * num_one * (N - num_one)) % 1000000007
print(ans)

### FIXED CODE ###

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

ans = 0
for i in range(60):
  p = 1 << i
  num_one = len([1 for x in A if x & p])
  ans = ans + p * num_one * (N - num_one)
print(ans % 1000000007)
### BUGGY CODE ###

# https://atcoder.jp/contests/abc065/tasks/abc065_b

def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

N = INT()
a = []
for _ in range(N):
    a.append(INT() - 1)

light_idx = 0

ans = 0
while True:
    light_idx = a[light_idx]
    ans += 1

    if light_idx == 1:
        break

    if light_idx == 0:
        ans = -1
        break

print(ans)


### FIXED CODE ###

# https://atcoder.jp/contests/abc065/tasks/abc065_b

def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

N = INT()
a = []
for _ in range(N):
    a.append(INT() - 1)

light_idx = 0

ans = 0
while True:
    light_idx = a[light_idx]
    ans += 1

    if light_idx == 1:
        break

    if ans > N:
        ans = -1
        break

print(ans)