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 ji {
  int nex, to;
} edge[100005 << 1];
set<pair<int, int> > s[100005];
set<pair<int, int> >::iterator it;
priority_queue<pair<int, int> > q;
pair<int, int> ans[100005];
int E, n, r, x, y, z, cnt, head[100005], sz[100005], mx[100005], f[100005],
    d[100005];
long long m;
void add(int x, int y) {
  edge[E].nex = head[x];
  edge[E].to = y;
  head[x] = E++;
}
void dfs(int k, int fa) {
  sz[k] = 1;
  mx[k] = 0;
  for (int i = head[k]; i != -1; i = edge[i].nex)
    if (edge[i].to != fa) {
      dfs(edge[i].to, k);
      sz[k] += sz[edge[i].to];
      mx[k] = max(mx[k], sz[edge[i].to]);
    }
  if (max(n - sz[k], mx[k]) <= n / 2) r = k;
}
void dfs(int k, int fa, int sh) {
  f[k] = fa;
  d[k] = sh;
  m -= sh;
  s[x].insert(make_pair(sh, k));
  sz[k] = 1;
  for (int i = head[k]; i != -1; i = edge[i].nex)
    if (edge[i].to != fa) {
      dfs(edge[i].to, k, sh + 1);
      sz[k] += sz[edge[i].to];
    }
}
int main() {
  scanf("%d%lld", &n, &m);
  memset(head, -1, sizeof(head));
  for (int i = 1; i < n; i++) {
    scanf("%d%d", &x, &y);
    add(x, y);
    add(y, x);
  }
  dfs(1, 0);
  for (int i = head[r]; i != -1; i = edge[i].nex) {
    x = edge[i].to;
    dfs(x, r, 1);
    q.push(make_pair(sz[x], x));
  }
  if ((m > 0) || (m % 2)) {
    printf("NO");
    return 0;
  }
  m /= -2;
  while (m) {
    x = q.top().second;
    q.pop();
    if (sz[x] < 2) {
      printf("NO");
      return 0;
    }
    sz[x] -= 2;
    if (sz[x]) q.push(make_pair(sz[x], x));
    if ((*--s[x].end()).first - 1 <= m) {
      y = (*--s[x].end()).second;
      s[x].erase(--s[x].end());
      m -= d[y] - 1;
      z = f[y];
      bool flag = 0;
      for (int i = head[z]; i != -1; i = edge[i].nex)
        if ((edge[i].to != f[z]) && (edge[i].to != y) &&
            (s[x].find(make_pair(d[edge[i].to], edge[i].to)) != s[x].end())) {
          ans[++cnt] = make_pair(edge[i].to, y);
          s[x].erase(make_pair(d[edge[i].to], edge[i].to));
          flag = 1;
          break;
        }
      if (!flag) {
        ans[++cnt] = make_pair(z, y);
        s[x].erase(make_pair(d[z], z));
      }
    } else {
      it = lower_bound(s[x].begin(), s[x].end(), make_pair((int)m, 0));
      while ((*it).first == m) {
        bool flag = 0;
        y = (*it).second;
        for (int i = head[y]; i != -1; i = edge[i].nex)
          if ((edge[i].to != f[y]) &&
              (s[x].find(make_pair(d[edge[i].to], edge[i].to)) != s[x].end())) {
            ans[++cnt] = make_pair(y, edge[i].to);
            s[x].erase(make_pair(d[y], y));
            s[x].erase(make_pair(d[edge[i].to], edge[i].to));
            flag = 1;
            break;
          }
        if (flag) break;
        it++;
      }
      m = 0;
    }
  }
  while (!q.empty()) {
    x = q.top().second;
    q.pop();
    if (q.empty()) {
      ans[++cnt] = make_pair((*s[x].begin()).second, r);
      break;
    }
    y = q.top().second;
    q.pop();
    if (sz[x] > 1) q.push(make_pair(--sz[x], x));
    if (sz[y] > 1) q.push(make_pair(--sz[y], y));
    ans[++cnt] = make_pair((*s[x].begin()).second, (*s[y].begin()).second);
    s[x].erase(s[x].begin());
    s[y].erase(s[y].begin());
  }
  printf("YES\n");
  for (int i = 1; i <= cnt; i++) printf("%d %d\n", ans[i].first, ans[i].second);
}