Problem: You are given an integer k and a tree T with n nodes (n is even).

Let dist(u, v) be the number of edges on the shortest path from node u to node v in T.

Let us define a undirected weighted complete graph G = (V, E) as following: 

  * V = \\{x ∣ 1 ≤ x ≤ n \} i.e. the set of integers from 1 to n
  * E = \{(u, v, w) ∣ 1 ≤ u, v ≤ n, u ≠ v, w = dist(u, v) \} i.e. there is an edge between every pair of distinct nodes, the weight being the distance between their respective nodes in T 



Your task is simple, find a perfect matching in G with total edge weight k (1 ≤ k ≤ n^2).

Input

The first line of input contains two integers n, k (2 ≤ n ≤ 100 000, n is even, 1 ≤ k ≤ n^2): number of nodes and the total edge weight of the perfect matching you need to find.

The i-th of the following n - 1 lines contains two integers v_i, u_i (1 ≤ v_i, u_i ≤ n) denoting an edge between v_i and u_i in T. It is guaranteed that the given graph is a tree. 

Output

If there are no matchings that satisfy the above condition, output "NO" (without quotes) on a single line. 

Otherwise, you should output "YES" (without quotes) on the first line of output.

You should then output n/2 lines, the i-th line containing p_i, q_i (1 ≤ p_i, q_i ≤ n): the i-th pair of the matching.

Examples

Input


4 2
1 2
2 3
3 4


Output


YES
2 1
3 4


Input


4 4
1 2
2 3
3 4


Output


YES
3 1
2 4

Note

A tree is a connected acyclic undirected graph.

A matching is set of pairwise non-adjacent edges, none of which are loops; that is, no two edges share a common vertex. 

A perfect matching is a matching which matches all vertices of the graph; that is, every vertex of the graph is incident to exactly one edge of the matching.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
struct LCT {
  struct Node {
    int parent;
    int child[2];
    int sum;
    int sze;
    bool flag;
    int v;
    bool rev;
  } tree[100005];
  int st[100005], top;
  bool nroot(int x) {
    return tree[tree[x].parent].child[0] == x ||
           tree[tree[x].parent].child[1] == x;
  }
  void pushup(int x) {
    tree[x].sze = tree[tree[x].child[0]].sze + tree[tree[x].child[1]].sze + 1;
    tree[x].sum =
        tree[tree[x].child[0]].sum + tree[tree[x].child[1]].sum + tree[x].v;
  }
  void pushr(int x) {
    swap(tree[x].child[0], tree[x].child[1]);
    tree[x].rev ^= 1;
  }
  void pushdown(int x) {
    if (tree[x].rev) {
      if (tree[x].child[0]) pushr(tree[x].child[0]);
      if (tree[x].child[1]) pushr(tree[x].child[1]);
      tree[x].rev = 0;
    }
    if (tree[x].flag) {
      if (tree[x].child[0]) {
        tree[tree[x].child[0]].flag ^= 1;
        tree[tree[x].child[0]].sum =
            tree[tree[x].child[0]].sze - tree[tree[x].child[0]].sum;
        tree[tree[x].child[0]].v ^= 1;
      }
      if (tree[x].child[1]) {
        tree[tree[x].child[1]].flag ^= 1;
        tree[tree[x].child[1]].sum =
            tree[tree[x].child[1]].sze - tree[tree[x].child[1]].sum;
        tree[tree[x].child[1]].v ^= 1;
      }
      tree[x].flag = 0;
    }
  }
  bool identify(int x) { return tree[tree[x].parent].child[1] == x; }
  void connect(int x, int pa, bool flag) {
    tree[x].parent = pa;
    tree[pa].child[flag] = x;
  }
  void rotate(int x) {
    int y = tree[x].parent;
    int r = tree[y].parent;
    bool flag_y = identify(y);
    bool flag_x = identify(x);
    int b = tree[x].child[!flag_x];
    if (nroot(y)) tree[r].child[flag_y] = x;
    tree[x].parent = r;
    connect(b, y, flag_x);
    connect(y, x, !flag_x);
    pushup(y);
    pushup(x);
  }
  void splay(int at) {
    top = 0;
    int pa = at;
    st[++top] = pa;
    while (nroot(pa)) {
      pa = tree[pa].parent;
      st[++top] = pa;
    }
    while (top) pushdown(st[top--]);
    while (nroot(at)) {
      pa = tree[at].parent;
      if (!nroot(pa))
        rotate(at);
      else if (identify(at) == identify(pa)) {
        rotate(pa);
        rotate(at);
      } else {
        rotate(at);
        rotate(at);
      }
    }
  }
  void access(int x) {
    int last = 0;
    while (x) {
      splay(x);
      tree[x].child[1] = last;
      pushup(x);
      last = x;
      x = tree[x].parent;
    }
  }
  void makeroot(int x) {
    access(x);
    splay(x);
    pushr(x);
  }
  int findroot(int x) {
    access(x);
    splay(x);
    while (tree[x].child[0]) {
      pushdown(x);
      x = tree[x].child[0];
    }
    return x;
  }
  void split(int x, int y) {
    makeroot(x);
    access(y);
    splay(y);
  }
  void link(int x, int y) {
    makeroot(x);
    if (findroot(y) != x) tree[x].parent = y;
    pushup(y);
  }
  void cut(int x, int y) {
    makeroot(x);
    if (findroot(y) == x && tree[x].parent == y && !tree[x].child[1]) {
      tree[x].parent = 0;
      tree[y].child[0] = 0;
      pushup(y);
    }
  }
} L;
struct Edge {
  int to;
  int nxt;
} e[200005];
int n, edgenum, head[100005], sze[100005], maxs[100005], dep[100005], root,
    pa[100005], ans;
long long k, maxv;
int match[100005];
bool flag[100005];
priority_queue<pair<int, int> > q;
vector<int> s[100005];
void add(int u, int v) {
  e[++edgenum].to = v;
  e[edgenum].nxt = head[u];
  head[u] = edgenum;
}
void dfs1(int node) {
  sze[node] = 1;
  for (int hd = head[node]; hd; hd = e[hd].nxt) {
    int to = e[hd].to;
    if (to == pa[node]) continue;
    pa[to] = node;
    dfs1(to);
    sze[node] += sze[to];
    maxs[node] = max(maxs[node], sze[to]);
  }
  maxs[node] = max(maxs[node], n - sze[node]);
  if (maxs[node] < maxs[root]) root = node;
  maxv += min(sze[node], n - sze[node]);
}
void dfs2(int node, int r) {
  sze[node] = 1;
  dep[node] = dep[pa[node]] + 1;
  s[r].push_back(node);
  for (int hd = head[node]; hd; hd = e[hd].nxt) {
    int to = e[hd].to;
    if (to == pa[node]) continue;
    pa[to] = node;
    dfs2(to, r);
    sze[node] += sze[to];
  }
}
void dfs3(int node) {
  sze[node] = 1;
  for (int hd = head[node]; hd; hd = e[hd].nxt) {
    int to = e[hd].to;
    if (to == pa[node] || flag[to]) continue;
    pa[to] = node;
    dfs3(to);
    sze[node] += sze[to];
    if (!match[to]) {
      if (match[node]) {
        int v = match[node];
        match[v] = to, match[to] = v;
        match[node] = 0;
      } else
        match[node] = to, match[to] = node;
    }
  }
}
bool cmp(int a, int b) { return dep[a] < dep[b]; }
int main() {
  maxs[0] = 2147483647;
  scanf("%d%lld", &n, &k);
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    add(u, v);
    add(v, u);
  }
  dfs1(1);
  if (k > maxv || ((maxv - k) & 1)) {
    printf("NO\n");
    return 0;
  }
  memset(pa, 0, sizeof(pa));
  sze[root] = 0;
  for (int hd = head[root]; hd; hd = e[hd].nxt) {
    int to = e[hd].to;
    pa[to] = root;
    dfs2(to, to);
    sort(s[to].begin(), s[to].end(), cmp);
    q.push(make_pair(sze[to], to));
  }
  s[root].push_back(root);
  q.push(make_pair(1, root));
  for (int i = 1; i <= n; i++) {
    if (sze[i] & 1) L.tree[i].v = L.tree[i].sum = 1, ans++;
    L.tree[i].sze = 1;
  }
  for (int i = 1; i <= n; i++) {
    if (i == root) continue;
    L.tree[i].parent = pa[i];
  }
  if (k < ans) {
    printf("NO\n");
    return 0;
  }
  printf("YES\n");
  while (k >= ans) {
    int u = q.top().second;
    q.pop();
    int v = q.top().second;
    q.pop();
    int x = s[u].back();
    int y = s[v].back();
    L.split(x, y);
    if (k - (L.tree[y].sze - 1) >
        ans - L.tree[y].sum + (L.tree[y].sze - 1 - L.tree[y].sum)) {
      k -= L.tree[y].sze - 1;
      ans = ans - L.tree[y].sum + (L.tree[y].sze - 1 - L.tree[y].sum);
      L.tree[y].sum = L.tree[y].sze - L.tree[y].sum;
      L.tree[y].flag ^= 1;
      L.tree[y].v ^= 1;
      L.splay(root);
      L.tree[root].v = 0;
      L.pushup(x);
      L.cut(x, pa[x]);
      L.cut(y, pa[y]);
      s[u].pop_back();
      s[v].pop_back();
      sze[u]--;
      sze[v]--;
      flag[x] = flag[y] = 1;
      if (sze[u]) q.push(make_pair(sze[u], u));
      if (sze[v]) q.push(make_pair(sze[v], v));
      printf("%d %d\n", x, y);
    } else
      break;
  }
  dfs3(root);
  k -= ans;
  for (int i = 1; i <= n; i++) {
    if (!k) break;
    if (flag[i]) continue;
    if (i != root && sze[i] % 2 == 0) {
      int j = pa[i];
      int ii = match[i];
      int jj = match[j];
      match[i] = jj, match[jj] = i;
      match[ii] = j, match[j] = ii;
      k -= 2;
    }
  }
  for (int i = 1; i <= n; i++)
    if (match[i] > i) printf("%d %d\n", i, match[i]);
  return 0;
}