runtime error when solving a python problem

Task:

Given a tree with n vertices and a number k, we want to find the smallest number of edges, when removing which there is at least one component of the size k (1 <= k <= n <= 1000).

This is quite a common problem on dynamics, its solution can even be googled (1.5.2 https://archive.lksh.ru/2015/august/B/lectures/dp.ru.pdf)

Here is my code

def main():
    n, k = map(int, input().split())
    
    g = [[] for _ in range(n)]  # g[v] - список соседей вершины v
    
    for i in range(n - 1):
        u, v = map(int, input().split())  # дерево задано списком ребер, ребро - пара вершин через пробел
        u -= 1
        v -= 1
        g[v].append(u)
        g[u].append(v)
    
    INF = int(1e9 + 9)
    dp = [[INF] * (n + 1) for i in range(n)]
    sz = [1] * n  # sz[v] - размер поддерева вершины v, если подвесить дерево за вершину 0
    
    def dfs(v, par):
        dp[v][1] = 0
            
        for u in g[v]:
            if u != par:
                dfs(u, v)
                newdp = [x + 1 for x in dp[v]]
                for i in range(1, sz[v] + 1):
                    for j in range(1, sz[u] + 1):
                        newdp[i + j] = min(newdp[i + j], dp[v][i] + dp[u][j])
                dp[v] = list(newdp)
                sz[v] += sz[u]
                
        #print(dp[v])
        
    dfs(0, -1)
    answer = dp[0][k]
    for i in range(1, n):
        answer = min(answer, dp[i][k] + 1)
    print(answer)
    
    
main()

On several tests, the verification system issues a RE verdict. I rewritten this code on the pros, he went in, i.e. the problem is not in the algorithm. What are the options for why it doesn't work?