1067_B. Multihedgehog_28529
Someone give a strange birthday present to Ivan. It is hedgehog — connected undirected graph in which one vertex has degree at least 3 (we will call it center) and all other vertices has degree 1. Ivan thought that hedgehog is too boring and decided to make himself k-multihedgehog.

Let us define k-multihedgehog as follows:

  * 1-multihedgehog is hedgehog: it has one vertex of degree at least 3 and some vertices of degree 1.
  * For all k ≥ 2, k-multihedgehog is (k-1)-multihedgehog in which the following changes has been made for each vertex v with degree 1: let u be its only neighbor; remove vertex v, create a new hedgehog with center at vertex w and connect vertices u and w with an edge. New hedgehogs can differ from each other and the initial gift. 



Thereby k-multihedgehog is a tree. Ivan made k-multihedgehog but he is not sure that he did not make any mistakes. That is why he asked you to check if his tree is indeed k-multihedgehog.

Input

First line of input contains 2 integers n, k (1 ≤ n ≤ 10^{5}, 1 ≤ k ≤ 10^{9}) — number of vertices and hedgehog parameter.

Next n-1 lines contains two integers u v (1 ≤ u,    v ≤ n;    u ≠ v) — indices of vertices connected by edge.

It is guaranteed that given graph is a tree.

Output

Print "Yes" (without quotes), if given graph is k-multihedgehog, and "No" (without quotes) otherwise.

Examples

Input

14 2
1 4
2 4
3 4
4 13
10 5
11 5
12 5
14 5
5 13
6 7
8 6
13 6
9 6


Output

Yes


Input

3 1
1 3
2 3


Output

No

Note

2-multihedgehog from the first example looks like this:

<image>

Its center is vertex 13. Hedgehogs created on last step are: [4 (center), 1, 2, 3], [6 (center), 7, 8, 9], [5 (center), 10, 11, 12, 13].

Tree from second example is not a hedgehog because degree of center should be at least 3.
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Queue;
import java.util.Random;
import java.util.Set;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

/**
 * Created by timur on 28.03.15.
 */

public class TaskE {
    boolean eof;
    BufferedReader br;
    StringTokenizer st;
    PrintWriter out;

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

    public String nextToken() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                eof = true;
                return "-1";
            }
        }
        return st.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(nextToken());
    }

    public long nextLong() {
        return Long.parseLong(nextToken());
    }

    double nextDouble() {
        return Double.parseDouble(nextToken());
    }

    String nextLine() throws IOException {
        return br.readLine();
    }


    void run() throws IOException {
        InputStream input = System.in;
        PrintStream output = System.out;
        try {
            File f = new File("a.in");
            if (f.exists() && f.canRead()) {
                input = new FileInputStream(f);
                output = new PrintStream("a.out");
            }
        } catch (Throwable e) {
        }
        br = new BufferedReader(new InputStreamReader(input));
        out = new PrintWriter(output);
        solve();
        br.close();
        out.close();
    }

    final Random RNG = new Random();

    class Node<K> {
        K key;
        int priority;
        int size;
        Node<K> l;
        Node<K> r;

        public Node(K k) {
            priority = RNG.nextInt();
            this.key = k;
            size = 1;
        }
    }

    class MySetGen<K extends Comparable<K>> {


        Node<K> root;

        void add(K e) {
            if (contains(e)) {
                return;
            }
            Node<K>[] t = split(root, e);
            root = merge(t[0], new Node<K>(e));
            root = merge(root, t[1]);
        }

        private Node<K> merge(Node<K> l, Node<K> r) {
            if (l == null) {
                return r;
            }
            if (r == null) {
                return l;
            }
            Node<K> ret;
            if (l.priority > r.priority) {
                l.r = merge(l.r, r);
                ret = l;
            } else {
                r.l = merge(l, r.l);
                ret = r;
            }
            ret.size = 1;
            if (ret.l != null) {
                ret.size += ret.l.size;
            }
            if (ret.r != null) {
                ret.size += ret.r.size;
            }
            return ret;
        }

        private Node<K>[] split(Node<K> v, K e) {
            if (v == null) {
                return new Node[2];
            }
            Node<K>[] t;
            if (v.key.compareTo(e) < 0) {
                t = split(v.r, e);
                v.r = t[0];
                v.size = 1;
                if (v.l != null) {
                    v.size += v.l.size;
                }
                if (v.r != null) {
                    v.size += v.r.size;
                }
                t[0] = v;
            } else {
                t = split(v.l, e);
                v.l = t[1];
                v.size = 1;
                if (v.l != null) {
                    v.size += v.l.size;
                }
                if (v.r != null) {
                    v.size += v.r.size;
                }
                t[1] = v;
            }
            return t;
        }

        private Node<K> get(Node<K> v, K e) {
            if (v == null) {
                return null;
            }
            int comp = v.key.compareTo(e);
            if (comp == 0) {
                return v;
            } else if (comp < 0) {
                return get(v.r, e);
            } else {
                return get(v.l, e);
            }
        }

        boolean contains(K e) {
            return get(root, e) != null;
        }

    }

    /*int n, k, root = -1;

    ArrayList<Integer>[] inc;
    int[] vis;
    boolean upk = false;
    int lad = 0;

    void getRoot(int v, int d) {
        if (d >= k && inc[v].size() == 1) {
            upk = true;
            return;
        }
        int u;
        vis[v] = 1;
        for (int i = 0; i < inc[v].size(); i++) {
            u = inc[v].get(i);
            if (vis[u] == 0) {
                getRoot(u, d + 1);
                if (upk) {
                    lad++;
                    if (lad == k) {
                        root = v;
                    }
                    return;
                }
            }
        }
    }

    boolean check(int v, int d) {
        if (inc[v].size() == 1) {
            if (d != k)
                return false;
            return true;
        }
        if (v == root && inc[v].size() < 3) {
            return false;
        }
        if (v != root && inc[v].size() < 4) {
            return false;
        }
        int u;

        vis[v] = 1;
        for (int i = 0; i < inc[v].size(); i++) {
            u = inc[v].get(i);
            if (vis[u] == 0) {
                if (!check(u, d + 1))
                    return false;
            }
        }
        return true;
    }
*/
    void solve() {
        int n = nextInt();
        int k = nextInt();
        int u, v;

        TreeSet<Integer>[] vv = new TreeSet[n];
        for (int i = 0; i < n; i++) {
            vv[i] = new TreeSet<>();
        }
        for (int i = 0; i < n - 1; i++) {
            u = nextInt() - 1;
            v = nextInt() - 1;
            vv[u].add(v);
            vv[v].add(u);
        }

        Queue<Integer> prior = new ArrayDeque<>();
        Queue<Integer> vert = new ArrayDeque<>();

        int[] pp = new int[n];
        for (int i = 0; i < n; i++) {
            pp[i] = -1;
        }

        for (int i = 0; i < n; i++) {
            if (vv[i].size() == 1) {
                prior.add(0);
                vert.add(i);
                pp[i] = 0;
            }
        }
        try {
            int proc = 0, pr;
            int[] son = new int[n];
            while (!prior.isEmpty()) {
                u = vert.remove();
                pr = prior.remove();
                if (pr > k) {
                    out.print("No");
                    return;
                }
                proc++;
                if (pr == 0) {
                    //leaf
                    v = vv[u].first();
                    son[v]++;
                    vv[v].remove(u);
                    if (pp[v] == -1) {
                        pp[v] = pr + 1;
                    }
                    if (pp[v] != pr + 1) {
                        out.print("No");
                        return;
                    }
                    if ((vv[v].size() == 1 && pr < k - 1) || (vv[v].size() == 0 && proc == n - 1)) {
                        prior.add(pr + 1);
                        vert.add(v);
                    }
                } else if (vv[u].size() == 0) {
                    //root
                    if (proc != n || son[u] < 3 || pr != k) {
                        out.print("No");
                        return;
                    }
                } else {
                    //middle
                    if (son[u] < 3) {
                        out.print("No");
                        return;
                    }
                    v = vv[u].first();
                    son[v]++;
                    vv[v].remove(u);
                    if (pp[v] == -1) {
                        pp[v] = pr + 1;
                    }
                    if (pp[v] != pr + 1) {
                        out.print("No");
                        return;
                    }
                    if ((vv[v].size() == 1 && pr < k - 1) || (vv[v].size() == 0 && proc == n - 1)) {
                        prior.add(pr + 1);
                        vert.add(v);
                    }
                }
            }


            if (proc == n) {
                out.print("Yes");
            } else {
                out.print("No");
            }
        } catch (Throwable e) {
            out.print("No");
        }
        /*inc = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            inc[i] = new ArrayList<>();
        }
        for (int i = 0; i < n - 1; i++) {
            u = nextInt() - 1;
            v = nextInt() - 1;
            inc[u].add(v);
            inc[v].add(u);
        }
        vis = new int[n];

        Queue<Integer> prior = new ArrayDeque<>();
        Queue<Integer> vert = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            if (inc[i].size() == 1) {
                prior.add(0);
                vert.add(i);
            }
        }

        int proc = 0, pr;
        int[] son = new int[n];
        while (!prior.isEmpty()) {
            u = vert.remove();
            pr = prior.remove();

        }

        for (int i = 0; i < n; i++) {
            if (inc[i].size() > 1) {
                getRoot(i, 0);
                break;
            }
        }

        if (root == -1) {
            out.print("No");
            return;
        }
        for (int i = 0; i < n; i++) {
            vis[i] = 0;
        }
        if (check(root, 0)) {
            out.print("Yes");
        } else {
            out.print("No");
        }*/
    }
}
3 1
1 3
2 3
 14 2
1 4
2 4
3 4
4 13
10 5
11 5
12 5
14 5
5 13
6 7
8 6
13 6
9 6
 13 2
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
 14 3
1 4
2 4
3 4
4 13
10 5
11 5
12 5
14 5
5 13
6 7
8 6
13 6
9 6
 18 2
1 4
2 4
3 4
4 13
10 5
11 5
12 5
14 5
5 13
6 7
8 6
13 6
9 6
13 15
15 16
15 17
15 18
 25 2
1 2
1 3
1 4
2 5
2 6
2 7
3 8
3 9
3 10
4 11
4 12
4 13
4 14
14 15
14 16
14 17
4 18
18 19
18 20
18 21
1 22
22 23
22 24
22 25
 22 2
1 4
2 4
3 4
5 8
6 8
7 8
9 12
10 12
11 12
13 16
14 16
15 16
17 20
18 20
19 20
4 21
8 21
12 21
4 22
16 22
20 22
 33 2
3 13
17 3
2 6
5 33
4 18
1 2
31 5
4 19
3 16
1 3
9 2
10 3
5 1
5 28
21 4
7 2
1 4
5 24
30 5
14 3
3 11
27 5
8 2
22 4
12 3
20 4
26 5
4 23
32 5
25 5
15 3
29 5
 16 2
1 12
2 12
3 12
4 13
5 13
6 13
7 16
8 16
9 15
10 15
11 15
12 14
13 14
16 14
15 14
 8 2
8 2
2 5
5 1
7 2
2 4
3 5
5 6
 5 1
4 1
3 1
5 1
1 2
 1 1
 13 2
7 5
10 11
5 12
1 2
10 7
2 6
10 4
9 5
13 10
2 8
3 10
2 7
 2 1
2 1
 14 1
1 4
2 4
3 4
4 13
10 5
11 5
12 5
14 5
5 13
6 7
8 6
13 6
9 6
 10 980000000
5 4
7 1
3 2
10 6
2 8
6 4
7 9
1 8
3 10
 4 1
2 3
4 2
1 2
 2 1
1 2
 8 1
8 2
2 5
5 1
7 2
2 4
3 5
5 6
 16 2
1 12
2 12
3 12
4 13
5 13
6 13
7 14
8 14
9 15
10 15
11 15
12 16
13 16
14 16
15 16
 13 1000000000
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
 7 1
1 2
1 3
1 4
5 1
1 6
1 7
 21 2
3 1
4 1
5 1
6 2
7 2
8 2
1 2
9 1
9 10
9 11
9 12
10 13
10 14
10 15
11 16
11 17
11 18
12 19
12 20
12 21
 18 2
1 4
2 4
3 4
4 13
10 5
11 5
12 5
14 5
5 13
1 7
8 6
13 6
9 6
13 15
15 16
15 17
15 18
 18 2
1 4
2 4
3 4
4 13
10 6
11 5
12 5
14 5
5 13
6 7
8 6
13 6
9 6
13 15
15 16
15 17
15 18
 8 2
8 2
4 5
5 1
7 2
2 4
3 5
5 6
 5 1
4 1
3 2
5 1
1 2
 16 3
1 12
2 12
3 12
4 13
5 13
6 13
7 14
8 14
9 15
10 15
11 15
12 16
13 16
14 16
15 16
 21 2
3 1
4 1
5 1
6 2
7 2
8 2
1 2
9 1
9 10
14 11
9 12
10 13
10 14
10 15
11 16
11 17
11 18
12 19
12 20
12 21
 13 2
1 2
2 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
 33 2
3 13
17 3
2 6
5 33
4 18
1 2
31 5
4 19
3 16
1 3
9 2
10 3
5 1
5 28
21 4
7 2
1 4
5 24
30 5
14 3
3 11
27 5
8 2
22 4
12 3
20 4
26 5
4 23
32 1
25 5
15 3
29 5
 8 2
8 2
2 5
3 1
7 2
2 4
3 5
5 6
 1 1
4 1
3 1
5 1
1 2
 1 2
 2 2
2 1
 10 980000000
5 4
7 1
3 2
10 6
3 8
6 4
7 9
1 8
3 10
 4 1
2 3
4 1
1 2
 13 1000000000
1 2
1 3
1 4
1 5
2 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
 33 2
4 13
17 3
2 6
5 33
4 18
1 2
31 5
4 19
3 16
1 3
9 2
10 3
5 1
5 28
21 4
7 2
1 4
5 24
30 5
14 3
3 11
27 5
8 2
22 4
12 3
20 4
26 5
4 23
32 1
25 5
15 3
29 5
 14 3
1 4
2 4
3 4
4 13
10 5
11 5
12 5
14 5
5 13
6 7
8 4
13 6
9 6
 22 2
1 4
2 4
3 4
5 8
6 8
7 8
9 12
10 12
11 12
13 16
14 16
15 16
17 20
18 20
19 20
4 21
8 21
12 1
4 22
16 22
20 22
 8 1
8 2
2 5
5 1
7 2
2 4
3 4
5 6
 10 980000000
5 4
7 1
3 2
10 6
2 8
1 4
7 9
1 8
3 10
 4 1
1 3
4 2
1 2
 8 1
8 2
2 5
6 1
7 2
2 4
3 5
5 6
 21 2
3 1
4 1
5 2
6 2
7 2
8 2
1 2
9 1
9 10
9 11
9 12
10 13
10 14
10 15
11 16
11 17
11 18
12 19
12 20
12 21
 21 2
3 1
4 1
5 1
6 2
7 2
8 2
1 2
9 1
9 10
20 11
9 12
10 13
10 14
10 15
11 16
11 17
11 18
12 19
12 20
12 21
 1 1
4 1
3 1
6 1
1 2
 10 1323614652
5 4
7 1
3 2
10 6
3 8
6 4
7 9
1 8
3 10
 33 2
4 13
17 3
2 6
5 33
4 18
1 2
31 5
4 19
3 16
1 3
9 2
10 3
5 1
5 28
21 4
7 2
1 4
5 24
30 5
14 3
3 11
27 5
8 2
22 4
12 3
20 4
26 5
4 23
32 1
25 5
15 6
29 5
 22 2
1 4
2 4
3 4
5 8
6 8
7 8
9 14
10 12
11 12
13 16
14 16
15 16
17 20
18 20
19 20
4 21
8 21
12 1
4 22
16 22
20 22
 8 1
8 2
2 5
5 1
7 1
2 4
3 4
5 6
 21 2
3 1
4 1
5 2
6 2
7 2
8 2
1 2
9 1
9 10
9 11
9 12
10 13
10 14
10 15
11 16
11 17
11 18
12 19
4 20
12 21
 21 2
3 1
4 1
5 1
6 2
7 2
8 2
1 2
9 1
9 10
20 11
9 12
10 13
10 14
10 15
5 16
11 17
11 18
12 19
12 20
12 21
 1 1
4 1
3 1
6 1
0 2
 8 1
8 2
2 5
5 1
7 1
1 4
3 4
5 6
 21 2
3 1
4 1
5 2
6 2
7 2
8 2
1 2
9 1
9 10
9 11
9 12
3 13
10 14
10 15
11 16
11 17
11 18
12 19
4 20
12 21
 1 1
4 1
3 1
6 1
-1 2
 8 1
8 2
2 5
5 1
7 1
1 4
3 8
5 6
 1 1
4 1
3 1
0 1
-1 2
 8 1
8 2
2 5
5 1
7 1
1 4
3 6
5 6
 1 1
4 1
3 2
0 1
-1 2
 1 2
4 1
3 2
0 1
-1 2
 1 2
4 1
3 2
0 1
-1 0
 1 1
4 1
3 2
0 1
-1 0
 22 2
1 4
2 4
3 4
5 8
6 8
7 8
9 12
10 12
11 12
13 16
14 16
15 13
17 20
18 20
19 20
4 21
8 21
12 21
4 22
16 22
20 22
 16 2
1 12
2 12
3 12
4 13
5 13
6 13
7 16
8 13
9 15
10 15
11 15
12 14
13 14
16 14
15 14
 1 1
1 2
 8 1
8 2
2 5
5 1
7 2
2 4
3 5
4 6

No
 Yes
 No
 No
 Yes
 No
 No
 Yes
 No
 No
 Yes
 No
 No
 No
 No
 No
 Yes
 No
 No
 No
 No
 Yes
 No
 No
 Yes
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
 No
