Far Vertices

!/bin/python3

import math
import os
import random
import re
import sys
from collections import Counter

def farVertices(n, k, edges):
    tree = {}
    for edge in edges:
        tree[edge[0],edge[1]] = 1
        tree[edge[1],edge[0]] = 1
    tree_paths = len(tree)
    cont_flag = True
    while cont_flag:
        for edge in edges:
            matches = {x:y for x,y in tree.items() if edge[1] == x[0]}
            for match in matches.keys():
                if (edge[0],match[1]) not in tree.keys() and edge[0] != match[1]:
                    tree[edge[0],match[1]] = matches[match] + 1
                    tree[match[1],edge[0]] = matches[match] + 1
            matches = {x:y for x,y in tree.items() if edge[0] == x[1]}
            for match in matches.keys():
                if (edge[1],match[0]) not in tree.keys() and edge[1] != match[0]:
                    tree[edge[1],match[0]] = matches[match] + 1
                    tree[match[0],edge[1]] = matches[match] + 1
        if len(tree) == tree_paths:
            cont_flag = False
        tree_paths = len(tree)
    removed = 0
    cont_flag = True
    while cont_flag:
        matches = [x[0] for x,y in tree.items() if y>k]
        if len(matches)==0:
            cont_flag = False
        else:
            removed += 1
            match_count = Counter(matches)
            maxcount = max([y for x,y in match_count.items()])
            match_max = [x for x,y in match_count.items() if y==maxcount]
            remove_node = match_max[0]
            nodes_to_remove = [x for x in tree.keys() if 
                                 x[0]==remove_node or x[1]==remove_node]
            print(nodes_to_remove)
            for node in nodes_to_remove:
                del tree[node]
    return removed
    

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    first_multiple_input = input().rstrip().split()

    n = int(first_multiple_input[0])

    k = int(first_multiple_input[1])

    edges = []

    for _ in range(n - 1):
        edges.append(list(map(int, input().rstrip().split())))

    result = farVertices(n, k, edges)

    fptr.write(str(result) + '\n')

    fptr.close()