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

N, M = map(int,input().split())
L1 = [set() for k in range(N+1)]
for k in range(M):
	u, v = map(int, input().split())
	L1[u].add(v)
S, T = map(int, input().split())
L2 = [None for k in range(N+1)]
L3 = [None for k in range(N+1)]
for n in range(N+1):
	a = set()
	for l in L1[n]:
		a = a.union(L1[l])
	L2[n] = a
	a = set()
	for l in L2[n]:
		a = a.union(L1[l])
	a.discard(n)
	L3[n] = a
t = 0
sumi = set([S])
now = set([S])
flg = 0
while(len(now) != 0):
	t +=1
	for d in now:
		now = now.union(L3[d])
	now = now - sumi
	sumi = sumi.union(now)
	if set([T]) <= sumi:
		print(t)
		flg = 1
		now = set()
if flg == 0:
	print(-1)

### FIXED CODE ###

N, M = map(int,input().split())
L1 = [[] for k in range(3*(N+1))]
for k in range(M):
	u, v = map(int, input().split())
	L1[3*u].append(3*v+1)
	L1[3*u+1].append(3*v+2)
	L1[3*u+2].append(3*v)
S, T = map(int, input().split())
S = 3*S
T = 3*T

t = 0
sumi = [None for k in range(3*(N+1))]
sumi[T] = -1
now = [S]
flg = 0
while(len(now) != 0):
	t += 1
	pre = []
	for n in now:
		pre.extend(L1[n])
	now = []
	for p in pre:
		if sumi[p] == None:
			sumi[p] = t
			now.append(p)
		elif sumi[p] == -1:
			flg = 1
	if flg == 1:
		print(t//3)
		flg = 2
		break
if flg == 0:
	print(-1)
### BUGGY CODE ###

n=int(input())
A=list(map(int,input().split()))
mod = 10**9+7;ans=0
for i in range(60):
  cnt=0
  for a in A: cnt+=a>>i&1
  cnt=cnt*(n-cnt)%mod
  cnt=2**i*cnt%mod
  ans+=cnt
print(ans%mod)

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
mod = 10**9+7;ans=0
for i in range(60):
  cnt=sum([1 for a in A if a>>i&1]) 
  cnt=cnt*(n-cnt)%mod
  cnt=2**i*cnt%mod
  ans+=cnt
print(ans%mod)
### BUGGY CODE ###

n= int(input())
s= [input() for i in range(n)]
p=set(s)
p1=list(p)
N=len(p)
c=[0]*N
for i in range(N):
	c[i]=s.count(p1[i])
m =max(c)
c1=c.count(m)
ans =[]
for i in range(N):
	if c[i]==m:
		ans.append(p1[i])
ans1 = sorted(ans)
for i in range(c1):
	print(ans1[i])

### FIXED CODE ###

n= int(input())
s= sorted([input() for i in range(n)])
s.append("END")
ans=[]
max=-1
past=s[0]
c=1
for i in range(1,n+1):
	if past==s[i]:
		c+=1
	else:
		if c>max:
			max=c
			ans=[]
			ans.append(s[i-1])
		elif c==max:
			ans.append(s[i-1])
		c=1
	past=s[i]
for i in range(len(ans)):
	print(ans[i])
### BUGGY CODE ###

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

    r = list(range(N - 2, -1, -1))
    result = 0
    for b in range(60):
        t = 0
        bs = (A[N - 1] >> b) & 1
        for i in r:
            if (A[i] >> b) & 1 == 0:
                t += bs
            else:
                t += (N - (i + 1)) - bs
                bs += 1
        result = (result + t * (1 << b)) % 1000000007
    print(result)
main()


### FIXED CODE ###

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

    r = list(range(N - 2, -1, -1))
    result = 0
    for b in range(60):
        t = 0
        bs = (A[N - 1] >> b) & 1
        for i in r:
            if (A[i] >> b) & 1 == 0:
                t += bs
            else:
                t += (N - (i + 1)) - bs
                bs += 1
        result = (result + t * (1 << b)) % 1000000007
    print(result)
main()
### BUGGY CODE ###

import time
from array import array

def solve(i, m):
    if m == 0:
        return True
    if i >= n:
        return False
    return solve(i+1, m) or solve(i+1, m-A[i])

if __name__ == '__main__':
    n = int(raw_input())
    A = array('I', map(int, raw_input().split()))
    q = int(raw_input())
    m = array('I', map(int, raw_input().split()))

    start = time.time()
    for m_i in m:
        print "yes" if solve(0, m_i) else "no"
    end = time.time()
    #print end - start

### FIXED CODE ###

def sequence(A, n):
    dic = {}
    
    def solve(i, m):
        if (i, m) in dic:
            return dic[(i, m)]
        if m == 0:
            dic[(i, m)] = True
        elif i >= n:
            dic[(i, m)] = False
        elif solve(i+1, m):
            dic[(i, m)] = True
        elif solve(i+1, m-A[i]):
            dic[(i, m)] = True
        else:
            dic[(i, m)] = False
        return dic[(i, m)]
    
    return solve

if __name__ == '__main__':
    n = int(raw_input())
    A = map(int, raw_input().split())
    q = int(raw_input())
    m = map(int, raw_input().split())

    solve = sequence(A, n)
    for m_i in m:
        print "yes" if solve(0, m_i) else "no"
### BUGGY CODE ###

n, m = map(int, input().split())
ab_list = [0] * m
for i in range(m):
	ab_list[i] = list(map(int, input().split()))
a_list = []
b_list = []
for i in ab_list:
	if i[0] == 1:
		a_list.append(i[1])
	elif i[1] == n:
		b_list.append(i[0])
r = 'IMPOSSIBLE'
for a in a_list:
	if a in b_list:
		r = 'POSSIBLE'
		break
print(r)

### FIXED CODE ###

n, m = map(int, input().split())
ab_list = [0] * m
for i in range(m):
	ab_list[i] = list(map(int, input().split()))
a_list = []
b_list = []
for i in ab_list:
	if i[0] == 1:
		a_list.append(i[1])
	elif i[1] == n:
		b_list.append(i[0])
r = 'POSSIBLE' if set(a_list) & set(b_list) else 'IMPOSSIBLE'
print(r)
### BUGGY CODE ###

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

max_num = 0
for i in range(N+1-K):
  max_num = max(max_num, sum(numbers[i:i+K]))
    
answer = (max_num + K) / 2
print(answer)


### FIXED CODE ###

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

mx = sum(p[:K])
cur = mx
for i in range(N-K):
  cur = cur-p[i]+p[i+K]
  mx = max(mx, cur)
  
ans = (mx+K) / 2
print(ans)
### BUGGY CODE ###

from collections import Counter
import sys
N, K = map(int, input().split())
a_lis = [int(_) for _ in input().split()]
count = 0
counter = sorted(Counter(a_lis).items(), key=lambda x: x[1])
while len(counter) > K:
    count += counter[0][1]
    del counter[0]
    if len(counter) == K:
        print(count)
        sys.exit()
print(0)

### FIXED CODE ###

from collections import Counter
import sys
N, K = map(int, input().split())
a_lis = [int(_) for _ in input().split()]

counter = sorted(Counter(a_lis).items(), key=lambda x: x[1])

if len(counter) > K:
    ans_list = counter[:len(counter) - K]
    count = sum([item[1] for item in ans_list])
    print(count)
    sys.exit()

print(0)
### BUGGY CODE ###

H, W, K = map(int, input().split())
S = [list(map(int, input())) for _ in range(H)]

sum_tab = [[0] for _ in range(H)]
for i in range(H):
    sum_tmp = 0
    for j in range(W):
        sum_tmp += S[i][j]
        sum_tab[i].append(sum_tmp)

ans = 1000000007
for case in range(1 << (H - 1)):
    t = 0
    divs = []
    case_tmp = case
    for i in range(1, H):
        if case_tmp % 2 > 0:
            divs.append((t, i))
            t = i
        case_tmp >>= 1
    else:
        divs.append((t, H))
    #
    # print("#", divs)
    ans_tmp = len(divs) - 1
    l = 0
    for x in range(W):
        cnt_max = 0
        for y_str, y_end in divs:
            cnt_tmp = sum([sum_tab[y][x + 1] - sum_tab[y][l] for y in range(y_str, y_end)])
            cnt_max = max(cnt_tmp, cnt_max)
        #
        if cnt_max > K:
            ans_tmp += 1
            # print("##", cnt_max, x)
            l = x
    #
    ans = min(ans, ans_tmp)

print(ans)

### FIXED CODE ###

H, W, K = map(int, input().split())
S = [list(map(int, list(input()))) for _ in range(H)]

tab_h = [[0] * (W + 1) for _ in range(H)]
for i in range(H):
    cnt = 0
    for j in range(W):
        cnt += S[i][j]
        tab_h[i][j + 1] = cnt

# tab_v = [[0] * (H + 1) for _ in range(W)]
# for j in range(W):
#     cnt = 0
#     for i in range(H):
#         cnt += S[i][j]
#         tab_v[i + 1][j] = cnt

ans = 1000000007
for case in range(2 ** (H - 1)):
    case_tmp = case
    iscut_v = []
    for i in range(H - 1):
        iscut_v.append(case_tmp % 2)
        case_tmp >>= 1
    #
    parts = []
    vsrc = 0
    for vdst in range(1, H + 1):
        if vdst == H:
            parts.append((vsrc, vdst))
            break
        elif iscut_v[vdst - 1] == 1:
            parts.append((vsrc, vdst))
            vsrc = vdst
        else:
            continue
    #
    possible = False
    hsrc = 0
    iscut_h = [0] * (W - 1)
    for hdst in range(1,  W + 1):
        num_1 = 0
        for vsrc, vdst in parts:
            num_1_tmp = 0
            for i in range(vsrc, vdst):
                num_1_tmp += tab_h[i][hdst] - tab_h[i][hsrc]
            num_1 = max(num_1, num_1_tmp)
            # print("##", hdst, (vsrc, vdst), num_1_tmp)
        #
        if num_1 > K:
            if hdst == 1 or hdst - 1 == hsrc:
                break
            else:
                iscut_h[hdst - 2] = 1
                hsrc = hdst - 1
        else:
            continue
    else:
        possible = True
    #
    if possible:
        ans_tmp = sum(iscut_v) + sum(iscut_h)
        # print("#", iscut_v, iscut_h, ans_tmp)
        ans = min(ans, ans_tmp)

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

import sys
sys.setrecursionlimit(10 ** 7)

N = int(input())
edge = [[] for _ in range(N)]
for lose in range(1, N):
    win = int(input())
    edge[win - 1].append(lose)

def dfs(n):
    """ nを根とする木の深さ """
    if not edge[n]:
        return 0
    
    que = []
    for v in edge[n]:
        que.append(dfs(v))

    que.sort(reverse=True)
    
    res = 0
    for plus, depth in enumerate(que, 1):
        # 今までの深さ + どれくらい深くするか
        res = max(res, depth + plus)
    
    return res

print(dfs(0))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
from heapq import heappop, heappush

N = int(input())
edge = [[] for _ in range(N)]
for node in range(1, N):
    a = int(input())
    edge[a-1].append(node)

def dfs(n):
    if not edge[n]:
        return 0
    
    que = []
    for v in edge[n]:
        heappush(que, (-1) * dfs(v))

    ans = 0
    for i in range(len(edge[n])):
        ans = max(ans, (-1) * heappop(que) + i + 1)
    
    return ans

print(dfs(0))
### BUGGY CODE ###

import itertools

x,y,z,K = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))

#a.sort(reverse=True)
#b.sort(reverse=True)
#c.sort(reverse=True)

r = [i+j for i,j in list(itertools.product(a, b))]
r.sort(reverse=True)

r = [i+j for i,j in list(itertools.product(r[0:min(3001,x*y*z)], c))]
r.sort(reverse=True)

for i in range(K):
    print(r[i])

### FIXED CODE ###

x,y,z,k = map(int,input().split())
lisa = list(map(int,input().split()))
lisb = list(map(int,input().split()))
lisc = list(map(int,input().split()))
lisa.sort(reverse=True)
lisb.sort(reverse=True)
lisc.sort(reverse=True)
an = []
ans = []
for num in lisb:
    for nu in lisa:
        an.append(num+nu)
an.sort(reverse=True)
an = an[:min(3001,x*y*z+1)]
for num in lisc:
    for nu in an:
        ans.append(num+nu)
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])
### BUGGY CODE ###

import fractions as m

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

gstackl = [0]
gstackr = [0]

ans = 0

for i in range(0, n):
	gstackl.append(m.gcd(gstackl[i], al[i]))

for i in reversed(range(1, n)):
	gstackr = [m.gcd(gstackr[0], al[i])] + gstackr

gstackr.append(0)

#print(gstackl)
#print(gstackr)

for i in range(n):
	l = gstackl[i]
	r = gstackr[i]
	#print("{} {}".format(l, r))
	a = m.gcd(l, r)
	#print(a)
	if a > ans:
		ans = a

print(ans)

### FIXED CODE ###

import fractions as m

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

gstackl = [0]*n
gstackr = [0]*n

ans = 0

for i in range(1, n):
	gstackl[i] = m.gcd(gstackl[i-1], al[i-1])
	gstackr[n-i-1] = m.gcd(gstackr[n-i], al[n-i])

#print(gstackl)
#print(gstackr)

for i in range(n):
	l = gstackl[i]
	r = gstackr[i]
	#print("{} {}".format(l, r))
	a = m.gcd(l, r)
	#print(a)
	if a > ans:
		ans = a

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

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

for _ in range(q):
    operation = input()
    if (operation[0] == '1'):
        s = s[::-1]
    else:
        if (operation[2] == '1'):

            s = operation[4] + s
        else:
            s += operation[4]


print(s)

### FIXED CODE ###

s = input()
q = int(input())
qs = [input().split() for i in range(q)]
n = False
left= right = ""
for operation in qs:
    if operation[0] == '1':
        n = not n
    if operation[0] == '2':
        t , f, c = operation
        f = int(f)
        if n:
            f = 1 if f != 1 else 2
        if f == 1:
            left=c+left
        elif f == 2:
            right+=c
s = left+s+right
print(s[::-1] if n else s)
### BUGGY CODE ###

from copy import deepcopy

H,W = map(int,input().split())
s = [list(input()) for _ in range(H)]
black=0

for tate in s:
  for yoko in tate:
    if yoko=="#":
      black += 1

def search(y,x,H,W,s,zumi):
  child=[]
      
  if y<H-1:
    if s[y+1][x]==".":
      if [y+1,x] not in zumi:
        child.append([y+1,x])
  if 0<y:
    if s[y-1][x]==".":
      if [y-1,x] not in zumi:
        child.append([y-1,x])
  if 0<x:
    if s[y][x-1]==".":
      if [y,x-1] not in zumi:
        child.append([y,x-1])
  if x<W-1:
    if s[y][x+1]==".":
      if [y,x+1] not in zumi:
        child.append([y,x+1])
  return child

def dfs(y,x,cnt,H,W,s,zumi):
  node_to_visit=search(y,x,H,W,s,zumi)
  zumi=deepcopy(node_to_visit)
  flag=True
  
  while flag:
    cnt += 1
    tmp=[]
    tmp2=[]
    #print(node_to_visit)
    zumi += node_to_visit
    for next_point in node_to_visit:
      t=next_point[0] #y。たて
      u=next_point[1] #x。よこ
      tmp=search(t,u,H,W,s,zumi)
      tmp2 += tmp
    node_to_visit=deepcopy(tmp2)
    if [H-1,W-1] in node_to_visit:
      white=cnt
      flag=False
      break     
  ans=H*W-white-black-2
  #print(white,black,ans)
  print(ans)

zumi=[]
dfs(0,0,0,H,W,s,zumi)

### FIXED CODE ###

from collections import deque

H,W = map(int,input().split())
s = [list(input()) for _ in range(H)]
c = [[-1 for _ in range(W)] for _ in range(H)]

black=0
for tate in s:
  for yoko in tate:
    if yoko=="#":
      black += 1

def search(y,x,H,W,c,i):
  child=[]      
  if y<H-1:
    if s[y+1][x]=="." and c[y+1][x]==-1:
      c[y+1][x]=i
      child.append([y+1,x])
  if 0<y:
    if s[y-1][x]=="." and c[y-1][x]==-1:
      c[y-1][x]=i
      child.append([y-1,x])
  if 0<x:
    if s[y][x-1]=="." and c[y][x-1]==-1:
      c[y][x-1]=i
      child.append([y,x-1])
  if x<W-1:
    if s[y][x+1]=="." and c[y][x+1]==-1:
      c[y][x+1]=i
      child.append([y,x+1])
  return child

def dfs(y,x,c):
  visited=[[y,x]]
  c[y][x]=0
  i=1
  
  while visited:
    tmp=[]
    for a in visited:
      p=search(a[0],a[1],H,W,c,i)  #listが戻る
      tmp += p
    visited=tmp
    i += 1

dfs(0,0,c)
a=c[-1][-1]
if a==-1:
  print(-1)
else:
  print(H*W-black-a-1)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
q = int(input())
b = [0]*q
c = [0]*q
s = 0
for i in range(q):
  b[i],c[i] = map(int,input().split())
for i in range(q):
  for j in range(n):
    if(a[j]==b[i]):
      a[j]=c[i]
    s +=a[j]
  print(s)
  s=0

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
q = int(input())
r = [0]*(10**5+10)
for i in range(n):
  r[a[i]] +=1
b = [0]*q
c = [0]*q
for i in range(q):
  b[i],c[i] = map(int,input().split())
s = 0
for m in range(n):
  s += a[m] 
for ii in range(q):
  s = s + (c[ii]-b[ii])*r[b[ii]]
  r[c[ii]] +=r[b[ii]]
  r[b[ii]]=0
  print(s)
### BUGGY CODE ###

import sys
from collections import deque
def input(): return sys.stdin.readline()
def inpl(): return [int(i) for i in input().split()]
from collections import defaultdict
N, M = inpl()
Edge = defaultdict(lambda: [])
Par = set(range(N)) 
for _ in range(N-1+M):
    A, B = inpl()
    Par.discard(B-1)
    Edge[A-1].append(B-1)
par = list(Par)[0]
dist = [0]*N
Q = deque([par])
while Q:
    st = Q.pop()
    for en in Edge[st]:
        if dist[en] < dist[st] + 1:
            dist[en] = dist[st] + 1
            if len(Edge[en]) == 1:
                Q.append(en)
            else:
                Q.appendleft(en)
Ans = [0]*N
Q = deque([par]) 
while Q:
    st = Q.pop()
    for en in Edge[st]:
        if dist[en] == dist[st] + 1:
            Ans[en] = st+1
            Q.appendleft(en)
for i in Ans:
    print(i)    


### FIXED CODE ###

import sys
from collections import deque
def input(): return sys.stdin.readline()
def inpl(): return [int(i) for i in input().split()]
from collections import defaultdict
N, M = inpl()
Edge = defaultdict(lambda: [])
Pcan = defaultdict(lambda: 0)

Par = set(range(N)) 
for _ in range(N-1+M):
    A, B = inpl()
    Par.discard(B-1)
    Edge[A-1].append(B-1)
    Pcan[B-1] += 1
par = list(Par)[0]
dist = [0]*N
Q = deque([par])

while Q:
    st = Q.pop()
    for en in Edge[st]:
        if dist[en] < dist[st] + 1:
            dist[en] = dist[st] + 1
            if Pcan[en] == 1:
                Q.append(en)
            else:
                Pcan[en] -= 1
Ans = [0]*N
Q = deque([par]) 
while Q:
    st = Q.pop()
    for en in Edge[st]:
        if dist[en] == dist[st] + 1:
            Ans[en] = st+1
            Q.appendleft(en)
for i in Ans:
    print(i)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
divide_minimam_prime = [0 for i in range(max(a) + 1)]
is_prime = [True for i in range(max(a) + 1)]
is_prime[0] = False
is_prime[1] = False
for div in range(max(a) + 1):
    if is_prime[div]:
        # divが素数だった場合
        k = div
        divide_minimam_prime[k] = k
        k += div
        while k <= max(a):
            is_prime[k] = False
            if divide_minimam_prime[k] == 0:
                divide_minimam_prime[k] = div
            k += div
    else:
        if divide_minimam_prime[div] == 0:
            divide_minimam_prime[div] = div
# pairwise coprimeであるかどうか？
pairwise_coprime = True
use_divnum = set()
for i in range(n):
    k = a[i]
    divnum_of_a = set()
    while k != 1:
        if divide_minimam_prime[k] in use_divnum:
            pairwise_coprime = False
            break
        else:
            divnum_of_a.add(divide_minimam_prime[k])
        k = k // divide_minimam_prime[k]
    use_divnum = use_divnum or divnum_of_a
if pairwise_coprime: 
    print("pairwise coprime")
    exit()
from math import gcd
gcd_of_a = a[0]
for i in range(n):
    gcd_of_a = gcd(gcd_of_a, a[i])
if gcd_of_a == 1:
    print("setwise coprime")
else:
    print("not coprime")

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
MAX_A = max(a)
divide_minimam_prime = [i for i in range(MAX_A + 1)]
is_prime = [True for i in range(MAX_A + 1)]
is_prime[0] = False
is_prime[1] = False
for div in range(2,int(MAX_A**0.5) + 1):
    if is_prime[div]:
        # divが素数だった場合
        k = div
        divide_minimam_prime[k] = k
        k += div
        while k <= MAX_A:
            is_prime[k] = False
            if divide_minimam_prime[k] == k:
                divide_minimam_prime[k] = div
            k += div
# pairwise coprimeであるかどうか？
pairwise_coprime = True
use_divnum = set()
for i in range(n):
    k = a[i]
    while k != 1:
        if divide_minimam_prime[k] in use_divnum:
            pairwise_coprime = False
            break
        else:
            use_divnum.add(divide_minimam_prime[k])
        div = divide_minimam_prime[k]
        while k % div == 0 and k > 1:
            k = k // div
if pairwise_coprime: 
    print("pairwise coprime")
    exit()
from math import gcd
gcd_of_a = a[0]
for i in range(n):
    gcd_of_a = gcd(gcd_of_a, a[i])
if gcd_of_a == 1:
    print("setwise coprime")
else:
    print("not coprime")
### BUGGY CODE ###

from collections import deque
N = int(input())
connected = [[] for _ in range(N)]
ans = [0] * (N-1)
for i in range(N-1):
    a,b = (int(x) for x in input().split())
    connected[a-1].append([b,i])
    connected[b-1].append([a,i])
colors = max(len(d) for d in connected)
print(colors)
init = 1
d = deque()
parents = deque()
for edge in connected[0]:
    ans[edge[1]] = init
    init += 1
    d.append(edge)
    parents.append(1)
while d:
    temp = d.popleft()
    parent = parents.popleft()
    used = deque(range(1,colors+1))
    used.remove(ans[temp[1]])
    if len(connected[temp[0]-1]) > 1:
        for edge in connected[temp[0]-1]:
            if edge[0] != parent:
                ans[edge[1]] = used.popleft()
                d.append(edge)
                parents.append(temp[0])
for i in range(N-1):
    print(ans[i])

### FIXED CODE ###

from collections import deque
N = int(input())
connected = [[] for _ in range(N)]
ans = [0] * (N-1)
for i in range(N-1):
    a,b = (int(x) for x in input().split())
    connected[a-1].append([b,i])
    connected[b-1].append([a,i])
colors = max(len(d) for d in connected)
print(colors)
init = 1
d = deque()
parents = deque()
for edge in connected[0]:
    ans[edge[1]] = init
    init += 1
    d.append(edge)
    parents.append(1)
while d:
    temp = d.popleft()
    parent = parents.popleft()
    l = len(connected[temp[0]-1])
    if l > 1:
        used = deque(range(1,l+1))
        for edge in connected[temp[0]-1]:
            if edge[0] != parent:
                color = used.popleft()
                if color == ans[temp[1]]:
                    ans[edge[1]] = used.popleft()
                else:
                    ans[edge[1]] = color
                d.append(edge)
                parents.append(temp[0])
for i in range(N-1):
    print(ans[i])
### BUGGY CODE ###

N,M = [int(x) for x in input().split()]
h = [int(x) for x in input().split()]
dist = [10**10]*N
for index,i in enumerate(h):
    if(index == 0):
        dist[index] = 0
    else:
        K=1
        min = 10**10
        while(index-K>=0 and K<=M):
            dist_iK = abs(i-h[index-K])+dist[index-K]
            if(dist_iK < min):
                min = dist_iK
            K+=1
        dist[index] = min

print(dist[N-1])


### FIXED CODE ###

N,K = [int(x) for x in input().split()]
h = [int(x) for x in input().split()]
dist = [0]+[10**10]*(N+100)
for index,i in enumerate(h):
    for indh,j in enumerate(h[index+1:index+K+1]):
        dist[index+indh+1]=min(dist[index+indh+1],abs(j-i)+dist[index])

print(dist[N-1])
### BUGGY CODE ###

#Breadth First Search

#for every node, print the last visited node before reaching itself
#starting from the source
from collections import deque

def bfs(graph,N,source):
    visited=[0]*N
    visited[source]=1
    q=deque([source])
    while len(q)>0:
        node=q.popleft()
        for i in graph[node]:
            if visited[i]==0:
                visited[i]=node+1
                q.append(i)
    return visited

n,m=map(int,input().split())
graph=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    graph[a].append(b)
    graph[b].append(a)
print('Yes')
for i in range(1,n):
    print(bfs(graph,n,0)[i])
    

    
        


### FIXED CODE ###

#Breadth First Search

#for every node, print the last visited node before reaching itself
#starting from the source
from collections import deque

def bfs(graph,N,source):
    visited=[0]*N
    visited[source]=1
    q=deque([source])
    while len(q)>0:
        node=q.popleft()
        for i in graph[node]:
            if visited[i]==0:
                visited[i]=node+1
                q.append(i)
    return visited

n,m=map(int,input().split())
graph=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    graph[a].append(b)
    graph[b].append(a)
aw=bfs(graph,n,0)
print('Yes')
for i in range(1,n):
    print(aw[i])
### BUGGY CODE ###

n, k = list(map(int, input().split()))
s = []
for i in range(k):
    a, b = list(map(int, input().split()))
    for j in range(a, b+1):
        s.append(j)
s = set(s)
dp = [0]*(n+1)
dp[1] = 1
mod = 998244353
for i in range(1, n+1):
    for ss in s:
        if i+ss <= n:
            dp[i+ss] += dp[i]
            dp[i+ss] %= mod
print(dp[-1])


### FIXED CODE ###

n, k = list(map(int, input().split()))
s = []
for i in range(k):
    a, b = list(map(int, input().split()))
    s.append((a, b))
dp = [0]*(n+1)
v = 0
mod = 998244353
for i in range(1, n+1):
    if i == 1:
        for l, r in s:
            if i+l <= n:
                dp[i+l] += 1
            if i+r+1 <= n:
                dp[i+r+1] -= 1
    else:
        v += dp[i]
        v %= mod
        for l, r in s:
            if i+l <= n:
                dp[i+l] += v
            if i+r+1 <= n:
                dp[i+r+1] -= v


print(v % mod)