from sys import stdin
import sys
import re

maxn = 10**5

number = r"[1-9][0-9]*"
two_numbers = f"{number} {number}$"

nk = stdin.readline()
assert re.match(two_numbers, nk), "Expected the first line to contain two integers (n, k)."
n, k = map(int, nk.split())

assert 1 <= n <= maxn, f"n doesn't meet 1 <= {n} <= {maxn}."
assert 1 <= k <= n, f"k doesn't meet 1 <= {k} <= {n}."

g, edges, viz = [[] for _ in range(n)], set(), [False] * n
for _ in range(n-1):
    xy = stdin.readline()
    assert re.match(two_numbers, xy), f"Expected the {_+1}-th edge to contain two integers (x, y)."
    x, y = map(int, xy.split())

    assert 1 <= x <= n, f"1 <= {x} <= {n}"
    assert 1 <= y <= n, f"1 <= {y} <= {n}"
    assert x != y, f"Can't have an edge ({x}, {y}) from a node to itself."

    if x > y:
        x, y = y, x

    assert (x, y) not in edges, f"Can't have a duplicate edge ({x}, {y}) in the tree."
    edges.add((x, y))

    x -= 1; y -= 1
    g[x].append(y)
    g[y].append(x)

stk = [(0, -1)]
while stk:
    nod, t = stk.pop()
    viz[nod] = True
    for nn in g[nod]:
        if not viz[nn]:
            stk.append((nn, nod))
        else:
            assert nn == t, "The given graph mustn't have a cycle in it."

assert all(viz), "All nodes must be accessible from the root node 1."

assert len(stdin.readline()) == 0, "The input contains unexpected data."
sys.exit(42)