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

from collections import deque
import sys
input = sys.stdin.readline

h, w = map(int, input().split())
a = [[j=="#" for j in input()] for i in range(h)]
# for i in range(h):
#     a[i] = list(input())

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

que = deque()

white = h * w

# スタート地点をqueueに追加
for i in range(h):
    for j in range(w):
        if a[i][j]:
            que.append([i, j])
            white -= 1

count = 0
while 1:
    if white == 0:
        break
    count += 1
    loop = len(que)
    for i in range(loop):
        p = que.popleft()
        for j in range(4):
            ny = p[0] + dy[j]
            nx = p[1] + dx[j]
            if nx < w and nx >= 0 and ny < h and ny >= 0 and not a[ny][nx]:
                a[ny][nx] = True
                white -= 1
                que.append([ny, nx])


print(count)

### FIXED CODE ###

from collections import deque
h, w = map(int, input().split())
a = [[] for i in range(h)]
for i in range(h):
    a[i] = list(input())

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

que = deque()

white = h * w

# スタート地点をqueueに追加
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            que.append([i, j])
            white -= 1

count = 0
while 1:
    if white == 0:
        break
    count += 1
    loop = len(que)
    for i in range(loop):
        p = que.popleft()
        for j in range(4):
            ny = p[0] + dy[j]
            nx = p[1] + dx[j]
            if nx < w and nx >= 0 and ny < h and ny >= 0 and a[ny][nx] == ".":
                a[ny][nx] = "#"
                white -= 1
                que.append([ny, nx])


print(count)
### BUGGY CODE ###

#Sが長いほう
N = int(input())
A = list(map(int, input().split()))

cnt = 0
for i in range(N-1): 
  for j in range(i+1,N):
    cnt += (A[i] * A[j])%(10**9+7)

print(cnt%(10**9+7))

### FIXED CODE ###

#Sが長いほう
N = int(input())
A = list(map(int, input().split()))

cnt = 0
sumall = sum(A)
#print(sumall)
for i in range(N-1):
  sumall -= A[i]
  cnt += (A[i] * sumall )%(10**9+7)
print(cnt%(10**9+7))
### BUGGY CODE ###

N,K=map(int,input().split())
h=list(map(int,input().split()))
dp=[0]*(N)
dp[1]=abs(h[0]-h[1])
for i in range(2,N):
    memo=10**9
    for j in range(1,min(i+1,K+1)):
        tmp=(dp[i-j]+abs(h[i-j]-h[i]))
        if tmp < memo:
            memo=tmp
    dp[i]=memo
print(dp[N-1])

### FIXED CODE ###

N,K=map(int,input().split())
h=list(map(int,input().split()))
dp=[0]*(N)
dp[1]=abs(h[0]-h[1])
for i in range(2,N):
    dp[i]=min(dp[j]+abs(h[j]-h[i]) for j in range(max(0,i-K),i))
print(dp[N-1])
### BUGGY CODE ###

#!/usr/bin/python

import sys

p=[0]*10000;mp=[];inf=65536;v=[0]*10;t=[0]*10
 
 
ans=100000

 
n,m,r=map(int,sys.stdin.readline().split(" "))

s=sys.stdin.readline().replace("\n","")

p=map(int,s.split(" "))


def dsss(x,now):
	global ans
	if x==r+1:
		ans=min(ans,now)
		return 
	else :
		for i in range(r):
			if v[p[i]]==0 :
				v[p[i]]=1
				t[x]=p[i]
				if x==1:
					dsss(x+1,now)
				else :
					dsss(x+1,now+mp[p[i]-1][t[x-1]-1])
				v[p[i]]=0
	return 
 
 
for i in range(n+5):
	mp.append(range(n+5))
 
 
for i in range(n+5):
    for j in range(n+5):
        if(i!=j):
            mp[i][j]=inf
 
for i in range(m):
	a,b,c=map(lambda x: int(x),sys.stdin.readline().split(" ",3))
	a-=1;b-=1;
	mp[a][b]=min(mp[a][b],c)
	mp[b][a]=min(mp[b][a],c)
 
for i in range(n):
	for j in range(n):
		for k in range(n):
			mp[j][k]=min(mp[j][k],mp[j][i]+mp[i][k])
 
dsss(1,0)
 
print ans


### FIXED CODE ###

#!/usr/bin/python

import sys

p=[0]*10000;mp=[];inf=65530060;v=[0]*1000;t=[0]*1000
 
 
ans=100000000

 
n,m,r=map(int,sys.stdin.readline().split(" "))



s=sys.stdin.readline().replace("\n","")

p=map(int,s.split(" "))


def dsss(x,now):
	global ans,v,p,t,mp
	if x==r+1:
		ans=min(ans,now)
		return 
	else :
		for i in range(r):
			if v[p[i]]==0 :
				v[p[i]]=1
				t[x]=p[i]
				if x==1:
					dsss(x+1,now)
				else :
					dsss(x+1,now+mp[p[i]-1][t[x-1]-1])
				v[p[i]]=0
	return 
 
 
for i in range(n+5):
	mp.append(range(n+5))
 
 
for i in range(n+5):
    for j in range(n+5):
            mp[i][j]=inf


for i in range(m):
	a,b,c=map(lambda x: int(x),sys.stdin.readline().split(" ",3))
	a-=1;b-=1;
	mp[a][b]=min(mp[a][b],c)
	mp[b][a]=min(mp[b][a],c)


for i in xrange(n):
	for j in xrange(n):
		for k in xrange(n):
			if mp[j][i]+mp[i][k]<mp[j][k]:
			    mp[j][k]=mp[j][i]+mp[i][k]

dsss(1,0)
 
print ans
### BUGGY CODE ###

import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

def check(i,s,s0):
    if i%2 == 0:
        if s == s0:
            return True
        else:
            return False
    else:
        if s != s0:
            return True
        else:
            return False

N = I()
print(0,flush=True)
s0 = str(input())
if s0 == 'Vacant':
    exit()

ok = N-1
ng = 0
while True:
    mid = (ok+ng)//2
    print(mid,flush=True)
    s = str(input())
    if s == 'Vacant':
        exit()
    flag = check(mid,s,s0)
    if flag:
        ng = mid
    else:
        ok = mid

### FIXED CODE ###

import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

def check(i,s,s0):
    if i%2 == 0:
        if s == s0:
            return True
        else:
            return False
    else:
        if s != s0:
            return True
        else:
            return False

N = I()
print(0)
sys.stdout.flush()
s0 = str(input())
if s0 == 'Vacant':
    exit()

print(N-1)
sys.stdout.flush()
s1 = str(input())
if s1 == 'Vacant':
    exit()

ok = N-1
ng = 0
while True:
    mid = (ok+ng)//2
    print(mid)
    sys.stdout.flush()
    s = str(input())
    if s == 'Vacant':
        exit()
    flag = check(mid,s,s0)
    if flag:
        ng = mid
    else:
        ok = mid
### BUGGY CODE ###

import itertools
n,m=map(int,input().split())
mv=m
l=[]
for i in range(2,int(m**0.5)+1):
	while m%i==0:
		l.append(i)
		m//=i
if m>1:l.append(m)
elif m==1 and l is None:l.append(1)

comb=set()
for i in range(len(l)+1):
	for x in itertools.combinations(l,i):
		comb.add(x)
		
ans=1
for i in comb:
	res=1
	for j in i:
		res*=j
	if res<=mv//n:
		ans=max(ans,res)
print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
divis=[]
for i in range(1,int(m**0.5)+1):
	if m%i==0:
		divis.append(i)
		if i!=m//i:
			divis.append(m//i)
ans=1
for i in divis:
	if i<=m//n:
		ans=max(ans,i)
print(ans)
### BUGGY CODE ###

import copy
S = input()

Sr = S.split('L')
R_max = len(max(Sr,key=len))
Sl = S.split('R')
L_max = len(max(Sl,key=len))

Sc = [1] * len(S)
Sc_ = [0] * len(S)

S_try = max(L_max,R_max)
if S_try % 2 == 1:
    S_try += 1

for n in range(S_try):
    for i in range(len(S)):
        if S[i] == 'L':
            Sc_[i - 1] += Sc[i]
        elif S[i] == 'R':
            Sc_[i + 1] += Sc[i]
    Sc = copy.deepcopy(Sc_)
    Sc_ = [0] * len(S)

print(" ".join(map(str,Sc)))



### FIXED CODE ###

import copy
S = input()
Slen = len(S)

Sc=[0]*Slen
for i in range(Slen):
    if S[i:i+2] == 'RL':
        for j in range(i,-1,-1):
            if S[j]=='R':
                Sc[(i-j)%2 + i] += 1
            else:
                break
        for j in range(i+1,Slen):
            if S[j] == 'L':
                Sc[(j-i)%2 +i] += 1
            else:
                break    

print(" ".join(map(str,Sc)))
### BUGGY CODE ###

s, t = input(), input()
n, m = len(s), len(t)
dp = [[0]*-~m for _ in [0]*-~n]
for i in range(n):
  for j in range(m):
    dp[i+1][j+1] = dp[i][j] + 1 if s[i] == t[j] else max(dp[i][j+1], dp[i+1][j])
R = ""
while n and m:
  if   dp[n][m] == dp[n-1][m]:n -= 1
  elif dp[n][m] == dp[n][m-1]:m -= 1
  else:n -= 1;m -= 1;R = s[n] + R
print(R)

### FIXED CODE ###

s, t = input(), input()
n, m = len(s), len(t)
dp = [[0]*-~m for _ in [0]*-~n]
for i in range(n):
  for j in range(m):
    dp[i+1][j+1] = dp[i][j] + 1 if s[i] == t[j] else max(dp[i][j+1], dp[i+1][j])
R = ""
while n and m:
  if   dp[n][m] == dp[n-1][m]:n -= 1
  elif dp[n][m] == dp[n][m-1]:m -= 1
  else:n -= 1;m -= 1;R = s[n] + R
print(R)
### BUGGY CODE ###

import collections

N = int(input())

Tree = collections.defaultdict(list)

for i in range(N - 1):
    a, b, c = map(int, input().split())
    Tree[a].append((b, c))
    Tree[b].append((a, c))

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

def bfs(tree, s, distance):
    queue = [s]
    distance[s] = 0

    while queue:
        v = queue.pop(0)
        for node, cost in tree[v]:
            if distance[node] == -1:
                distance[node] = distance[v] + cost
                queue.append(node)

distance = collections.defaultdict(lambda : -1)
bfs(Tree, k, distance)

for i in range(q):
    x, y = map(int, input().split())
    print(distance[x] + distance[y])


### FIXED CODE ###

import sys
import collections

sys.setrecursionlimit(int(1e7))

def dfs(node, parent, distance):
    depth[node] = distance
    for next_node, cost in Tree[node]:
        if next_node != parent:
            dfs(next_node, node, distance + cost)

N = int(input())

Tree = collections.defaultdict(list)

for i in range(N - 1):
    a, b, c = map(int, input().split())
    Tree[a].append((b, c))
    Tree[b].append((a, c))

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

depth = {}
dfs(k, -1, 0)

for i in range(q):
    x, y = map(int, input().split())
    print(depth[x] + depth[y])
### BUGGY CODE ###

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

ans = l[0]

for i in range(1,len(l)):
    ans = ans * l[i]
    if ans == 0:
        break

if ans >= 1000000000000000001:
    print(-1)
else:
    print(ans)
    

### FIXED CODE ###

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

ans = l[0]

minn = min(l)

if (minn == 0):
    print(0)
else:
    for i in range(1,len(l)):
        ans = ans * l[i]

        if ans >= 1000000000000000001:
            break
    
    if ans >= 1000000000000000001:
        print(-1)
    else:
        print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 1
for i in range (0, N):
	if A[i] == 0:
		ans = 0
		break
	else:
		ans *= A[i]
		if ans > 10 ** 18:
			ans = -1
			continue

print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 1
for i in range (0, N):
	if A[i] == 0:
		ans = 0
		break
	else:
		if ans > 0:
			ans *= A[i]
		if ans > 10 ** 18:
			ans = -1

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

N, K = map(int, input().split())
k_bitlen = K.bit_length()
dp = [[0] * N for _ in range(k_bitlen + 1)]
dp[0] = list(map(lambda x: int(x) - 1, input().split()))

for k in range(k_bitlen):
    for i in range(N):
        dp[k + 1][i] = dp[k][dp[k][i]]
pos = 0
for k in range(k_bitlen):
    if K >> k & 1:
        pos = dp[k][pos]
print(pos + 1)

### FIXED CODE ###

import sys


def input():
    return sys.stdin.readline().strip()


N, K = map(int, input().split())
A = [0] + list(map(int, input().split()))

pos = A[1]
path = [1]
visited = {1}
cycle_start = -1
for _ in range(N):
    if pos in visited:
        cycle_start = pos
        break
    visited.add(pos)
    path.append(pos)
    pos = A[pos]

if cycle_start > 0:
    cycle_start_idx = path.index(cycle_start)
    acyclic_path = path[:cycle_start_idx]
    cyclic_path = path[cycle_start_idx:]
    if K < len(acyclic_path):
        print(acyclic_path[K])
    else:
        print(cyclic_path[(K - len(acyclic_path)) % len(cyclic_path)])
else:
    print(path[K])
### BUGGY CODE ###

N = int(input())
Up = []
Down = []
for _ in range(N):
    S = input()
    L = [0]
    for __ in range(len(S)):
        if S[__] == '(':
            L.append(L[-1] + 1)
        else:
            L.append(L[-1] - 1)
    las = L[-1]
    mi = min(L)
    if las > 0:
        Up.append((mi, las))
    else:
        Down.append((mi - las, mi, las))

Up.sort(reverse=True)
Down.sort()

now = 0
for i, j in Up:
    if now + i < 0:
        print('No')
        exit()
    else:
        now += j
for _, i, j in Down:
    if now + i < 0:
        print('No')
        exit()
    else:
        now += j
if now == 0:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

N = int(input())
Up = []
Down = []
for _ in range(N):
    S = input()
    L = [0]
    mi = 0
    now = 0
    for __ in range(len(S)):
        if S[__] == '(':
            now += 1
        else:
            now -= 1
            mi = min(mi, now)
    if now > 0:
        Up.append((mi, now))
    else:
        Down.append((mi - now, mi, now))

Up.sort(reverse=True)
Down.sort()

now = 0
for i, j in Up:
    if now + i < 0:
        print('No')
        exit()
    else:
        now += j
for _, i, j in Down:
    if now + i < 0:
        print('No')
        exit()
    else:
        now += j
if now == 0:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

def ABC146D_ColoringEdge():
    N = int(input())

    graph = [[] for i in range(0, N)]
    edge = [0] * (N - 1)
    for i in range(0, N - 1):
        frm, to = list(map(int, input().split()))
        frm -= 1
        to -= 1
        graph[frm].append(i)
        graph[to].append(i)
    
    maxColor = 0
    for node in graph:
        usedColor = []
        maxColor = max(maxColor, len(node))
        for eNo in node:
            if edge[eNo] is not 0:
                usedColor.append(edge[eNo])
        
        nowColor = 1
        for eNo in node:
            if edge[eNo] is 0:
                while nowColor in usedColor:
                    nowColor += 1

                edge[eNo] = nowColor
                usedColor.append(nowColor)

    print(maxColor)
    
    for color in edge:
        print(color)


def main():
    ABC146D_ColoringEdge()

if __name__ == "__main__":
    main()


### FIXED CODE ###

def ABC146D_ColoringEdge():
    N = int(input())

    graph = [[] for i in range(0, N)]
    edge = [0] * (N - 1)
    for i in range(0, N - 1):
        frm, to = list(map(int, input().split()))
        frm -= 1
        to -= 1
        graph[frm].append(i)
        graph[to].append(i)
    
    maxColor = 0
    for node in graph:
        usedColor = []
        maxColor = max(maxColor, len(node))
        for eNo in node:
            if edge[eNo] is not 0:
                usedColor.append(edge[eNo])
        
        nowColor = 1
        for eNo in node:
            if edge[eNo] is 0:
                while nowColor in usedColor:
                    nowColor += 1

                edge[eNo] = nowColor
                usedColor.append(nowColor)

    print(maxColor)
    
    for color in edge:
        print(color)


def main():
    ABC146D_ColoringEdge()

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

N,M = map(int,input().split())
X = sorted(list(map(int,input().split())))
if len(X) >1:
    l = [X[i+1]-X[i] for i in range(M-1)]
else:
    print(0)
    exit()
for i in range(N-1):
    ma = l.index(max(l))
    l[ma] = 0
print(sum(l))

### FIXED CODE ###

N, M = map(int,input().split())
X = sorted(list(map(int,input().split())))
if M > 1:
    l = [X[i+1]-X[i] for i in range(M-1)]
else:
    print(0)
    exit()
ll = sorted(l, reverse=True)
z = sum(ll[:N-1])
print(sum(l)-z)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
A.sort()
B.sort()
C.sort()
A.reverse()
B.reverse()
C.reverse()

ue=0
naka=0
sita=0
count=0
for i in range(N):
    ue=A[i]
    for j in range(N):
        naka=B[j]
        if ue>=naka:
            break
        for k in range(N):
            
            sita=C[k]
            if A[i]<B[j] and B[j]<C[k]:
                count+=1
            if naka>=sita:
                break
            
print(count)

### FIXED CODE ###

N=int(input())
S=list(map(int,input().split()))
T=list(map(int,input().split()))
U=list(map(int,input().split()))
S.sort()
T.sort()
U.sort()
#print(S)
#print(T)
#print(U)


count=0
def is_ok(index,key):
    if key>S[index]:
        return True
    else:
        return False


def meguru_bisect(key):
    ng=N
    ok=-1
    
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid,key):
            ok = mid
        else:
            ng = mid
    return ok

def is_ok2(index,key):
    if key<U[index]:
        return True
    else:
        return False


def meguru_bisect2(key):
    ng=-1
    ok=N
    
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok2(mid,key):
            ok = mid
        else:
            ng = mid
    return ok
ans=0
for i in range(N):
    ans+=(N-meguru_bisect2(T[i]))*(meguru_bisect(T[i])+1)
print(ans)
### BUGGY CODE ###

n = int(input())
a = [i for i in range(n)]
print(sum(a))

### FIXED CODE ###

n = int(input())
ans = (n - 1) * n // 2
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 1
for ai in a:
  ans *= ai
if ans > 10 ** 18:
  print(-1)
else:
  print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 1
if 0 in a:
  print(0)
  quit()

for ai in a:
  ans *= ai
  if ans > 10 ** 18:
    print(-1)
    quit()
else:
  print(ans)
### BUGGY CODE ###

import numpy as np
N,W = map(int,input().split())
#N = int(input())
dp =[[0 for i in range(W+1)] for j in range(N+1)]
w = np.zeros(W+1)
v = [0]*N
ndp = np.zeros(W + 1, dtype=np.int64)
for i in range(N):
  w[i],v[i] =  map(int,input().split())
for i in range(N):
  ndp[w[i]:] = np.maximum(ndp[:-w[i]] + v[i], ndp[w[i]:])
print(ndp[W])

### FIXED CODE ###

import numpy as np
N,W = map(int,input().split())
s=np.full(N*1000+1,W+1)
s[0]=0
for i in range(N):
  w,v =  map(int,input().split())
  s[v:]=np.minimum(s[v:],s[:-v]+w)
print(np.max(np.where(s<=W)))
### BUGGY CODE ###

from collections import deque

def main():
    H,W = map(int, input().split())

    A = [["" for _ in range(W)] for _ in range(H)]

    stack = deque()
    for i in range(H):
        tmp = list(input())
        for j in range(W):
            A[i][j] = tmp[j]
            if tmp[j] == "#":
                stack.append((i,j))

    ans = 0
    flag = False
    if stack:
        flag = True
    while flag:
        ans += 1
        #print(ans, stack)
        flag = False
        new_stack = deque()
        for a,b in stack:
            #a,b = stack.pop() # 取り出す
            # A[a][b]の隣接マスについて調べる
            if a != 0: # 上
                if A[a-1][b] == ".": # 白の場合
                    A[a-1][b] = "#"
                    new_stack.append((a-1,b))
            if a != H-1: # 下
                if A[a+1][b] == ".": # 白の場合
                    A[a+1][b] = "#"
                    new_stack.append((a+1,b))
            if b != 0: # 左
                if A[a][b-1] == ".": # 白の場合
                    A[a][b-1] = "#"
                    new_stack.append((a,b-1))
            if b != W-1: # 右
                if A[a][b+1] == ".": # 白の場合
                    A[a][b+1] = "#"
                    new_stack.append((a,b+1))
        stack = new_stack
        if stack:
            flag = True
        else:
            ans -= 1 

    print(ans)
            


if __name__ == "__main__":
    main()




### FIXED CODE ###

from collections import deque

def main():
    H,W = map(int, input().split())

    A = [[a for a in input()] for _ in range(H)]
    #stack = deque([(i, j) for i in range(H) for j in range(W) if A[i][j]=="#"])
    stack = [(i, j) for i in range(H) for j in range(W) if A[i][j]=="#"]
    ans = 0
    flag = False
    if stack:
        flag = True
    while flag:
        ans += 1
        flag = False
        #new_stack = deque()
        new_stack = []
        for a,b in stack:
        #while stack:
            #a,b = stack.pop() # 取り出す
            # A[a][b]の隣接マスについて調べる
             # 上
            if a != 0 and A[a-1][b] == ".": # 白の場合
                    A[a-1][b] = "#"
                    new_stack.append((a-1,b))
             # 下
            if a != H-1 and A[a+1][b] == ".": # 白の場合
                    A[a+1][b] = "#"
                    new_stack.append((a+1,b))
            # 左
            if b != 0 and A[a][b-1] == ".": # 白の場合
                    A[a][b-1] = "#"
                    new_stack.append((a,b-1))
            # 右
            if b != W-1 and A[a][b+1] == ".": # 白の場合
                    A[a][b+1] = "#"
                    new_stack.append((a,b+1))
        stack = new_stack
        if stack:
            flag = True
        else:
            ans -= 1 

    print(ans)
            


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

n,k = (int(x) for x in input().split())
h = list(int(x) for x in input().split())
dp = [0]*n

# i = 1の時
dp[1] = abs(h[1] - h[0])

# i番目までの必要な体力を求める
for i in range(2,n):

    # i >= 2の時
    # i番目に必要な体力の最小値を求める
    dp[i] = (min(dp[j] + abs(h[i] - h[j]) for j in range(max(0,i-k),i)))

print(dp[-1])
                  



### FIXED CODE ###

def main():
    n,k = map(int,input().split())
    h = list(map(int,input().split()))
    dp = [0]*n
    dp[1] = abs(h[1] - h[0])
    for i in range(2,n):
        dp[i] = min(abs(h[i] - h[j]) + dp[j] for j in range(max(0,i-k),i))
    print(dp[-1])

main()
### BUGGY CODE ###

INF = 2**60 # 無限大を表す値
H, N = map(int, input().split())
AB = [map(int, input().split()) for i in range(N)]
dp = [INF] * (H + 1)
dp[0] = 0
for (A, B) in AB:
    for j in range(H+1):
        k = j - A
        if k < 0:
            k = 0
        dp[j] = min(dp[j], dp[k] + B)
print(dp[H])

### FIXED CODE ###

INF = 2**60 # 無限大を表す値
H, N = map(int, input().split())
AB = [map(int, input().split()) for i in range(N)]
dp = [INF] * (H + 1)
dp[0] = 0
for A, B in AB:
    for j in range(H+1):
        dp[j] = min(dp[j], dp[max(j-A, 0)] + B)
print(dp[H])
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]

min = 2020202021

for i in range(1,len(a)):
    
    if min > abs(sum(a[:i]) - sum(a[i:])):
        min = abs(sum(a[:i]) - sum(a[i:]))

print(min)

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]

len_f = sum(a)
sum_a = 0
min = 2020202021

for i in range(n):
    sum_a += a[i]
    len_f -= a[i]
    if min > abs(sum_a - len_f):
        min = abs(sum_a - len_f)

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

from collections import deque


def solve(a):
    ans = deque()

    for i, aa in enumerate(a):
        ans.append(str(aa))
        ans.reverse()

    return list(ans)


if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))
    print(' '.join(solve(a)))


### FIXED CODE ###

from collections import deque


def solve(a):
    ans = deque()

    for i, aa in enumerate(a):
        if i % 2 == 0:
            ans.append(str(aa))
        else:
            ans.appendleft(str(aa))

    if len(a) % 2 == 1:
        ans.reverse()

    return list(ans)


if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))
    print(' '.join(solve(a)))
### BUGGY CODE ###

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

c = []
for i in range(N-1):
	b = a[0:i+1]
	c.append(abs(sum(a)-2*sum(b)))

print(min(c))

### FIXED CODE ###

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

c = [2*a[0]-sum(a)]
d = [abs(c[0])]
for i in range(N-2):
	c.append(c[i]+2*a[i+1])
	d.append(abs(c[i+1]))

print(min(d))