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;
const int N = 1e5 + 5;
int n, cen, t;
long long m, mn, mx;
int sz[N], mxs[N], dep[N], gsz[N], fa[N];
vector<int> nei[N];
set<int> rs[N], son[N];
priority_queue<pair<int, int> > ld[N], pq;
void dfs0(int x, int p) {
  sz[x] = 1;
  for (int i = 0; i < int(nei[x].size()); i++) {
    int to = nei[x][i];
    if (to != p) {
      dfs0(to, x);
      sz[x] += sz[to];
      mxs[x] = max(mxs[x], sz[to]);
    }
  }
}
void dfs1(int x, int p) {
  fa[x] = p;
  sz[x] = 1;
  son[p].insert(x);
  dep[x] = dep[p] + 1;
  ld[t].push(make_pair(dep[x], x));
  rs[t].insert(x);
  gsz[t]++;
  for (int i = 0; i < int(nei[x].size()); i++) {
    int to = nei[x][i];
    if (to != p) {
      dfs1(to, x);
      sz[x] += sz[to];
    }
  }
  mn += 1ll * sz[x] % 2ll;
  mx += 1ll * sz[x];
}
int main() {
  scanf("%d%lld", &n, &m);
  for (int i = 1; i < n; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    nei[x].push_back(y);
    nei[y].push_back(x);
  }
  dfs0(1, -1);
  for (int i = 1; i <= n; i++)
    if (max(mxs[i], n - sz[i]) <= n / 2) cen = i;
  for (int i = 0; i < int(nei[cen].size()); i++) {
    t++;
    int to = nei[cen][i];
    dfs1(to, cen);
    pq.push(make_pair(gsz[t], t));
  }
  if (mn > m || mx < m || mx % 2ll != m % 2ll) {
    puts("NO");
    return 0;
  }
  puts("YES");
  m = (mx - m) / 2ll;
  while (m != 0ll) {
    pair<int, int> px = pq.top();
    pq.pop();
    int gp = px.second;
    while (true) {
      pair<int, int> x = ld[gp].top();
      ld[gp].pop();
      if (son[x.second].empty() || x.first > m) continue;
      m -= 1ll * x.first;
      set<int>::iterator it = son[x.second].begin();
      printf("%d ", *it);
      rs[gp].erase(*it);
      son[x.second].erase(it);
      if (!son[x.second].empty()) {
        it = son[x.second].begin();
        printf("%d\n", *it);
        rs[gp].erase(*it);
        son[x.second].erase(it);
        ld[gp].push(x);
      } else {
        printf("%d\n", x.second);
        rs[gp].erase(x.second);
        son[fa[x.second]].erase(x.second);
      }
      break;
    }
    px.first -= 2;
    if (px.first) pq.push(px);
  }
  rs[t + 1].insert(cen);
  pq.push(make_pair(1, t + 1));
  while (!pq.empty()) {
    pair<int, int> px = pq.top();
    pq.pop();
    pair<int, int> py = pq.top();
    pq.pop();
    px.first--;
    py.first--;
    set<int>::iterator itx = rs[px.second].begin();
    set<int>::iterator ity = rs[py.second].begin();
    printf("%d %d\n", *itx, *ity);
    rs[px.second].erase(itx);
    rs[py.second].erase(ity);
    if (px.first) pq.push(px);
    if (py.first) pq.push(py);
  }
  return 0;
}