import java.io.*;
import java.util.*;

public class Validate {
	
	static final int MAXN = 100000;
	
	class Edge {
		int x, y;
		
		Edge(int x, int y) {
			this.x = x;
			this.y = y;
		}
		
		@Override
		public boolean equals(Object o) {
			Edge p = (Edge)o;
			return p.x == x && p.y == y;
		}
		
		@Override
		public int hashCode() {
			return 239017 * x + y;
		}
	}
	
	ArrayList<Integer>[] G;
	boolean[] u;

	void dfs(int i) {
		u[i] = true;
		for (int j : G[i]) {
			if (!u[j]) {
				dfs(j);
			}
		}
	}

    public void run() {
        StrictScanner inf = new StrictScanner(System.in);

        int n = inf.nextInt();
        ensureLimits(n, 3, MAXN, "n");
        ensureLimits(inf.nextInt(), 1, n - 1, "d");
        inf.nextLine();
        int[] a = new int[n];
        int[] b = new int[n];
        Set<Edge> edges = new HashSet<Edge>();
        G = new ArrayList[n];
        for (int i = 0; i < n; i++) {
        	G[i] = new ArrayList<Integer>();
        }
        for (int i = 0; i < n - 1; i++) {
        	a[i] = inf.nextInt();
        	b[i] = inf.nextInt();
        	ensureLimits(a[i], 1, n, "a " + i);
        	ensureLimits(b[i], 1, n, "b " + i);
        	ensure(a[i] != b[i], "Equal vertices");
        	inf.nextLine();
            a[i]--;
            b[i]--;

        	Edge p = new Edge(a[i], b[i]);
        	ensure(!edges.contains(p), "Equal edges!");
        	edges.add(p);
        	p = new Edge(b[i], a[i]);
        	ensure(!edges.contains(p), "Equal edges!");
        	edges.add(p);
        	
        	G[a[i]].add(b[i]);
        	G[b[i]].add(a[i]);
        }
        inf.close();
        u = new boolean[n];
        dfs(0);
        for (int i = 0; i < n; i++) {
        	ensure(u[i], "Graph is not connected");
        }
    }

    public static void main(String[] args) {
        new Validate().run();
    }

    public class StrictScanner {
        private final BufferedReader in;
        private String line = "";
        private int pos;
        private int lineNo;

        public StrictScanner(InputStream source) {
            in = new BufferedReader(new InputStreamReader(source));
            nextLine();
        }

        public void close() {
            ensure(line == null, "Extra data at the end of file");
            try {
                in.close();
            } catch (IOException e) {
                throw new AssertionError("Failed to close with " + e);
            }
        }

        public void nextLine() {
            ensure(line != null, "EOF");
            ensure(pos == line.length(),  "Extra characters on line " + lineNo);
            try {
                line = in.readLine();
            } catch (IOException e) {
                throw new AssertionError("Failed to read line with " + e);
            }
            pos = 0;
            lineNo++;
        }

        public String next() {
            ensure(line != null, "EOF");
            ensure(line.length() > 0,  "Empty line " + lineNo);
            if (pos == 0)
                ensure(line.charAt(0) > ' ',  "Line " + lineNo + " starts with whitespace");
            else {
                ensure(pos < line.length(),  "Line " + lineNo + " is over");
                ensure(line.charAt(pos) == ' ',  "Wrong whitespace on line " + lineNo);
                pos++;
                ensure(pos < line.length(),  "Line " + lineNo + " is over");
                ensure(line.charAt(0) > ' ',  "Line " + lineNo + " has double whitespace");
            }
            StringBuilder sb = new StringBuilder();
            while (pos < line.length() && line.charAt(pos) > ' ')
                sb.append(line.charAt(pos++));
            return sb.toString();
        }

        public int nextInt() {
            String s = next();
            ensure(s.length() == 1 || s.charAt(0) != '0',  "Extra leading zero in number " + s + " on line " + lineNo);
            ensure(s.charAt(0) != '+',  "Extra leading '+' in number " + s + " on line " + lineNo);
            try {
                return Integer.parseInt(s);
            } catch (NumberFormatException e) {
                throw new AssertionError("Malformed number " + s + " on line " + lineNo);
            }
        }

        public double nextDouble() {
            String s = next();
            ensure(s.length() == 1 || s.startsWith("0.") || s.charAt(0) != '0',  "Extra leading zero in number " + s + " on line " + lineNo);
            ensure(s.charAt(0) != '+',  "Extra leading '+' in number " + s + " on line " + lineNo);
            try {
                return Double.parseDouble(s);
            } catch (NumberFormatException e) {
                throw new AssertionError("Malformed number " + s + " on line " + lineNo);
            }
        }
    }

    void ensure(boolean b, String message) {
        if (!b) {
            throw new AssertionError(message);
        }
    }
    
    void ensureLimits(int n, int from, int to, String name) {
        ensure(from <= n && n <= to, name + " must be from " + from + " to " + to);
    }

}