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

#event sort
import bisect
N, Q = map(int, input().split())
events = [[0,0,0] for _ in range(2*N)]
for i in range(N):
    s,t,x = map(int, input().split())
    events[2*i]=[s-x, 1, x]
    events[2*i+1]=[t-x, -1, x]
events.sort()
sets = set()
for _ in range(Q):
    d = int(input())
    eventime = [event[0] for event in events]
    index = bisect.bisect_right(eventime, d)
    for _ in range(index):
        t, pm, x = events.pop(0)
        if pm == 1:
            sets.add(x)
        if pm == -1:
            sets.remove(x)
    if len(sets)==0:
        print(-1)
    else:
        print(min(sets))

### FIXED CODE ###

from bisect import bisect_left
N, Q = map(int, input().split())
consts = []
for _ in range(N):
    s,t,x = map(int, input().split())
    consts.append((x,s,t))
consts.sort()
D=[int(input()) for _ in range(Q)]
ans=[-1]*Q
jump=[-1]*Q
for x,s,t in consts:
    left=bisect_left(D,s-x)
    right=bisect_left(D,t-x)
    while left<right:
        if jump[left]==-1:
            ans[left]=x
            jump[left]=right
            left += 1
        else:
            left=jump[left]
print(*ans, sep='\n')
### BUGGY CODE ###

import itertools
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353
def cummax(it, first=-float('inf')):
    """
    np.maximum.accumulate(arr) でもよさそう
    https://stackoverflow.com/questions/33569668/numpy-max-vs-amax-vs-maximum

    累積 max
    :param collections.Iterable it:
    :param float first:
    :return:
    """
    cm = first
    ret = []
    for v in it:
        cm = max(v, cm)
        ret.append(cm)
    return ret


N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))

# dp[k]: i | j | k == k となる i, j のうち A[i] + A[j] が最大となる i, j
#: :type: list of ((int, int), (int, int))
dp = [None] * (2 ** N)
for k in range(1, 2 ** N):
    dp[k] = (A[0], 0), (A[k], k)

digits = []
k = 1
while k < 2 ** N:
    digits.append(k)
    k <<= 1

for bit in range(2, N + 1):
    for ds in itertools.combinations(digits, bit):
        k = sum(ds)
        for rm1, rm2 in itertools.combinations(ds, 2):
            a, b = dp[k - rm1]
            c, d = dp[k - rm2]
            e, f = dp[k]
            ss = sorted({a, b, c, d, e, f})
            dp[k] = ss[-1], ss[-2]

ans = [0] * (2 ** N)
for k in range(1, 2 ** N):
    (a1, _), (a2, _) = dp[k]
    ans[k] = a1 + a2

ans = cummax(ans[1:])
print(*ans, sep='\n')


### FIXED CODE ###

import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353
def cummax(it, first=-float('inf')):
    """
    np.maximum.accumulate(arr) でもよさそう
    https://stackoverflow.com/questions/33569668/numpy-max-vs-amax-vs-maximum

    累積 max
    :param collections.Iterable it:
    :param float first:
    :return:
    """
    cm = first
    ret = []
    for v in it:
        cm = max(v, cm)
        ret.append(cm)
    return ret


N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))
SIZE = 2 ** N

# dp[k]: i | j | k == k となる i, j のうち A[i] + A[j] が最大となる i, j
#: :type: list of ((int, int), (int, int))
dp = [None] * SIZE
for k in range(1, SIZE):
    dp[k] = list(sorted([(A[0], 0), (A[k], k)]))

for k in range(1, SIZE):
    mask = k
    while mask < SIZE - 1:
        # kに立ってないビットを1つだけ立てる
        next_k = (mask + 1) | k
        mask |= next_k

        a1, a2 = dp[k]
        b1, b2 = dp[next_k]
        if a1 > b2:
            # dp[next_k] = a1, a2
            dp[next_k] = dp[k]
        elif b1 > a2:
            # dp[next_k] = b1, b2
            pass
        elif a2 > b2:
            dp[next_k] = b2, a2
        elif b2 > a2:
            dp[next_k] = a2, b2

ans = [0] * SIZE
for k in range(1, SIZE):
    (a1, _), (a2, _) = dp[k]
    ans[k] = a1 + a2

ans = cummax(ans[1:])
print(*ans, sep='\n')
### BUGGY CODE ###

n = int(input())
b = list(map(str, input().split()))
''.join(b)
ans = []
def dfs(b):
    if len(b) == 1:
        if int(b[0]) == 1:
            return True
    else:
        for i in range(len(b) - 1, -1, -1):
            if int(b[i]) == i + 1:
                if i == 0:
                    if dfs(b[1:]):
                        ans.append(i + 1)
                        return True
                else:
                    if dfs(b[:i] + b[i+1:]):
                        ans.append(i + 1)
                        return True
        return False
if dfs(b):
    ans.insert(0, 1)
    for i in range(len(ans)):
        print(ans[i])
else:
    print(-1)


### FIXED CODE ###

n = int(input())
b = list(map(int, input().split()))
ans = []
while(len(b) != 1):
    count = 0
    for i in range(len(b) - 1, -1, -1):
        if b[i] == i + 1:
            b.pop(i)
            ans.append(i + 1)
            count = 0
            break
        else:
            count += 1
    if count == len(b):
        print(-1)
        exit()
if b[0] == 1:
    ans.append(1)
    ans = list(reversed(ans))
    for i in range(len(ans)):
        print(ans[i])
else:
    print(-1)
### BUGGY CODE ###

N,M = map(int,input().split())
A = []
C = []

for i in range(M):
    A.append(int(input().split()[0]))
    C.append(list(map(int,input().split())))

import numpy as np


inf = 1000000000
dp = np.zeros(2**N).astype('int')

dp[:] = inf
dp[0] = 0


for i in range(M):
    cost = A[i]
    candidate = C[i]
    mask = 0
    for c in candidate:
        mask += 1 << (c-1)
    for j in range(2**N):
        if dp[j|mask] > dp[j] + cost:
            dp[j|mask] = dp[j] + cost


if dp[-1] == inf:
    print(-1)
else:
    print(dp[-1])


### FIXED CODE ###


import sys
input = sys.stdin.readline
N,M = map(int,input().split())
A = []
C = []

for i in range(M):
    A.append(int(input().split()[0]))
    C.append(list(map(int,input().split())))


inf = 1000000000
dp = [inf for _ in range(2**N)]
dp[0] = 0

for i in range(M):
    cost = A[i]
    candidate = C[i]
    mask = 0
    for c in candidate:
        mask += 1 << (c-1)
    for j in range(2**N):
        if dp[j|mask] > dp[j] + cost:
            dp[j|mask] = dp[j] + cost

if dp[-1] == inf:
    print(-1)
else:
    print(dp[-1])
### BUGGY CODE ###

N = int(input())
numb = input().split()

def answer(N, numb):
    for i in range(N):
        for j in range(N):
            if i <= j:
                continue

            if numb[i] == numb[j]:
                return "NO"

    return "YES"
 
print(answer(N,numb))


### FIXED CODE ###

N = int(input())
numb = input().split()

if len(set(numb)) == len(numb):
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

N=int(input())
mod=998244353
Combi=[1]
for i in range(1,N+1):
    Combi.append(Combi[-1]*(N-i+1)*pow(i,mod-2,mod)%mod)
SC=0
for i in range(N//2+1,N+1):
    SC+=Combi[i]*pow(2,N-i,mod)
print((pow(3,N,mod)-SC*2)%mod)

### FIXED CODE ###

N=int(input())
mod=998244353

FACT=[1]
for i in range(1,N+1):
    FACT.append(FACT[-1]*i%mod)

FACT_INV=[pow(FACT[-1],mod-2,mod)]
for i in range(N,0,-1):
    FACT_INV.append(FACT_INV[-1]*i%mod)

FACT_INV.reverse()

POW=[1]
for i in range(N):
    POW.append(POW[-1]*2%mod)

def Combi(a,b):
    return FACT[a]*FACT_INV[b]*FACT_INV[a-b]%mod

SC=0
for i in range(N//2+1,N+1):
    SC+=Combi(N,i)*POW[N-i]

print((pow(3,N,mod)-SC*2)%mod)
### BUGGY CODE ###

from collections import deque

H, W=map(int, input().split())
ch, cw=map(int, input().split())
dh, dw=map(int, input().split())
ch-=1
cw-=1
dh-=1
dw-=1

grid=["0"]*H
for i in range(H):
    s=input()
    grid[i]=s

Inf=10**12
cost=[[Inf] * W for i in range(H)]

walk=[(0, 1), (0, -1), (-1, 0), (1, 0)]
warp=[]
for i in range(-2, 3):
    for j in range(-2, 3):
        if i==0 and j==0:
            continue
        if (i, j) not in walk:
            warp.append((i, j))

q=deque()
cost[ch][cw]=0
q.append((ch, cw, 0))

while q:
    x, y, c=q.popleft()
    for dx, dy in walk:
        nx = x+dx
        ny = y+dy
        if 0<= nx < H and 0<= ny < W and grid[nx][ny]=="." and cost[nx][ny]>c:
            cost[nx][ny]=c
            q.appendleft((nx, ny, c))
    
    for dx, dy in warp:
        nx = x+dx
        ny = y+dy
        if 0<= nx < H and 0<= ny < W and grid[nx][ny]=="." and cost[nx][ny]>c+1:
            cost[nx][ny]=c+1
            q.append((nx, ny, c+1))


if cost[dh][dw]==Inf:
    print(-1)
else:
    ans=cost[dh][dw]
    print(ans)

### FIXED CODE ###

from collections import deque


H, W = map(int, input().split())
Ch, Cw = map(lambda x: int(x) - 1, input().split())
Dh, Dw = map(lambda x: int(x) - 1, input().split())
maze = [input() for _ in range(H)]

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]  # path: 各マスへの移動コスト

# walk:移動A, warp:移動B
walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

q = deque()
path[Ch][Cw] = 0
q.append((Ch, Cw, 0))

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:  # 移動A
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
            path[nx][ny] = s
            q.appendleft((nx, ny, s))  # 移動Aの場合はコスト0. キューの先頭に追加する.
    for dx, dy in warp:  # 移動B
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
            path[nx][ny] = s + 1
            q.append((nx, ny, s + 1))  # 移動Bの場合はコスト1. キューの最後尾に追加する.
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)
### BUGGY CODE ###

def f(n,x,i):
    if n == 0:
        if i != 0:
            if x/i == m:
                return 1
        return 0
    if memo[n-1][i][x] != -1 :
        if memo[n-1][i][x] > 0:
            return memo[n-1][i][x]
    memo[n-1][i][x] = f(n-1,x,i)+f(n-1,x+a[n-1],i+1)
    return memo[n-1][i][x]

n, m= map(int,input().split())
a = list(map(int,input().split()))
memo = [[[-1 for _ in range(sum(a)+1)]for i in range(n)]for i in range(n)]
print(f(n,0,0))

### FIXED CODE ###

def f(n,x,i):
    if n == 0:
        if i != 0:
            if x/i == m:
                return 1
        return 0
    if memo[n-1][i][x] != -1 :
        return memo[n-1][i][x]
    memo[n-1][i][x] = f(n-1,x,i)+f(n-1,x+a[n-1],i+1)
    return memo[n-1][i][x]

n, m= map(int,input().split())
a = list(map(int,input().split()))
memo = [[[-1 for _ in range(sum(a)+1)]for i in range(n)]for i in range(n)]
print(f(n,0,0))
### BUGGY CODE ###

import numpy as np


def mo(v):
    return v % 1000000007


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


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
s = [0]
ans = 0
MOD = 1000000007
for i in range(0, n, 1):
    s.append((s[i] + a[i]) % MOD)

for i in range(0, n, 1):
    ans += ((s[n] - s[i + 1]) * a[i]) % MOD

print(ans % MOD)
### BUGGY CODE ###

import math
K = int(input())
ans = 0
for i in range(1,K+1):
	for j in range(1,K+1):
		for n in range(1,K+1):
			tmp = math.gcd(i,j)
			ans += math.gcd(tmp,n)
print(ans)

### FIXED CODE ###

import math
K = int(input())
ans = 0
for i in range(1,K+1):
	for j in range(1,K+1):
		tmp = math.gcd(i,j)
		for n in range(1,K+1):
			ans += math.gcd(tmp,n)
print(ans)
### BUGGY CODE ###

def solve(a,M):
	for x,y in xy:
		if x in a and y in a and a.index(x) > a.index(y):
			break
	else:
		if len(a) == m: return a
		return max([solve([M[i]] + a,M[:i]+M[i+1:]) for i in range(len(M))])

m = input()
xy = [map(int,raw_input().split()) for i in range(input())]
ans = solve([],range(1,m+1))
for i in ans: print i

### FIXED CODE ###

def solve(a):
	for i in M-set(a):
		if any(x == i and y not in a for x,y in xy): continue
		r = solve([i]+a)
		if r: return r
	return a
m = input()
M = set(range(1,m+1))
xy = [map(int,raw_input().split()) for i in range(input())]
for i in solve([]): print i
### BUGGY CODE ###

import random
random.seed(0)

D = int(input())
C = [int(i) for i in input().split()]
S = [[int(i) for i in input().split()] for j in range(D)]

def score_calc(T):
    total = 0
    last = [0] * 26
    for i in range(1, D+1):
        t = T[i-1]
        total += S[i-1][t-1]
        last[t-1] = i
        for j in range(26):
            total -= C[j] * (i - last[j])
    return total
    
N = 10000
T_ls = [[random.randint(1, 26) for i in range(D)] for j in range(N)]
best_score = 0
ans = []
for i in range(N):
    if score_calc(T_ls[i]) > best_score:
        best_score = score_calc(T_ls[i])
        ans = T_ls[i]

for i in range(D):
    print(ans[i])

### FIXED CODE ###

D = int(input())
C = [int(i) for i in input().split()]
S = [[int(i) for i in input().split()] for j in range(D)]

total = 0
last = [0] * 26
ans = []
for i in range(1, D+1):
    score = [0] * 26
    for t in range(26):
        score[t] += S[i-1][t-1]
        for j in range(26):
            if j != t:
                score[t] -= C[j] * (i - last[j])
    total += max(score)
    last[score.index(max(score))] = i
    ans.append(score.index(max(score))+1)

for i in range(D):
    print(ans[i])
### BUGGY CODE ###

def main():
    from collections import deque
    from itertools import combinations
    import sys
    input = sys.stdin.readline

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

    g = tuple(set() for _ in range(N))
    for idx in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        g[a].add((b, c, idx))  # to,weight,idx
        g[b].add((a, c, idx))  # to,weight,idx

    used_edge = 0

    dq = deque()
    for frm, to in combinations(range(N), r=2):
        dq.append((frm, 0))

        dist = [1000 * 100 + 10] * N
        dist[frm] = 0
        while dq:
            v, c = dq.popleft()
            if dist[v] < c: continue
            for u, dc, idx in g[v]:
                nc = c + dc
                if dist[u] > nc:
                    dist[u] = nc
                    dq.append((u, nc))

        dq.append((to, 0))
        while dq:
            v, b = dq.popleft()
            if v == frm:
                used_edge |= b
                continue

            for u, dc, idx in g[v]:
                if dist[u] == dist[v] - dc:
                    dq.append((u, b | 1 << idx))

    print(M - bin(used_edge).count('1'))


if __name__ == '__main__':
    main()


### FIXED CODE ###

inf = 1000 * 1000 + 10

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

g = tuple([inf] * n for _ in range(n))
e = set()
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    g[a][b] = c
    g[b][a] = c
    e.add((a, b, c))

for i in range(n):
    g[i][i] = 0

for k in range(n):
    for i in range(n):
        for j in range(n):
            g[i][j] = min(g[i][j], g[i][k] + g[k][j])

# print(g)

need = set()
for a, b, c in e:
    for s in range(n):
        for t in range(n):
            if g[s][t] == g[s][a] + c + g[b][t]:
                need.add((a, b))
                break
        else:
            continue
        break
# print(need)
print(m - len(need))
### BUGGY CODE ###

mod = 1000000007        

import fractions

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

n=int(input())

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

max_gcm = 1

for i in t:
    max_gcm = lcm(i,max_gcm)

ans = 0

for i in t:
    ans += max_gcm//i
    ans %= mod

print(ans)

### FIXED CODE ###

import math
 
mod = 1000000007
 
def lcm(x, y):
    return (x * y) // math.gcd(x, y)
 
n=int(input())
 
a = list(map(int,input().split()))
 
memo = a[0]
 
for i in range(1,n):
    memo = lcm(memo,a[i])
 
ans = 0
 
for i in range(n):
    ans += memo*pow(a[i], mod-2, mod)%mod
    ans %= mod
 
print(ans)
### BUGGY CODE ###

N = int(input())
A = [int(n) for n in input().split()]
A = [0] + A + [0]
L = []
LL = []

for i, a in enumerate(A):
    if i < len(A) - 1:
        L.append(abs(A[i] - A[i+1]))
    if i < len(A) - 2:
        LL.append(abs(A[i] - A[i+2]))

for i in range(N):
    ans = sum(L) - L[i] - L[i+1] + LL[i]
    print(ans)


### FIXED CODE ###

N = int(input())
A = [int(n) for n in input().split()]
A = [0] + A + [0]
L = []
LL = []

for i, a in enumerate(A):
    if i < len(A) - 1:
        L.append(abs(A[i] - A[i+1]))
    if i < len(A) - 2:
        LL.append(abs(A[i] - A[i+2]))

s = sum(L)

for i in range(N):
    ans = s - L[i] - L[i+1] + LL[i]
    print(ans)
### BUGGY CODE ###

N = int(input())
lst_a = list(map(int, input().split()))
total = sum(lst_a)
ans = float("INF")


for i in range(N - 1):
    x = sum(lst_a[:i+1])
    y = total - x
    ans = min(ans, abs(x - y))


print(ans)

### FIXED CODE ###

N = int(input())
lst_a = list(map(int, input().split()))
total = sum(lst_a)
x = 0
ans = float("INF")


for i in range(N - 1):
    x += lst_a[i]
    y = total - x
    ans = min(ans, abs(x - y))


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

import heapq
h,w = map(int,input().split())
ch, cw = map(int,input().split())
dh, dw = map(int,input().split())
s = [list(input()) for _ in range(h)]
ch -= 1
cw -= 1
dh -= 1
dw -= 1
vec5 = []
vec = [(1, 0), (0, 1), (-1, 0), (0, -1)]
for i in range(-2, 3):
    for j in range(-2, 3):
        vec5 += [(i,j)]

q = [(0, (ch, cw))]
heapq.heapify(q)
while len(q) > 0:
    c, (i,j) = heapq.heappop(q)
    if s[i][j] != '.' and s[i][j] != '#' and s[i][j] <= c:
        continue
    s[i][j] = c
    for v in vec:
        ii = i + v[0]
        jj = j + v[1]
        if 0 <= ii < h and 0 <= jj < w and s[ii][jj] == '.':
            heapq.heappush(q, (c, (ii, jj)))
    for v in vec5:
        ii = i+v[0]
        jj = j+v[1]
        if 0 <= ii < h and 0 <= jj < w and s[ii][jj] == '.':
            heapq.heappush(q, (c+1, (ii, jj)))
if s[dh][dw] == '.':
    print(-1)
else:
    print(s[dh][dw])

### FIXED CODE ###

h,w = map(int,input().split())
ch, cw = map(int,input().split())
dh, dw = map(int,input().split())
s = [list(input()) for _ in range(h)]
ch -= 1
cw -= 1
dh -= 1
dw -= 1
vec5 = []
vec = [(1, 0), (0, 1), (-1, 0), (0, -1)]
for i in range(-2, 3):
    for j in range(-2, 3):
        if abs(i) + abs(j) < 2:
            continue
        vec5 += [(i,j)]

c = 0
q = [(ch, cw)]
while len(q) > 0:
    nq = []
    while len(q) > 0:
        i, j = q.pop()
        s[i][j] = c
        nq += [(i,j)]
        for v in vec:
            ii = i + v[0]
            jj = j + v[1]
            if 0 <= ii < h and 0 <= jj < w and s[ii][jj] == '.':
                q += [(ii, jj)]


    while len(nq) > 0:
        i, j = nq.pop()
        for v in vec5:
            ii = i+v[0]
            jj = j+v[1]
            if 0 <= ii < h and 0 <= jj < w and s[ii][jj] == '.':
                q += [(ii, jj)]
    c += 1
if s[dh][dw] == '.':
    print(-1)
else:
    print(s[dh][dw])
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
count = 1
l = []
for i in range(0,N):
	for j in range(0,N):
		if(count == A[j]):
			l.append(j+1)
			count += 1
			break

print(' '.join(map(str, l)))

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
count = 1
l = [0]*N

for i in A:
	l[i-1] = count
	count += 1
    
print(' '.join(map(str, l)))
### BUGGY CODE ###

n, k = map(int, input().split())
nums = list(map(int, input().split()))

sum_max = [sum(nums[i:i+k]) for i in range(n-k+1)]

max_e = (max(sum_max) +k)/2

print(max_e)


### FIXED CODE ###

n, k = map(int, input().split())
nums = list(map(int, input().split()))
 
sum_max = sum(nums[:k])
temp = sum_max
for i in range(k,n):
  temp -= nums[i-k]
  temp += nums[i]
  sum_max = max(temp, sum_max)
print((sum_max +k)/2)
### BUGGY CODE ###

A,B,K = [int(_) for _ in input().split()]
for i in range(K):
    if A >= 1:
        A -= 1
    elif B >= 1:
        B -= 1
    else:
        break
print(A, B)


### FIXED CODE ###

A,B,K = [int(_) for _ in input().split()]
if K <= A:
    A -= K
elif K <= A+B:
    B -= K-A
    A = 0
elif A+B < K:
    A = 0
    B = 0
print(A, B)
### BUGGY CODE ###

M = 10**9 + 7
a = [1] + [0] * 12
p = 1
for c in reversed(input()):
    r = range(0, p * 10, p) if c == '?' else (p * int(c),)
    a = [sum(a[(i - j) % 13] for j in r) for i in range(13)]
    p = p * 10 % 13
print(a[5] % M)

### FIXED CODE ###

M = 10**9 + 7
a = [1] + [0] * 12
p = 1
for c in reversed(input()):
    r = range(10) if c == '?' else (int(c),)
    a = [sum(a[(i - p * j) % 13] for j in r) % M for i in range(13)]
    p = p * 10 % 13
print(a[5])
### BUGGY CODE ###

import sys
from collections import defaultdict
input = sys.stdin.readline
N, M = map(int, input().split())
g = defaultdict(list)
for i in range(M):
  a, b = map(int, input().split())
  g[a].append(b)
  g[b].append(a)
ans = [0 for _ in range(N+1)]
ans[1] = 1
#print(g)
current = [1]
while 0 in ans[2:]:
  #print(ans)
  next = []
  for i in current:
    #print('i',i)
    for j in g[i]:
      if ans[j] == 0:
        ans[j] = i
        next.append(j)
  current = next
print('Yes')
for i in range(2,N+1):
  print(ans[i])


### FIXED CODE ###

import sys
from collections import defaultdict
input = sys.stdin.readline
N, M = map(int, input().split())
g = defaultdict(list)
for i in range(M):
  a, b = map(int, input().split())
  g[a].append(b)
  g[b].append(a)
que = [1]
ans = [0 for _ in range(N+1)]
while len(que)>0:
  current = que.pop(0)
  for next in g[current]:
    if ans[next] == 0:
      que.append(next)
      ans[next] = current
print('Yes')
for i in range(2,N+1):
  print(ans[i])
### BUGGY CODE ###

import sys
n = int(input())
d = []
for i in range(n):
    c = sys.stdin.readline()
    if c[0] == 'i':
        d.append(c[7:])
    else:
        if c[5:] in d:
            print('yes')
        else:
            print('no')

### FIXED CODE ###

import sys
input()
r = sys.stdin.readlines()
d = {}

for i in r:
    if i[0] == 'i':
        d[i[7:]] = 0
    else:
        if i[5:] in d:
            print('yes')
        else:
            print('no')
### BUGGY CODE ###

S = input()
N = len(S)
table = [1] + [0] * 2020

curr = 0
for i in range(N):
    curr += int(S[N-1-i])*(10**i)%2019
    curr %= 2019
    table[curr] += 1

ans = 0
for i in table:
    ans += i*(i-1)//2
print(ans)

### FIXED CODE ###

S = input()
N = len(S)
table = [1] + [0] * 2020
exp = [1]
for i in range(N):
    exp += [exp[-1]*10 %2019]

curr = 0
for i in range(N):
    curr += int(S[N-1-i])*exp[i]
    curr %= 2019
    table[curr] += 1

ans = 0
for i in table:
    ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

s=input()
n=len(s)

#sのあるindexに、ある操作回数後にいる人の数を格納する配列を準備する。はじめはすべてのマスに1人
state=[0 for i in range(n)]

def countR(i): 
	count=0
	j=i
	while s[j]=='R':
		count+=1
		j+=1
	return count

def countL(i):
	count=0
	j=i
	while s[j]=='L':
		count+=1
		j-=1
	return count
	
for i in range(n):
	if s[i]=='R':
		state[i+countR(i)-(countR(i)%2==1)]+=1
	if s[i]=='L':
		state[i-countL(i)+(countL(i)%2==1)]+=1
		
for i in range(n):
	print(state[i],end=' ')

### FIXED CODE ###

#print('RRRLLRL'.index('LR'))
#print('RRRLLRLR'.index('LR'))
#=>4
#str.index(検索文字列,開始位置,終了位置)

#indexは見つからないとエラー
#findは見つからないと-1を出力

#s='RRLRLR'
#bubun=s[0:3]
#print(bubun)
#=>RRL


def stateRL(s):
	state=[0]*len(s)
	r=s.count('R')
	l=s.count('L')
	state[r-1]=1+(r-1)//2+l//2
	state[r]=1+r//2+(l-1)//2
	return state

s=input()
n=len(s)

state=[]

kireme=-1
nkireme=s.find('LR',0)

while nkireme!=-1:
	bubun=s[kireme+1:nkireme+1:]
	state+=stateRL(bubun)
	kireme=nkireme
	nkireme=s.find('LR',kireme+1)

bubun=s[kireme+1::]
state+=stateRL(bubun)
	
for i in range(n):
	print(state[i],end=' ')