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

import sys
sys.setrecursionlimit(10**7)
n = int(input())
graph = {i:[] for i in range(n+1)}
for j in range(n-1):
    x, y = [int(i) for i in sys.stdin.readline().split()]
    x -= 1
    y -= 1
    graph[x].append(y)
    graph[y].append(x)

memo_ls = [[None for j in range(2)] for i in range(n+1)]
# i番目の人がj色の時の通り数 0 : 白
cur = 0
def dfs(cur, col, last):
    if memo_ls[cur][col] is not None:
        return memo_ls[cur][col]
    next_col_num = 1 if col == 1 else 2
    _sum = 1
    cnt = 0
    for _next in graph[cur]:
        if _next == last:
            continue
        cnt += 1
        res = 0
        for next_col in range(next_col_num):
            res += dfs(_next, next_col, cur)
        _sum *= max(1, res)
    if cnt == 0:
        memo_ls[cur][col] = 1
        return 1
    res = _sum % (10 ** 9 + 7)
    memo_ls[cur][col] = res
    return res
res = dfs(0,0,-1) + dfs(0,1,-1)
print(res % (10**9+7))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
n = int(input())
graph = {i:[] for i in range(n+1)}
for j in range(n-1):
    x, y = [int(i) for i in sys.stdin.readline().split()]
    x -= 1
    y -= 1
    graph[x].append(y)
    graph[y].append(x)

memo_ls = [[None for j in range(2)] for i in range(n+1)]
# i番目の人がj色の時の通り数 0 : 白
cur = 0
def dfs(cur, col, last):
    if memo_ls[cur][col] is not None:
        return memo_ls[cur][col]
    next_col_num = 1 if col == 1 else 2
    _sum = 1
    cnt = 0
    for _next in graph[cur]:
        if _next == last:
            continue
        cnt += 1
        res = 0
        for next_col in range(next_col_num):
            res += dfs(_next, next_col, cur)
        _sum *= max(1, res)
    if cnt == 0:
        memo_ls[cur][col] = 1
        return 1
    res = _sum % (10 ** 9 + 7)
    memo_ls[cur][col] = res
    return res
res = dfs(0,0,-1) + dfs(0,1,-1)
print(res % (10**9+7))
### BUGGY CODE ###

n,W = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
inf = float('INF')
bag = [inf for _ in range(10**5+1)]
bag[0] = 0

ans = 0
for w,v in a:
  for i in range(min(v,10**5+1), 10**5+1)[::-1]:
    if bag[i-v] + w < min(bag[i],W+1):
        bag[i] = bag[i-v] + w
        ans = max(ans, i)
print(ans)


### FIXED CODE ###

n,W = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
inf = float('INF')
bag = [inf for _ in range(10**5+1)]
bag[0] = 0

ans = 0
for w,v in a:
  for i in range(min(v,10**5+1), 10**5+1)[::-1]:
    if bag[i-v] + w < min(bag[i],W+1):
        bag[i] = bag[i-v] + w
        ans = max(ans, i)
print(ans)
### BUGGY CODE ###

N = int(input())
A = []
B = []
for i in range(N):
	A.append(int(input()))
	
for i in range(len(A)):
	B = A[:]
	B.pop(i)
	print(max(B))


### FIXED CODE ###

N = int(input())
A = []
B = []
for i in range(N):
	A.append(int(input()))
	
max_1 = max(A)
B = A[:]
B.remove(max_1)
max_2 = max(B)

for i in A:
	if i == max_1:
		print(max_2)
	else:
		print(max_1)
### BUGGY CODE ###

L, R = map(int, input().split())
mod = 2018


for i in range(L, R):
    for j in range(i + 1, R + 1):
        mod = min(i * j % 2019, mod)
        if mod == 0:
            break

print(mod)

### FIXED CODE ###

L, R = map(int, input().split())

L_q = L // 2019
R_q = R // 2019
mod = 2018

if L_q + R_q == 0:
    for i in range(L, R):
        for j in range(i + 1, R + 1):
            mod = min(i * j % 2019, mod)

    print(mod)

else:
    if R_q - L_q > 1:
        print(0)

    else:
        for i in range(L, R):
            for j in range(i + 1, R + 1):
                mod = min(i * j % 2019, mod)

        print(mod)
### BUGGY CODE ###

n = int(input())
str_list = []

for _ in range(n):
    cmd,input_str = input().split()
    if   cmd == 'insert':
        str_list.append(input_str)
    elif cmd == 'find':
        if input_str in str_list:
            print('yes')
        else:
            print('no')
    


### FIXED CODE ###

n = int(input())
dic = {}
ans_list = []

for i in range(n):
    cmd,num = input().split()
    if   cmd == 'insert':
        dic[num] = i
    elif cmd == 'find':
        if dic.__contains__(num):
            ans_list.append('yes')
        else:
            ans_list.append('no')

for ans in ans_list:
    print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
h = [int(input()) for i in range(N)]

# 小さい順にソートする
def sort(h):
    if len(h) <= 1:
        return h
    base = h[-1]
    low_temp = [];
    high_temp = [];
    base_count = 1
    for i in range(len(h)-1):
        if h[i] < base:
            low_temp.append(h[i])
        elif h[i] > base:
            high_temp.append(h[i])
        else:
            base_count += 1
    low = sort(low_temp)
    high = sort(high_temp)
    return low + [base]*base_count + high

h = sort(h)
hantei = 10**10
for i in range(N-K+1):
    temp = h[i:i+K]
    temp_dif = max(temp) - min(temp)
    if temp_dif < hantei:
        hantei = temp_dif

print(hantei)


### FIXED CODE ###

N, K = map(int, input().split())
h = [int(input()) for i in range(N)]
h.sort()
print(min(h[i+K-1] - h[i] for i in range(N-K+1)))
### BUGGY CODE ###

import math

def wa(a,bl):
    if min(bl)>a:
        return math.factorial(len(bl))*a
    if len(bl)==1:
        return a%bl[0]
    else:
        re=0
        for b in bl:
            re+=wa(a%b,list(set(bl)^set([b])))
        return re

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

print(wa(a,bl)%(10**9+7))


### FIXED CODE ###

from bisect import bisect_right
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class mint:
    def __init__(self, x):
        self.__x = x % md

    def __repr__(self):
        return str(self.__x)

    def __neg__(self):
        return mint(-self.__x)

    def __add__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x + other)

    def __sub__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x - other)

    def __rsub__(self, other):
        return mint(other - self.__x)

    def __mul__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * other)

    __radd__ = __add__
    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * pow(other, md - 2, md))

    def __rtruediv__(self, other):
        return mint(other * pow(self.__x, md - 2, md))

    def __pow__(self, power, modulo=None):
        return mint(pow(self.__x, power, md))

md = 10**9+7

def main():
    n,x=MI()
    ss=LI()
    ss.sort()
    dp=[0]*(x+1)
    dp[x]=mint(1)
    for i in range(x,0,-1):
        pre=dp[i]
        if pre==0:continue
        mxj=bisect_right(ss,i)
        for j in range(mxj):
            dp[i%ss[j]]+=pre/mxj

    ev=sum(dp[i]*i for i in range(ss[0]))
    fac=mint(1)
    for i in range(1,n+1):fac*=i
    print(ev*fac)

main()
### BUGGY CODE ###

Q = int(input())
lr = [list(map(int, input().split())) for _ in range(Q)]
prime = [True] * (10**5)
prime[0] = prime[1] = False
for i in range(2, int((10**5)**0.5) + 1):
    if prime[i]:
        for j in range(i*2, 10**5, i):
            prime[j] = False
for l, r in lr:
    result = 0
    for i in range(l, r+1, 2):
        if prime[i] and prime[(i+1)//2]:
            result += 1
    print(result)

### FIXED CODE ###

Q = int(input())
lr = [list(map(int, input().split())) for _ in range(Q)]
n=10**5 + 1
prime = [True] * (n)
prime[0] = prime[1] = False
for i in range(2, int((n)**0.5) + 1):
    if prime[i]:
        for j in range(i*2, n, i):
            prime[j] = False
counter = 0
work = [0] * (n)
for i in range(2, n):
    if prime[i] and prime[(i+1)//2]:
        counter += 1
    work[i] = counter
for l, r in lr:
    print(work[r] - work[l-1])
### BUGGY CODE ###

N = int(input())
rabit = input().split(" ")
skip = []
num = 0

for i in range(N):
  n = int(rabit[i])
  if i in skip:
    continue
  if int(rabit[n-1]) == i+1:
    skip.append(n-1)
    num += 1

print(num)

### FIXED CODE ###

N = int(input())
rabit = input().split(" ")
skip = []
num = 0

for i in range(N):
  n = int(rabit[i])
  if n < i+1:
    continue
  if int(rabit[n-1]) == i+1:
    num += 1

print(num)
### BUGGY CODE ###

s=input()
N=len(s)
t=input()
M=len(t)

alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
def al(str):
    return alphabetlist.index(str)+1

dp=[[0 for i in range(0,M)] for i in range(0,N)]

firsts=N
for i in range(0,N):
    if s[i]==t[0]:
        firsts=i
        break

firstt=M
for i in range(0,M):
    if t[i]==s[0]:
        firstt=i
        break

for i in range(0,N):
    if i>=firsts:
        dp[i][0]=al(t[0])

for i in range(0,M):
    if i>=firstt:
        dp[0][i]=al(s[0])

for i in range(1,N):
    for j in range(1,M):
        if s[i]==t[j]:
            dp[i][j]=dp[i-1][j-1]*27+al(s[i])
        else:
            if dp[i][j-1]>dp[i-1][j]:
                dp[i][j]=dp[i][j-1]
            else:
                dp[i][j]=dp[i-1][j]

a=dp[N-1][M-1]
ans=[]
while a!=0:
    i=a%27
    ans.append(alphabetlist[i-1])
    a//=27

ans=ans[::-1]
print(''.join(ans))

### FIXED CODE ###

s=input()
N=len(s)
t=input()
M=len(t)

alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
def al(str):
    return alphabetlist.index(str)+1

dp=[[0 for i in range(0,M+1)] for i in range(0,N+1)]

for i in range(0,N):
    for j in range(0,M):
        if s[i]==t[j]:
            dp[i+1][j+1]=dp[i][j]+1
        else:
            if dp[i+1][j]>dp[i][j+1]:
                dp[i+1][j+1]=dp[i+1][j]
            else:
                dp[i+1][j+1]=dp[i][j+1]

ans=[]
i=N
j=M
while i>0 and j>0:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        ans.append(s[i-1])
        i-=1
        j-=1

ans=ans[::-1]
print(''.join(ans))
### BUGGY CODE ###

N, Q = map(int, input().split())
S = list(input())
cnt = [0] * (N - 1)

for i in range(N - 1):
    if S[i] + S[i + 1] == 'AC':
        cnt[i] = 1

for _ in range(Q):
    l, r = map(int, input().split())
    ans = sum(cnt[l - 1:r - 1])
    print(ans)

### FIXED CODE ###

N, Q = map(int, input().split())
S = list(input())
cnt = [0] * (N)

for i in range(1, N):
    if S[i - 1] + S[i] == 'AC':
        cnt[i] = cnt[i - 1] + 1
    else:
        cnt[i] = cnt[i - 1]

for _ in range(Q):
    l, r = map(int, input().split())
    ans = cnt[r - 1] - cnt[l - 1]
    print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
a = 1
for i in range(N):
    a *= A[i]
print(a if a<=10**18 else -1)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
a = 1
for i in range(N):
    a *= A[i]
    if a>10**18:
        print(-1)
        exit()
print(a)
### BUGGY CODE ###

import sys
def SI(): return sys.stdin.readline().strip()

def main():
    s = SI()
    t = SI()

    d = {}
    for i, c in enumerate(s):
        if c not in d.keys():
            d[c] = [i]
        else:
            d[c].append(i)

    import collections
    didx = collections.defaultdict(int)

    keys = d.keys()
    for c in set(t):
        if c not in keys:
            print(-1)
            return

    import bisect

    i_loop = 0
    currentidx = -1
    for c in t:
        # 次の文字を読む
        poslist = d[c]

        if len(poslist) <= didx[c]:
            # 文字を取り切っている場合は次のループに
            i_loop += 1
            didx = collections.defaultdict(int)
            currentidx = poslist[0]
            didx[c] += 1
        else:
            # とり切っていない場合
            poslist_afteridx = poslist[didx[c]:]
            posidx = bisect.bisect_right(poslist_afteridx, currentidx)

            if posidx >= len(poslist_afteridx):
                # とれないなら次のループでとったことにする
                i_loop += 1
                didx = collections.defaultdict(int)
                currentidx = poslist[0]
                didx[c] += 1
            else:
                # 同じループでとれるなら取って、現在位置を更新
                pos = poslist_afteridx[posidx]
                currentidx = pos
                didx[c] = posidx + 1

    print(len(s)*i_loop + currentidx + 1)

main()

### FIXED CODE ###

import sys
def SI(): return sys.stdin.readline().strip()

def main():
    s = SI()
    t = SI()

    import collections
    d = collections.defaultdict(list)
    for i, c in enumerate(s):
        d[c].append(i)

    keys = d.keys()
    for c in set(t):
        if c not in keys:
            print(-1)
            return

    import bisect

    i_loop = 0
    currentidx = -1
    for c in t:
        # 次の文字を読む
        poslist = d[c]

        # とり切っていない場合
        posidx = bisect.bisect_right(poslist, currentidx)

        if posidx >= len(poslist):
            # とれないなら次のループでとったことにする
            i_loop += 1
            currentidx = poslist[0]
        else:
            # 同じループでとれるなら取って、現在位置を更新
            pos = poslist[posidx]
            currentidx = pos

    print(len(s)*i_loop + currentidx + 1)

main()
### BUGGY CODE ###

n, m = map(int, input().split())
a = []
dp = [0]
mod = 10**9+7

for i in range(m):
    a.append(int(input()))

if 1 in a and 2 in a:
    dp.append(0)
    dp.append(0)
elif 1 in a and 2 not in a:
    dp.append(0)
    dp.append(1)
elif 1 not in a and 2 in a:
    dp.append(1)
    dp.append(0)
else:
    dp.append(1)
    dp.append(2)

for i in range(3, n+1):
    if i in a:
        dp.append(0)
    else:
        dp.append((dp[i-1] + dp[i-2]) % mod)

print(dp[n])






### FIXED CODE ###

n, m = map(int, input().split())
a = []
# dp = [0]*(n+1)
dp = [None]*(10**5+1)
mod = 10**9+7
dp[0] = 0

for i in range(m):
    ng = int(input())
    a.append(ng)
    dp[ng] = 0

if 1 in a and 2 in a:
    print(0)
    exit()
elif 1 in a and 2 not in a:
    dp[1] = 0
    dp[2] = 1
elif 1 not in a and 2 in a:
    dp[1] = 1
    dp[2] = 0
else:
    dp[1] = 1
    dp[2] = 2

for i in range(3, n+1):
    if dp[i] is None:
        dp[i] = (dp[i-1] + dp[i-2]) % mod

print(dp[n])
### BUGGY CODE ###

import sys
# import math
# import queue
# import copy
# import bisect#2分探索


def input():
    return sys.stdin.readline()[:-1]
def inputi():
    return int(input())

K=inputi()
vals=[float('inf')]*K
visit=[]
vals[1]=0
q=[1]
flag=False
while len(q)>0:
    s=q.pop(0)
    vs=vals[s]
    if s==0:
        print(vs+1) 
        flag=True
        break
    #visit.append(s)
    s0=(10*s)%K

    if vs<vals[s0]:
        vals[s0]=vs
        q.insert(0,s0)
    s1=(s+1)%K

    if vs+1<vals[s1]:
        vals[s1]=vs+1
        q.append(s1)
    #print(q,s,s0,s1,vals)

#if flag==False:
#    print(vals[0]+1)


### FIXED CODE ###

import sys
# import math
# import queue
# import copy
# import bisect#2分探索
from collections import deque


def input():
    return sys.stdin.readline()[:-1]
def inputi():
    return int(input())

K=inputi()
vals=[10**5+1]*K
visit=[]
vals[1]=0
q = deque([1])
flag=False
while len(q)>0:
    s=q.popleft()
    vs=vals[s]
    if s==0:
        print(vs+1) 
        flag=True
        break
    #visit.append(s)
    s0=(10*s)%K

    if vs<vals[s0]:
        vals[s0]=vs
        q.appendleft(s0)
    s1=(s+1)%K

    if vs+1<vals[s1]:
        vals[s1]=vs+1
        q.append(s1)
    #print(q,s,s0,s1,vals)

#if flag==False:
#    print(vals[0]+1)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
i=0
ans=0
while(i<len(a)):
    if a[i]==i+1:
        i+=1
    else:
        a.pop(i)
        ans+=1
print(ans if ans!=n else -1)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
p=ans=0
for i in range(1,n+1):
    for j in range(p,n):
        if i==a[j]:
            p=j
            break
    else:
        ans=i-1
        break
else:
    ans=n
print(n-ans if ans>0 else -1)
### BUGGY CODE ###

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

if abs(A-B) > 10**(18):
    print("Unfair")
else:
    for i in range(K):
        a = B+C
        b = A+C
        c = A+B
        A = a
        B = b
        C = c
print(A-B)

### FIXED CODE ###

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

if abs(A-B) > 10**(18):
    print("Unfair")
elif K%2 == 0:print(A-B)
elif K%2 == 1:print(B-A)
### BUGGY CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
def score(A,N,K):
    s=1
    for i in range(N-K+1,N+1):
        s*=A[i]
    return s

for i in range(K-1,N-1):
    a=score(A,i,K)
    b=score(A,i+1,K)
    if(a<b):
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

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

for i in range(K-1,N-1):
    a=A[i-K+1]
    b=A[i+1]
    if(a<b):
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

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

ab_list = [0]*n

for i in range(n):
    ab_list[i] = list(map(int, input().split()))

ma_list = [0]*h

for i in range(h):
    ma_list[i] = 10000000000
    for item in ab_list:
        ma = 0
        if item[0] >= (i + 1):
            ma = item[1]
        else:
            ma = item[1] + ma_list[i - item[0]]
        if ma_list[i] > ma:
            ma_list[i] = ma

print(ma_list[-1])


### FIXED CODE ###

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

ab_list = [0]*n

for i in range(n):
    ab_list[i] = list(map(int, input().split()))

ma_list = [0]*h

for i in range(h):
    ma_list[i] = 10000000000
    for item in ab_list:
        ma = 0
        if item[0] >= (i + 1):
            ma = item[1]
        else:
            ma = item[1] + ma_list[i - item[0]]
        if ma_list[i] > ma:
            ma_list[i] = ma

print(ma_list[-1])
### BUGGY CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[5]:


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


# In[7]:


ans = 0
for x in range(N-2):
    a = L[x]
    for y in range(x+1,N-1):
        b = L[y]
        for z in range(y+1,N):
            c = L[z]
            if a<b+c and b<c+a and c<a+b:
                ans += 1
print(ans)


# In[ ]:






### FIXED CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[9]:


import bisect


# In[10]:


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


# In[11]:


s_L = sorted(L)
ans = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        ans += bisect.bisect_left(s_L,s_L[i]+s_L[j])-j-1
print(ans)


# In[ ]:
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from bisect import bisect

def main():
    N, Q = LI()
    XST = []
    for _ in range(N):
        s, t, x = LI()
        s -= x
        t -= x
        XST.append([x, s, t])
    D = []
    for _ in range(Q):
        D.append(II())
    ts = []
    for x, s, t in XST:
        ts.append(s)
        ts.append(t)
    ts.sort()
    ts.append(INF)
    xs = [INF] * (N * 2 + 1)
    XST.sort(reverse=True)
    for x, s, t in XST:
        s0 = bisect(ts, s)
        t0 = bisect(ts, t)
        for i in range(s0, t0):
            xs[i] = x
    for d in D:
        y = bisect(ts, d)
        y = xs[y]
        if y == INF:
            y = -1
        print(y)
    return

main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from bisect import bisect_left

def main():
    N, Q = LI()
    XST = []
    for _ in range(N):
        s, t, x = LI()
        s -= x
        t -= x
        XST.append([x, s, t])
    D = []
    for _ in range(Q):
        D.append(II())
    ans = [-1] * Q
    nexts = [-1] * Q
    XST.sort()
    for x, s, t in XST:
        i = bisect_left(D, s)
        end = bisect_left(D, t)
        while i < end:
            if nexts[i] == -1:
                ans[i] = x
                nexts[i] = end
                i += 1
            else:
                i = nexts[i]
    for y in ans:
        print(y)
    return

main()
### BUGGY CODE ###

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

  def CalExVal(x):
      return (1/2*(x+1))
  Ex = list(map(CalExVal, A))
  temp = len(A)-K + 1
  #adjlist = [0]*(temp)
  adjlist = [sum(Ex[i:(K+i)]) for i in range(temp)]
  #for i in range(temp):
  #    adjlist[i] = sum(Ex[i:(K+i)])

  print(max(adjlist))
main()

### FIXED CODE ###

def main():
  def CalExVal(x):
    return (1/2*(x+1))
  N, K = map(int, input().split())
  A = list(map(int, input().split()))


  Ex = list((map(CalExVal, A)))
  #temp = len(A)-K + 1
  #adjlist = [0]*(temp)
  #adjlist = [sum(list(map(CalExVal, A))[i:(K+i)]) for i in range(temp)]
  tem = sum(Ex[:K])
  res = tem
  for i in range(0,N-K):
      tem = tem - Ex[i] + Ex[i+K]
      if res < tem:
      	res = tem
  print(res)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n = int(input())
power = 1
for i in range(1,n + 1):
    power *= i
print(power % (10**9 + 7))

### FIXED CODE ###

import math
n = int(input())
power = math.factorial(n)
print(power % (10**9 + 7))
### BUGGY CODE ###

s = input()
n = len(s) 
ls = [0]*2019
ls[0]+=1

r = 0
for i in range(n-1,-1,-1):
  r += int(s[i]) * (10**(n-i-1))
  r %= 2019
  ls[r] += 1

ans = 0
for a in ls:
  ans += a*(a-1)//2
print(ans)
       

### FIXED CODE ###



s = input()
n = len(s) 

rs = [1]*n
for i in range(1,n):
  rs[i] = rs[i-1]*10 %2019
  
ls = [0]*2019
ls[0]+=1

r = 0
for i in range(n-1,-1,-1):
  r += int(s[i]) * (rs[n-i-1])
  r %= 2019
  ls[r] += 1

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

N, M = map(int, input().split())
g = {}
for i in range(M):
  a, b = map(int, input().split())
  if a in g.keys():
    g[a].append(b)
  else:
    g[a] = [b]
  if b in g.keys():
    g[b].append(a)
  else:
    g[b] = [a]
ans = [0 for _ in range(N+1)]
#print(g)
tmp = [1]
while 0 in ans[2:]:
  #print(ans)
  for i in tmp:
    #print('i',i)
    next = g[i]
    #print('next',next)
    for j in next:
      if ans [j] == 0:
        ans[j] = i
  tmp = 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])