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

from math import ceil, log2
class SegTree:
    ide_ele = 0
    def __init__(self, init_val):
        n = len(init_val)
        self.num = 2**ceil(log2(n))
        self.seg = [self.ide_ele] * (2 * self.num - 1)

    def segfunc(self, x, y):
        return max(x, y)

    def update(self, k, x):
        k += self.num - 1
        self.seg[k] = x
        while k:
            k = (k - 1) // 2
            self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2])

    def query(self, a, b, k, l, r):
        """
        最初はquery(a, b, 0, 0, self.num)で呼び出す
        [a:b) でクエリをよびだす
        @see https://www.slideshare.net/iwiwi/ss-3578491
        :param a:
        :param b:
        :param k: ノード
        :param l:
        :param r:
        :return:
        """
        if r <= a or b <= l:
            return self.ide_ele
        if a <= l and r <= b:
            return self.seg[k]
        else:
            vl = self.query(a, b, k*2+1, l, (l+r)//2)
            vr = self.query(a, b, k*2+2, (l+r)//2, r)
            return self.segfunc(vl, vr)


n, k = map(int, input().split())
a = [int(input()) for _ in range(n)]
MAX_A = max(a)
st = SegTree([0]*MAX_A)
res = 0
for i in a:
    min_a = max(i-k, 0)
    max_a = min(i+k, MAX_A)
    s = st.query(min_a, max_a+1, 0, 0, st.num)
    st.update(i, max(s, 0)+1)
    res = max(res, max(s, 0) + 1)

print(res)


### FIXED CODE ###

from math import ceil, log2
import sys
z=sys.stdin.readline


# SegTreeの関数
def segfunc(x, y):
    return max(x, y)


# 単位元
# min->inf, max->-inf, add->0, mul->1
ide_ele = -1


# セグメント木
class SegTree:

    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセットする
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        res = self.ide_ele
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res


n, k = map(int, z().split())
a = [int(z()) for _ in range(n)]
M=300001
st = SegTree([0]*M, max, 0)
res = 0
for i in a:
    min_a = max(i-k, 0)
    max_a = min(i+k, M)
    s = st.query(min_a, max_a+1)
    st.update(i, max(s, 0)+1)
    res = max(res, max(s, 0) + 1)

print(res)
### BUGGY CODE ###

n, q = map(int, input().split())
s = str(input())

for i in range(q):
  l, r = map(int, input().split())
  slice = s[l-1:r]
  print(slice.count("AC"))


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t = [0] * (N + 1)
for i in range(N):
  t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
  l, r = map(int, input().split())
  print(t[r-1] - t[l-1])
### BUGGY CODE ###

# many TLEs & 2 WAs

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

S = [0]
X = [0]
#check = []
for i in range(N):
    S.append(S[-1] + A[i])
    X.append(X[-1] ^ A[i])
    #if A[i]==0 or bin(A[i]).count('1')==1:
    #    check.append(i+1)
    #    if i>0:
    #        check.append(i)
#check = list(set(check))

#print(A)
#print(S)
#print(X)
#print(check)

ans = N
for i in range(1, N):
#for s in check:
    j = i + 1
    while S[j]-S[i-1]==X[j]^X[i-1]:
        j += 1
        if j==N+1:
            break
    ans += j - i - 1
    #for j in range(s+1, N+1):
        #print((i,j), S[j]-S[i-1], X[j]^X[i-1])
        #if S[j]-S[s-1]==X[j]^X[s-1]:#xor(i, j):
            #print(s,j)
            #ans += 1
print(ans)


### FIXED CODE ###

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

l = 0 # start index
r = 0 # end index + 1
S = 0 # sum of As
X = 0 # XOR sum of As

ans = 0
while l<N:
    if S==X and r<=N:
        if r<N:
            S += A[r]
            X ^= A[r]
        r += 1
    else:
        S -= A[l]
        X ^= A[l]
        ans += r - l - 1
        l += 1

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

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

def check(K):
    st = []
    for i, a in enumerate(A):
        while st and a < st[-1][0]:
            st.pop()
        u = (i > 0 and A[i-1] >= a)
        if not st:
            st.append([a, u])
            continue
        l = st[-1]
        if l[0] != a:
            st.append([a, u])
            continue
        l[1] += 1
        while st and l[1] == K:
            st.pop(); a -= 1
            if a == 0:
                return 0
            if not st:
                st.append([a, 1])
                break
            l = st[-1]
            if l[0] != a:
                st.append([a, 1])
                break
            l[1] += 1
    return 1

ok = 1
for i in range(N-1):
    if not A[i] < A[i+1]:
        ok = 0
if ok:
    print(1)
    exit(0)

left = 1; right = N+1
while left+1 < right:
    mid = (left + right) // 2
    if check(mid):
        right = mid
    else:
        left = mid
print(right)

### FIXED CODE ###

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

def check(K):
    st = []
    for i, a in enumerate(A):
        #print(K, i, st, a)
        while st and a < st[-1][0]:
            st.pop()
        u = i > 0 and A[i-1] >= A[i]
        if not st:
            st.append([a, u])
            continue
        l = st[-1]
        if l[0] == a:
            l[1] += 1
            while st and l[1] == K:
                st.pop(); a -= 1
                if a == 0:
                    return 0
                if not st:
                    st.append([a, 1])
                    break
                l = st[-1]
                if l[0] == a:
                    l[1] += 1
                else:
                    st.append([a, 1])
                    break
            #print(l, st)
        else:
            st.append([a, u])
    #print(st)
    return 1

ok = 1
for i in range(N-1):
    if not A[i] < A[i+1]:
        ok = 0
if ok:
    print(1)
    exit(0)

left = 1; right = N+1
while left+1 < right:
    mid = (left + right) // 2
    if check(mid):
        right = mid
    else:
        left = mid
print(right)
### BUGGY CODE ###

from heapq import heappop, heappush
xs, ys, xt, yt = map(int, input().split())
N = int(input())
cost = [[0] * (N + 2) for i in range(N + 2)]
D = []
for i in range(N):
    x, y, r = map(int, input().split())
    D.append((x, y, r))
D.append((xs, ys, 0))
D.append((xt, yt, 0))

for i in range(len(D)):
    for j in range(len(D)):
        cost[i][j] = max(0, ((D[i][0] - D[j][0]) ** 2 + (D[i][1] - D[j][1]) ** 2) ** 0.5 - (D[i][2] + D[j][2]))

INF = float('inf')
d = [INF] * (N + 2)
d[N] = 0
que = [(N, 0.0)]
while que:
    v, dist = heappop(que)
    if d[v] < dist:
        continue
    for w in range(N + 2):
        if d[w] > d[v] + cost[v][w]:
            d[w] = d[v] + cost[v][w]
            heappush(que, (w, d[w]))

print(d[N + 1])



### FIXED CODE ###

import sys
from math import sqrt
input = sys.stdin.readline
from heapq import heappop, heappush
xs, ys, xt, yt = map(int, input().split())
N = int(input())
INF = float('inf')
cost = [[INF] * (N + 2) for i in range(N + 2)]
D = [(xs, ys, 0)]
for i in range(N):
    x, y, r = map(int, input().split())
    D.append((x, y, r))
D.append((xt, yt, 0))

for i in range(N + 2):
    for j in range(i + 1, N + 2):
        k = max(0, sqrt((D[i][0] - D[j][0]) ** 2 + (D[i][1] - D[j][1]) ** 2) - D[i][2] - D[j][2])
        cost[i][j] = k
        cost[j][i] = k

visit = [0] * (N + 2)
visit[0] = 1
d = [INF] * (N + 2)
d[0] = 0
que = [(0, 0)]
while que:
    dist, v = heappop(que)
    if d[v] < dist:
        continue
    if v == N + 1:
        print(d[v])
        exit()
    visit[v] = 1
    for w in range(N + 2):
        if visit[w] == 0 and w != v and d[w] > d[v] + cost[v][w]:
            d[w] = d[v] + cost[v][w]
            heappush(que, (d[w], w))
### BUGGY CODE ###

n = int(input())
a = list(input().split())
q = int(input())
b = list(input().split() for i in range(q))

for i in range(q):
    j = b[i][0]
    k = b[i][1]
    if j in a:
        a = [(k if a[i] == j else a[i])for i in range(n)]
        l = [int(i) for i in a]
        print(sum(l))
    else:
        l = [int(i) for i in a]
        print(sum(l))

### FIXED CODE ###

import collections
n = int(input())
a = list(map(int,input().split()))
q = int(input())
l = [list(map(int,input().split())) for i in range(q)]
b,c = [list(i) for i in zip(*l)]
x = collections.Counter(a)
y = sum(a)
for i in range(q):
    if b[i] in x:
        y -= x[b[i]] * b[i]
        y += x[b[i]] * c[i]
        x[c[i]] += x[b[i]]
        x[b[i]] = 0
    print(y)
### BUGGY CODE ###

import collections

def main():
    S = input()
    result = 0
    t = [0]
    for i in range(len(S)):
        t.append((t[-1]+int(S[-i-1])*10**i) % 2019)
    count_dict = collections.Counter(t)
    for a, b in count_dict.items():
        result += b*(b-1) // 2

    print(result)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    S = list(input())
    N = len(S)
    t = 0
    A = [0] * 2019
    A[0] += 1
    d = 1
    for s in reversed(S):
        d *= 10
        d %= 2019
        t += (int(s) * d)
        t %= 2019
        A[t] += 1
    result = sum([a*(a-1)//2 for a in A])
    print(result)


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

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

### FIXED CODE ###

n=int(input())
v=list(map(int,input().split()))
ans=[]
for i in range(n):
    ans.append(v[i])
    a=v[i]+1
    ans.append(a)
    b=v[i]-1
    ans.append(b)
from collections import Counter
data=Counter(ans)
print(data.most_common(1)[0][1])
### BUGGY CODE ###

from collections import deque
N,M,P = map(int,input().split())
INF = 10**18
edge = []
rev_edge = [[] for _ in range(N+1)]
dis = [INF]*(N+1)
dis[1] = 0
for i in range(M):
    A,B,C = map(int,input().split())
    edge.append((A,B,P-C))
    rev_edge[B].append(A)
d = deque()
can_arrive = set()
d.append(N)
while d:
    x = d.popleft()
    can_arrive.add(x)
    for y in rev_edge[x]:
        if not y in can_arrive:
            d.append(y)

for i in range(N):
    update = False
    for j in range(M):
        A,B,cost = edge[j]
        if dis[A] != INF and dis[B] > dis[A]+cost:
            dis[B] = dis[A]+cost
            if B in can_arrive:
                update = True
ans = dis[N]
if update:
    print(-1)
else:
    print(max(0,-ans))

### FIXED CODE ###

from collections import deque
N,M,P = map(int,input().split())
INF = 10**18
edge = []
rev_edge = [[] for _ in range(N+1)]
dis = [INF]*(N+1)
dis[1] = 0
for i in range(M):
    A,B,C = map(int,input().split())
    edge.append((A,B,P-C))
    rev_edge[B].append(A)
d = deque()
can_arrive = set()
d.append(N)
can_arrive.add(N)
while d:
    x = d.popleft()
    for y in rev_edge[x]:
        if not y in can_arrive:
            d.append(y)
            can_arrive.add(y)

for i in range(N):
    update = False
    for j in range(M):
        A,B,cost = edge[j]
        if dis[A] != INF and dis[B] > dis[A]+cost:
            dis[B] = dis[A]+cost
            if B in can_arrive:
                update = True
ans = dis[N]
if update:
    print(-1)
else:
    print(max(0,-ans))
### BUGGY CODE ###

s = int(input())
l = [s]

for i in range(1, 1000000):
    n = l[i - 1]
    if n % 2 == 0:
        l.append(int(n / 2))
    else:
        l.append(int(3 * n + 1))

# print(l[:100])
for i, v in enumerate(l):
    for j in range(i + 1, len(l) - i):
        if l[j] == v:
            print(j + 1)
            exit()

### FIXED CODE ###

s = int(input())
l = [s]

for i in range(1, 1000):
    n = l[i - 1]
    if n % 2 == 0:
        l.append(int(n / 2))
    else:
        l.append(int(3 * n + 1))

# print(l[:100])
for i, v in enumerate(l):
    for j in range(i + 1, len(l) - i):
        if l[j] == v:
            print(j + 1)
            exit()
### BUGGY CODE ###

N = int(input())
a = [int(input()) for _ in range(N)]
ans = 1
now = a[0]

while True:
    if now == 1:
        print(-1)
        break
    if now == 2:
        print(ans)
        break
    now = a[now-1]
    ans += 1

### FIXED CODE ###

N = int(input())
button_list = [int(input()) for i in range(N)]
button =  1
count = 0

while True:
    button = button_list[button-1]
    count += 1
    if button == 2:
        break
    if count == N:
        print(-1)
        exit()
print(count)
### BUGGY CODE ###

n = int(input())
A = list(map(int,input().split()))
L = []
for i in range(n):
  L.append(A[i])
  L.reverse()
for j in range(n):
  print(L[j],end = ' ')

### FIXED CODE ###

n = int(input())
L = list(map(int,input().split()))
if n%2 == 0:
  for i in range(n//2):
    print(L[2*(n//2-i-1)+1],end = ' ')
  for j in range(n//2):  
    print(L[2*j],end = ' ')
else:
  for k in range(n//2+1):
    print(L[2*(n//2-k)],end = ' ')
  for l in range(n//2):
    print(L[2*(l+1)-1],end = ' ')
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Thu May  7 13:25:51 2020

@author: shinba
"""
import sys

S = input()
Q = int(input())
data = [sys.stdin.readline().rstrip().split() for i in range(Q)]

for i in data:
    if i[0] == "1":
        S = S[::-1]
    else:
        if i[1] == "1":
            S = i[2] + S
        else:
            S = S + i[2]

print(S)

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Thu May  7 13:56:40 2020

@author: shinba
"""
import sys
from collections import deque

s = input()
q = int(input())

dq = deque(s)
rev = False

for i in range(q):
    t = sys.stdin.readline().rstrip().split()
    if t[0] == "1":
        rev = not rev
    else:
        if t[1] == "1":
            if rev:
                dq.append(t[2])
            else:
                dq.appendleft(t[2])
        else:
            if rev:
                dq.appendleft(t[2])
            else:
                dq.append(t[2])

s = "".join(list(dq))

if rev:
    print(s[::-1])
else:
    print(s)
### BUGGY CODE ###

n, m = map(int, input().split())
ps_list = [[i for i in input().split()] for j in range(m)]

ac_list = []
wa_list = [0 for i in range(n)]
num_wa = 0
num_ac = 0

for ps in ps_list:
    p = int(ps[0])
    s = ps[1]
    
    if s == 'AC' and p not in ac_list:
        ac_list.append(p)
        num_wa += wa_list[p-1]
        num_ac += 1
    elif p not in ac_list:
        wa_list[p-1] += 1
        
print(num_ac, num_wa)

### FIXED CODE ###

n, m = map(int, input().split())
ps_list = [[i for i in input().split()] for j in range(m)]

ac_list = []
wa_list = [0 for i in range(n)]
num_wa = 0
num_ac = 0

for ps in ps_list:
    p = int(ps[0])
    s = ps[1]
    
    if s == 'AC' and wa_list[p-1] != -1:
        ac_list.append(p)
        num_wa += wa_list[p-1]
        num_ac += 1
        wa_list[p-1] = -1
    elif wa_list[p-1] != -1:
        wa_list[p-1] += 1
        
print(num_ac, num_wa)
### BUGGY CODE ###

#python3
import sys
sys.setrecursionlimit(10**6)
def main():
    n, q = map(int, input().split())
    to = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(lambda x: int(x)-1, input().split())
        to[a].append(b)
        to[b].append(a)

    node = [0 for _ in range(n)]
    for _ in range(q):
        p, x = map(int, input().split())
        p -= 1
        node[p] += x  
    def dfs(v, p=-1):
        for u in to[v]:
            if u == p:
                continue
            else:
                node[u] += node[v]
                dfs(u, v)
    dfs(0)
    for i in range(n):
        if i == n-1:
            print(node[i])
        else:
            print(node[i], end=' ')
main()

### FIXED CODE ###

#python3
from collections import deque 
def main():
    n, q = map(int, input().split())
    to = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(lambda x: int(x)-1, input().split())
        to[a].append(b)
        to[b].append(a)

    node = [0 for _ in range(n)]

    for _ in range(q):
        p, x = map(int, input().split())
        node[p-1] += x

    dq = deque() 
    dq.append(0)
    done = [0 for _ in range(n)]
    done[0] = 1
    while len(dq) > 0:
        x = dq.popleft()
        for i in to[x]:
            if done[i] == 1:
                continue
            node[i] += node[x]
            done[i] = 1 
            dq.append(i)

    for i in range(n):
        print(node[i]) if i == n-1 else print(node[i], end=' ')
main()
### BUGGY CODE ###

import bisect


def main():
    N = int(input())
    P = list(map(int, input().split()))

    ans = 0
    i = N
    for j in range(N):
        if i == 0:
            break
        ans += 1
        m = min(set(P[0:i]))
        i = P.index(m)

    print(ans)

    return 0


if __name__ == '__main__':
    main()

### FIXED CODE ###

import bisect
import numpy as np

def main():
    N = int(input())
    P = list(map(int, input().split()))


    ans = 1
    f = P[0]

    for i in range(1, N):
        f_o = P[i]
        if f >= f_o:
            ans+=1
            f = f_o
    print(ans)
    return 0


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

s=input()
mod=10**9+7
ans=0
dp = [[0]*15 for i in range(100005)]
dp[0][0]=1
for i in range(len(s)):
    keta = len(s)-i-1
    if s[i]=='?':
        for num in range(10):
            amari = num*10**keta
            amari%=13
            for j in range(13):
                dp[i+1][(j+amari)%13]+=dp[i][j]
                dp[i+1][(j+amari)%13]%=mod
    else:
        amari = int(s[i])*10**keta
        amari%=13
        for j in range(13):
            dp[i+1][(j+amari)%13]+=dp[i][j]
            dp[i+1][(j+amari)%13]%=mod

print(dp[len(s)][5])

### FIXED CODE ###

s=input()
mod=10**9+7
dp = [[0]*15 for i in range(100005)]
dp[0][0]=1
for i in range(len(s)):
    keta = len(s)-i-1

    if s[i]=='?':
        nums = range(10)
    else:
        nums = [int(s[i])]
    
    tmp = pow(10,keta,13)
    for num in nums:
        amari = num*tmp%13
        for j in range(13):
            dp[i+1][(j+amari)%13]+=dp[i][j]
            dp[i+1][(j+amari)%13]%=mod

print(dp[len(s)][5])
### BUGGY CODE ###

n=int(input())
a=[int(x) for x in input().split()]
for i in range(1,n+1):
  ans=a.index(i)+1
  print(ans)

  


### FIXED CODE ###

n = int(input())
num_list = list(map(int,input().split()))
num_array = [0]*n
for i in range(n):
    num_array[num_list[i]-1] = i+1
for i in range(n):
    print(num_array[i])
### BUGGY CODE ###

import sys
import math
from fractions import Fraction
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict

MOD = 10**9+7
N = int(input())
dic = defaultdict(int)
gp = []
zero = 0
left_zero = 0
right_zero = 0
for i in range(N):
    a,b = map(int, input().split())
    if b < 0:
        a = -a
        b = -b
    if a == 0 and b != 0:
        left_zero += 1
    elif a != 0 and b == 0:
        right_zero += 1
    elif a == 0 and b == 0:
        zero += 1
    else:
        g = math.gcd(a, b)
        a //= g
        b //= g
        dic[str(Fraction(a, b))] += 1
        gp.append((a, b))
done = defaultdict(bool)
ans = 1
for a,b in gp:
    k = str(Fraction(a, b))
    if done[k]: continue
    rk = str(Fraction(-b, a))
    done[k] = True
    done[rk] = True
    cnt1 = pow(2, dic[k], MOD)-1
    cnt2 = pow(2, dic[rk], MOD)-1
    c = cnt1+cnt2+1
    ans *= c
    ans %= MOD
c1 = pow(2, left_zero, MOD)-1
c2 = pow(2, right_zero, MOD)-1
c = c1+c2+1
ans *= c
ans += zero
ans %= MOD
print((ans-1)%MOD)


### FIXED CODE ###

import sys
import math
from fractions import Fraction
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict

MOD = 10**9+7
N = int(input())
dic = defaultdict(int)
gp = []
zero = 0
left_zero = 0
right_zero = 0
for i in range(N):
    a,b = map(int, input().split())
    if b < 0:
        a = -a
        b = -b
    if a == 0 and b != 0:
        left_zero += 1
    elif a != 0 and b == 0:
        right_zero += 1
    elif a == 0 and b == 0:
        zero += 1
    else:
        g = math.gcd(a, b)
        a //= g
        b //= g
        dic[str(Fraction(a, b))] += 1
        gp.append((a, b))
done = defaultdict(bool)
ans = 1
for a,b in gp:
    k = str(Fraction(a, b))
    if done[k]: continue
    rk = str(Fraction(-b, a))
    done[k] = True
    done[rk] = True
    cnt1 = pow(2, dic[k], MOD)-1
    cnt2 = pow(2, dic[rk], MOD)-1
    c = cnt1+cnt2+1
    ans *= c
    ans %= MOD
c1 = pow(2, left_zero, MOD)-1
c2 = pow(2, right_zero, MOD)-1
c = c1+c2+1
ans *= c
ans += zero
ans %= MOD
print((ans-1)%MOD)
### BUGGY CODE ###

from sys import stdin
import numpy as np
N = list(map(int, (stdin.readline().strip().split())))[0]
M = list(map(int, (stdin.readline().strip().split())))
#M=np.array(M)
c_list=[]
ans=0
for i in range(1,max(M)+1):
    #num=np.count_nonzero(M == i)
    num = M.count(i)
    ans+=(num*(num-1))//2
for k in range(N):
    #num=(np.count_nonzero(M ==M[k]))-1
    num = M.count(M[k])-1
    print(ans-num)

### FIXED CODE ###

from sys import stdin
import numpy as np
N = list(map(int, (stdin.readline().strip().split())))[0]
M = list(map(int, (stdin.readline().strip().split())))
num_list=np.array([0]*(2*10**5+1))
ans=0
for i in M:
    num_list[i-1]+=1
ans=sum(num_list*(num_list-1))//2
for k in range(N):
    num=num_list[M[k]-1]-1
    print(ans-num)
### BUGGY CODE ###

import numpy as np
n,m=map(int,input().split())
r=np.array([list(map(int,input().split())) for _ in range(m)])
start=np.array([1])
done=np.array([1])
ans=np.array([-1]*n)

for _ in range(n-1):
    start_tmp=np.array([])
    for st in start:
        r_st = r[np.any(r==st, axis=1)].flatten()
        r_gl = np.delete(r_st, np.where(r_st == st))
        r_gl = np.setdiff1d(r_gl, done)
        
        start_tmp=np.unique(np.append(start_tmp, r_gl))
        done=np.unique(np.append(done, r_gl))
        #print(r_gl)
        ans[r_gl-1] = st
        
    start = start_tmp
    #print(ans)
    #print(start, done)
    
    if len(done)==n:
        break
    
print('Yes')
print('\n'.join(map(str, ans[1:])))

### FIXED CODE ###

print('Yes')

from collections import deque  

n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]

for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
#print(graph)

ans = [-1] * (n+1)
ans[0] = 0
ans[1] = 0

d = deque()
d.append(1)

while d:
    v = d.popleft()
    for i in graph[v]:
        if ans[i] != -1:
            continue
        ans[i] = v
        d.append(i)

print(*ans[2:], sep="\n")
### BUGGY CODE ###

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

AB = []
for _ in range(M):
    a, b = map(int, input().split())
    AB.append((a, b))

import copy
import collections

fights = AB[:]

fights = sorted(fights)

bridges = []
for a,b in fights:
    bridges.append(
        [x for x in range(a,b)]
    )

ans = 0
while True:
    if not bridges:
        break
    else:
        ans += 1
    
    flat_b = []
    for b in bridges:
        flat_b = flat_b + b

    #print(flat_b)
    max_n = collections.Counter(flat_b).most_common()[0][0]
    
    next_bridges = []
    for b in bridges:
        if max_n in b:
            continue
        else:
            next_bridges.append(b[:])
    bridges = copy.deepcopy(next_bridges)

print(ans)

### FIXED CODE ###

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

AB = []
for _ in range(M):
    a, b = map(int, input().split())
    AB.append((a, b))

fights = AB[:]

fights = sorted(fights, reverse=True)

import bisect


bridges = []
for a,b in fights:
    a_position = bisect.bisect(bridges, a)
    b_position = bisect.bisect(bridges, b)
    
    if a_position == b_position:
        bisect.insort(bridges, a+1)
        #print(bridges)

print(len(bridges))