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

def small(a, b):
    if a > b:
        return b
    else:
        return a


n, k = map(int, input().split())
h = list(map(int, input().split()))
INF = 10 ** 9
dp = [INF] * n
dp[0] = 0
for i in range(n):
    for j in range(1, k + 1):
        if i + j < n:
            dp[i + j] = small(dp[i + j], dp[i] + abs(h[i] - h[i + j]))
print(dp[-1])

### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    h = tuple(map(int, input().split()))
    INF = 10 ** 9
    dp = [INF] * n
    dp[0] = 0
    for i in range(n):
        for j in range(1, k + 1):
            i_j = i + j
            if i_j < n:
                x = dp[i] + abs(h[i] - h[i_j])
                if dp[i_j] > x:
                    dp[i_j] = x
    print(dp[-1])


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

n, k, q = map(int, input().split())
a = [int(input()) for _ in range(q)]
d = [a.count(i) for i in range(1, n + 1)]
for i in d:
    print("YNeos"[k - q + i < 1::2])

### FIXED CODE ###

n, k, q = map(int, input().split())
d = dict()
for i in range(n):
    d[i + 1] = 0
for i in range(q):
    d[int(input())] += 1
for i in range(n):
    print("YNeos"[(q - k) >= d[i + 1]::2])
### BUGGY CODE ###

n = int(input())
T = []
for _ in range(n-1):
    T += [list(map(int, input().split()))]
T.sort()
P = [0]+[-1]*(n-1)
while T:
    for t in T:
        u, v, w = t
        pu, pv = P[u-1], P[v-1]
        if (pu >= 0) & (pv < 0):
            P[v-1] = (pu+(w%2))%2
            T.remove(t)
        if (pv >= 0) & (pu < 0):
            P[u-1] = (pv+(w%2))%2
            T.remove(t)
for p in P: print(p)

### FIXED CODE ###

n = int(input())
L = [[] for _ in range(n+1)]
R = [[] for _ in range(n+1)]
for _ in range(n-1):
    u, v, w = map(int, input().split())
    w %= 2
    L[u] += [[u, v, w]]
    R[v] += [[v, u, w]]
P = [[] for _ in range(2*n+2)]
P[1] += (L[1]+R[1])
L[1] = R[1] = []
for i in range(1, 2*n):
    for _, v, w in P[i]:
        P[i+2-w] += (L[v]+R[v])
        L[v] = R[v] = []
A = []
for p in P[1::2]: A += p
B = set([u for u, *_ in A])
for i in range(1, n+1): print(1 if i in B else 0)
### BUGGY CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


n, m = map(int, input().split())
uf = UnionFind(n)
for i in range(m):
    a, b = map(int, input().split())
    uf.union(a-1, b-1)

ans = 0
v = list(uf.all_group_members().values())
for y in range(len(v)):
    ans = max(ans, len(v[y]))

print(ans)

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

from collections import defaultdict
n, m = map(int, input().split())
uf = UnionFind(n)
for i in range(m):
    a, b = map(int, input().split())
    uf.union(a-1, b-1)

ans = defaultdict(int)
for i in range(n):
    ans[uf.find(i)] += 1

print(max(ans.values()))
### BUGGY CODE ###

m = int(input())
for i in range(m):
    str1 = input()
    str2 = input()
    A = [0 for j in range(len(str2)+1)]
    for char1 in str1:
        A_copy = A[:]
        for j,char2 in enumerate(str2):
            if(char1==char2):
                A[j+1] = A_copy[j]+1
            elif(A[j] > A[j+1]):
                A[j+1] = A[j]
    print(A[-1])


### FIXED CODE ###

def LCS(str1,str2):
    A = [0 for _ in range(len(str2)+1)]
    for i in range(len(str1)):
        A_copy = A[:]
        for j in range(len(str2)):
            if(str1[i]==str2[j]):
                A[j+1] = A_copy[j]+1
            elif(A[j] > A[j+1]):
                A[j+1] = A[j]
    print(A[-1])


m = int(input())
for i in range(m):
    str1 = input()
    str2 = input()
    LCS(str1,str2)
### BUGGY CODE ###

#from collections import deque
s=int(input())
a=list(map(int,input().split()))
b=[]
for i in range(0,s):
  b.append(a[i])
  b=b[::-1]
print(" ".join(map(str,b)))

### FIXED CODE ###

s=int(input())
a=list(map(int,input().split()))
b=[]
if s%2!=0:
  for i in range(s-1,-1,-2):
    b.append(a[i])
  for i in range(1,s,2):
    b.append(a[i])
else:
  for i in range(s-1,0,-2):
    b.append(a[i])
  for i in range(0,s,2):
    b.append(a[i])
print(" ".join(map(str,b)))
### BUGGY CODE ###

n=int(input())
A=list(map(int,input().split()))
a=0
b=0
c=0
d=sum(A)
for i in range(n):
  if A[i]==1:
    a=a+1
  elif A[i]==2:
    b=b+1
c=n-a-b
i=0
dp=[[[0]*(n+3) for i in range(n+3)] for j in range(n+3)]
for k in range(1,c+2):
  for j in range(1,n-k-i+4):
    for i in range(1,n-k-j+4):
      if i==1 and j==1 and k==1:
        continue
      dp[i][j][k]=(dp[i-1][j][k]*(i-1)+dp[i+1][j-1][k]*(j-1)+dp[i][j+1][k-1]*(k-1)+n)/(i+j+k-3)
print(dp[a+1][b+1][c+1])

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
a=0
b=0
c=0
d=sum(A)
for i in range(n):
  if A[i]==1:
    a=a+1
  elif A[i]==2:
    b=b+1
c=n-a-b
i=1
dp=[[[0]*(n+2) for i in range(n+2)] for j in range(n+2)]
for k in range(c+1):
  for j in range(n-k-a+1):
    for i in range(n-k-j+1):
      if i==0 and j==0 and k==0:
        continue
      dp[k][j][i]=(dp[k][j][i-1]*i+dp[k][j-1][i+1]*j+dp[k-1][j+1][i]*k+n)/(i+j+k)
print(dp[c][b][a])
### BUGGY CODE ###

n = int(input())
s = list(input())
ans = 0

def rest(a, b):
    if (a == "R" and b == "G") or (a == "G" and b == "R"):
        return("B")
    elif (a == "R" and b == "B") or (a == "B" and b == "R"):
        return("G")
    else:
        return("R")

for i in range(n - 3):
    for j in range(i + 1, n - 1):
        if s[i] != s[j]:
            parts = s[j + 1:]
            ans = ans + parts.count(rest(s[i], s[j]))

            if 2 * j - i < n:
                if s[2 * j - i] == rest(s[i], s[j]):
                    ans = ans - 1

print(ans)

### FIXED CODE ###

n = int(input())
s = list(input())
ans = 0

def rest(a):
    if a == "R":
        return(["G", "B"])
    elif a == "G":
        return(["R", "B"])
    else:
        return (["R", "G"])

for i in range(n - 3):
    rest1 = rest(s[i])[0]
    rest2 = rest(s[i])[1]
    ans = ans + s[i + 1:].count(rest1) * s[i + 1:].count(rest2)

    j = i + 1
    k = 1
    while True:
        if (s[j] == rest1 and s[j + k] == rest2) or (s[j] == rest2 and s[j + k] == rest1):
            ans = ans - 1
        k = k + 1
        j = i + k
        if j + k > n - 1:
            break

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

n, m = map(int, input().split())
ls = [list(map(int, input().split())) for _ in range(m)]
nodes = [[i, [i], 1] for i in range(n + 1)]
res = [n * (n - 1) // 2]
for a, b in reversed(ls):
    x = nodes[a][0]
    y = nodes[b][0]
    if x == y:
        res.append(res[-1])
    else:
        if x > y:
            x, y = y, x
        res.append(res[-1] - nodes[x][2] * nodes[y][2])
        nodes[x][1] += nodes[y][1]
        nodes[x][2] += nodes[y][2]
        for z in nodes[x][1]:
            nodes[z][0] = x
print(*reversed(res[:-1]), sep='\n')

### FIXED CODE ###

n, m = map(int, input().split())
ls = [list(map(int, input().split())) for _ in range(m)]

parents = list(range(n + 1))
ranks = [0 for _ in range(n + 1)]


def find(x):
    if parents[x] == x:
        return x
    parents[x] = find(parents[x])
    return parents[x]


def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    if ranks[x] < ranks[y]:
        parents[x] = y
    else:
        parents[y] = x
        if ranks[x] == ranks[y]:
            ranks[x] += 1


res = [n * (n - 1) // 2]
nums = [1 for _ in range(n + 1)]
for a, b in reversed(ls):
    aa = find(a)
    bb = find(b)
    if aa == bb:
        res.append(res[-1])
    else:
        res.append(res[-1] - nums[aa] * nums[bb])
        nums[aa] = nums[bb] = nums[aa] + nums[bb]
        unite(aa, bb)
print(*reversed(res[:-1]), sep='\n')
### BUGGY CODE ###

n,k = map(int,input().split())
w=[]
v=[]
MAX_N = 110
MAX_V=100100
dp =[[float("inf") for i in range(MAX_V)] for j in range(MAX_N)]
dp[0][0] = 0

for i in range(n):
    a,b = map(int,input().split())
    w.append(a)
    v.append(b)
for i in range(n):
    for sum_v in range(MAX_V):
        if sum_v - v[i] >=0:
            dp[i+1][sum_v]=min(dp[i][sum_v],dp[i][sum_v - v[i]] + w[i])
        
        dp[i+1][sum_v]=min(dp[i][sum_v],dp[i+1][sum_v])
for sum_v in range(MAX_V):
    if dp[n][sum_v] <= k:
        res = sum_v
print(res)

### FIXED CODE ###

N, W = map(int, input().split())
a = []
for i in range(N):
    x,y = map(int,input().split())
    a.append([x,y])
max_v, inf = 10**5, float("inf")
dp = [0] + [inf]*max_v
 
for w, v in a:
    for i, j in zip(range(max_v-v, -1, -1), range(max_v, -1, -1)):
        if dp[i]+w <= W and dp[j] > dp[i]+w:
            dp[j] = dp[i]+w
 
for weight, value in zip(dp[::-1], range(max_v, -1, -1)):
    if weight != inf:
        print(value)
        break
### BUGGY CODE ###

import numpy as np
n, q = map(int, input().split())
s = input()
dic = {}
g = np.ones(n).astype(int)
for i, c in enumerate(s):
    if c in dic.keys():
        dic[c].append(i)
    else:
        dic[c] = [i]

for i in range(q):
    t, d = input().split()
    sign = 0
    if d == 'L':
        sign = -1
    else:
        sign = 1
    try:
        for m in dic[t]:
            number = g[m]
            g[m] = 0
            if 0 <= m + sign < n:
                g[m + sign] += number
    except:
        continue
print(int(sum(g)))


### FIXED CODE ###

n, q = map(int, input().split())
s = input()
dic = {}
t_list = []
d_list = []

for i in range(q):
    t, d = input().split()
    t_list.append(t)
    if d == 'L':
        d_list.append(-1)
    else:
        d_list.append(1)


def find_pos(left, right):
    return left + (right - left - 1) // 2


def calc(sites, ts, ds):
    def check(idx):
        num = idx
        for j in range(q):
            site = sites[num]
            if ts[j] == site:
                num += ds[j]
            if num < 0:
                return -1
            if num > n - 1:
                return 1
        return 0

    def func(left, right):
        assert left > -1
        assert right < n + 1
        if right - left == 1:
            if check(left) > -1:
                return left
            else:
                return right
        pos = find_pos(left, right)
        if check(pos) > -1:
            return func(left, pos + 1)
        else:
            return func(pos + 1, right)
    return func


f1 = calc(s, t_list, d_list)
f2 = calc(s[::-1], t_list, [-i*1 for i in d_list])
print(n - f1(0, n) - f2(0, n))
### BUGGY CODE ###

# -*- coding: utf-8 -*-

def popMaxOishisa(sushis):
    t, d = sushis.pop()
    return t, d


def popMinOishisa_nonUniqueNeta(sel_sushis):
    t, d = min(sel_sushis["min"].items(), key=lambda i:i[1])
    if d > 1e9:
        return -1, -1
    sel_sushis[t].pop()
    if len(sel_sushis[t]) == 1:
        sel_sushis["min"][t] = 1e10
    else:
        sel_sushis["min"][t] = sel_sushis[t][-1]
    return t, d


def popMaxOishisa_uniqueNeta(sushis, netas):
    t, d = -1, -1
    while True:
        t, d = sushis.pop()
        if not t in netas:
            break
    return t, d


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

# Store data
sushis = []
neta_set = set()
sel_sushis = {"min":{}}
for i in range(n):
    t, d = map(int, input().split())
    sushis.append((t,d))
    neta_set.add(t)


# Formatting
sushis.sort(key=lambda i:i[1])
tMax = len(neta_set)

# Select sushi set as maximum oishisa point
sum_oishisa = 0
for i in range(k):
    t, d = popMaxOishisa(sushis)
    if not t in sel_sushis:
        sel_sushis[t] = [d]
        sel_sushis["min"][t] = 1e10
    else:
        sel_sushis[t].append(d)
        if sel_sushis["min"][t] > d:
            sel_sushis["min"][t] = d
    sum_oishisa += d

tMin = len(sel_sushis) - 1
max_score = tMin**2 + sum_oishisa

for nNeta in range(tMin+1, tMax + 1, 1):

    # Find sushi having minimum oishisa and being not unique for neta
    t1, d1 = popMinOishisa_nonUniqueNeta(sel_sushis)
    if t1 < 0:
        break
    sum_oishisa -= d1

    # Find sushi having maximum oishisa and unique for neta
    t2, d2 = popMaxOishisa_uniqueNeta(sushis, list(sel_sushis.keys()))
    sum_oishisa += d2

    if not t2 in sel_sushis:
        sel_sushis[t2] = [d2]
    else:
        sel_sushis[t2].append(d2)

    score = nNeta**2 + sum_oishisa
    if score > max_score:
        max_score = score

print(max_score)


### FIXED CODE ###

# -*- coding: utf-8 -*-


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

# Store data
sushis = []
neta_set = set()
for i in range(n):
    t, d = map(int, input().split())
    sushis.append((t,d))
    neta_set.add(t)


# Formatting
sushis.sort(key=lambda i:i[1])
tMax = len(neta_set)


# Select sushi set as maximum oishisa point
sel_sushis = []
neta_set = set()
sum_oishisa = 0
for i in range(k):
    t, d = sushis.pop()
    if t in neta_set:
        sel_sushis.append((t,d))
    else:
        neta_set.add(t)
    sum_oishisa += d

sel_sushis.sort(key=lambda i:i[1], reverse=True)
tMin = len(neta_set)
max_score = tMin**2 + sum_oishisa

for nNeta in range(tMin+1, tMax + 1, 1):

    # Find sushi having minimum oishisa and being not unique for neta
    if len(sel_sushis) == 0:
        break
    t1, d1 = sel_sushis.pop()
    sum_oishisa -= d1

    # Find sushi having maximum oishisa and unique for neta
    while True:
        t2, d2 = sushis.pop()
        if not t2 in neta_set:
            break

    sum_oishisa += d2
    neta_set.add(t2)

    score = nNeta**2 + sum_oishisa
    if score > max_score:
        max_score = score

print(max_score)
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def read():
    N = int(input().strip())
    S = input().strip()
    return N, S


def solve(N, S):
    ans = 0
    l0 = 0
    r0 = 1
    cache = [0 for i in range(N)]
    while l0 < N:
        for l1 in range(l0+1, N):
            # find and compare
            if S[l0] == S[l1]:
                if cache[l1] > 0:
                    k = cache[l1]
                else:
                    k = 1
                while l0 + k < l1 and l1+k < N and S[l0+k] == S[l1+k]:
                    k += 1
                ans = max(ans, k)
                # [l0, l0+k] と [l1, l1+k] が一致したという情報を保持しておく
                # l0を増やしたときに参照し、無駄なマッチングを省く
                if l1 + 1 < N:
                    cache[l1+1] = k-1
                l1 += k
        l0 += 1
    return ans

if __name__ == "__main__":
    inputs = read()
    print("%s" % solve(*inputs))


### FIXED CODE ###

import random
from collections import defaultdict


class RollingHash():

    def __init__(self, S, b=3491, m=999999937):
        """任意の基数と法でハッシュを生成する"""
        n = len(S)
        self.prefix = prefix = [0] * (n+1)
        self.power = power = [1] * (n+1)
        self.b = b
        self.m = m
        for i in range(n):
            c = ord(S[i])
            prefix[i+1] = (prefix[i] * b + c) % m
            power[i+1] = (power[i] * b) % m
    
    def get(self, l, r):
        """S[l, r) のハッシュを求める"""
        return (self.prefix[r] - self.power[r-l] * self.prefix[l]) % self.m
    
    def concat(self, h1, h2, l2):
        """S1+S2 のハッシュを、それぞれのハッシュから求める"""
        return (self.power[l2] * h1 + h2) % self.m
    
    def lcp(self, l1, r1, l2, r2):
        """S[l1, r1) とS[l2, r2) の最大共通接頭辞を求める"""
        low = 0
        high = min(r1-l1, r2-l2) + 1
        while high - low > 1:
            mid = (high + low) // 2
            if self.get(l1, l1 + mid) == self.get(l2, l2 + mid):
                low = mid
            else:
                high = mid
        return low


def read():
    N = int(input().strip())
    S = input().strip()
    return N, S


def solve(N, S):
    ans = []
    for m in [999999937, 10**9+7]:
        b = random.randint(10000, m-1)
        rh = RollingHash(S, b=b, m=m)
        low = 0
        high = (N+1) // 2 + 1
        dmax = defaultdict(int)
        dmin = defaultdict(int)
        while high - low > 1:
            dmax.clear()
            dmin.clear()
            mid = (high + low) // 2
            for i in range(0, N-mid+1):
                h = rh.get(i, i+mid)
                dmax[h] = max(dmax[h], i+1)
                dmin[h] = max(dmin[h], N+1-i)
            is_match = False
            for h in dmax.keys():
                if dmax[h] - (N+2 - dmin[h]) >= mid:
                    is_match = True
                    break
            if is_match:
                low = mid
            else:
                high = mid
        ans.append(low)
    return min(ans)


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
n=int(input())
#答え
sumy=0
#約数の個数を各値ごとにリストに入れる
cnt1=[]
#各値ごとの約数の個数
cnt2=0
for i in range(n+1):
  for j in range(i):
#0で割るのを防ぐ
    k=j+1
#商が割る数より小さいときは二重に数えることになるので省く
    if i/k<k:
      continue
    else:
#約数であるかを確認
      if i%k==0:
        if k==i/k:
          cnt2+=1
#計算量を減らすためにペアで数える(商と割る数)
        else:
          cnt2+=2
  cnt1.append(cnt2)
#cntを初期化
  cnt2=0    
  sumy+=cnt1[i]*i
print(sumy)

### FIXED CODE ###

# -*- coding: utf-8 -*-
n=int(input())
sumy=0
#nの半分より上の倍数は1個なのでそこで分ける
numhalf=int(n/2)
#nの半分までは倍数ごとに個数を求めて足していく
for i in range(numhalf):
  t=i+1
  k=int(n/t)
  sumy+=int(t*k*(k+1)/2)
#半分より上の倍数はすべて1個ずつなのでまとめて足す
sumy+=int((n+numhalf+1)*(n-numhalf)/2)
print(sumy)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
a,b,n = map(int,input().split())
li = []
append = li.append
for x in range(n+1):
    append(int((a*(x))/b) - a * int(x/b))
print(max(li))

### FIXED CODE ###

import math
 
A, B, N = map(int, input().split())
 
 
ans1 = 0
 
if N > B - 1:
    x = B-1
    print(int((A * x) / B) - A * int(x / B))
elif N <= B - 1:
    x = N
    print(int((A * x) / B) - A * int(x / B))
### BUGGY CODE ###

import sys 
sys.setrecursionlimit(10**6)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 10**9+7
N = int(readline())
K = int(readline())

def f(N,K):
    if K == -1:
        return 0
    if N < 10:
        if K == 0:
            return 1
        elif K == 1:
            return N
        else:
            return 0
    ans = 0
    q, mod = divmod(N, 10)
    ans += f(q,K) + mod * f(q,K-1) + (9-mod) * f(q-1,K-1) 
    return ans
print(f(N,K))

### FIXED CODE ###

import sys 
from functools import lru_cache
sys.setrecursionlimit(10**6)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 10**9+7
N = int(readline())
K = int(readline())
@lru_cache(None)
def f(N,K):
    if K == -1:
        return 0
    if N < 10:
        if K == 0:
            return 1
        elif K == 1:
            return N
        else:
            return 0
    ans = 0
    q, mod = divmod(N, 10)
    ans += f(q,K) + mod * f(q,K-1) + (9-mod) * f(q-1,K-1) 
    return ans
print(f(N,K))
### BUGGY CODE ###

import queue 
N = int(input())
tree = [[]for _ in range(N+1)]
for i in range(1,N):
    a,b = map(int,input().split())
    tree[a].append( [b,i])
    tree[b].append([a,i])

que = queue.Queue()
node = [-1]*(N+1)
edge = [-1]*N
que.put(1)
node[1] = 1
maxi = 1
color = [[] for _ in range(N+1)]
while(True):
    if que.empty():
        break
    start = que.get()
    for i in tree[start]:
        
        if node[i[0]] == -1 :
            que.put(i[0])
            node[i[0]] = 1
        col = 1
        if edge[i[1]] == -1:
            while(True):
               
                if col in (color[i[0]] + color[start]):
                    col +=1
                    if col > maxi:
                        maxi = col
                else :
                    break
            edge[i[1]] = col
            color[i[0]].append(col)
            color[start].append(col)
print(maxi)
for i in edge[1:]:
    print(i)

### FIXED CODE ###

import queue 
N = int(input())
tree = [[]for _ in range(N+1)]
for i in range(1,N):
    a,b = map(int,input().split())
    tree[a].append( [b,i])
    tree[b].append([a,i])
 
que = queue.Queue()
node = [-1]*(N+1)
edge = [-1]*N
que.put(1)
node[1] = 1
maxi = 1
start = 0
color = [[] for _ in range(N+1)]
node[1] = 0
while(True):
    if que.empty():
        break
    before = start
    start = que.get()
    col =1
    for i in tree[start]:
        
        if node[i[0]] == -1 :
            que.put(i[0])
        if edge[i[1]] == -1:
            if col == node[start]:
                col += 1
            edge[i[1]] = col
            node[i[0]] = col
            if col > maxi:
                maxi = col
            col +=1
            
print(maxi)
for i in edge[1:]:
    print(i)
### BUGGY CODE ###

ta,tt,aa,at=map(int,input().split())

while True:
 if at-tt>0:
    at-=tt
 elif at-tt<0:
    print("Yes")
 elif tt-aa>0:
     tt=-aa
 elif tt-aa<0:
    print("No")

### FIXED CODE ###

tt,ta,at,aa=map(int,input().split())
 
for i in range(100):
 at-=ta 
 if at>0:
    pass
 elif at<=0:
    print("Yes")
    exit()
 tt-=aa
 if tt>0:
    pass
 elif tt<=0:
    print("No")
    exit()