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;
vector<vector<long long> > g;
vector<long long> dist, _sz;
void dfs1(long long v, long long p = -1) {
  _sz[v] = 1;
  for (long long i = 0; i < g[v].size(); i++) {
    long long to = g[v][i];
    if (to != p) {
      dfs1(to, v);
      _sz[v] += _sz[to];
    }
  }
}
long long n, k;
long long centroid(long long v, long long p = -1) {
  for (long long i = 0; i < g[v].size(); i++) {
    long long to = g[v][i];
    if (to != p && _sz[to] > n / 2) {
      return centroid(to, v);
    }
  }
  return v;
}
vector<long long> deg;
vector<set<pair<long long, long long> > > lca;
vector<long long> par, top;
vector<vector<long long> > g1;
long long minfunct = 0, maxfunct = 0;
void dfs2(long long v, long long p, long long t) {
  dist[v] = dist[p] + 1;
  _sz[v] = 1;
  par[v] = p;
  top[v] = t;
  auto it = find(g[v].begin(), g[v].end(), p);
  g[v].erase(it);
  deg[v] = g[v].size();
  for (long long i = 0; i < g[v].size(); i++) {
    long long to = g[v][i];
    dfs2(to, v, t);
    _sz[v] += _sz[to];
  }
  if (deg[v] != 0) {
    lca[t].insert({dist[v], v});
  }
  minfunct += (_sz[v] & 1);
  maxfunct += _sz[v];
}
void Delete(long long v) {
  v = par[v];
  deg[v]--;
  if (deg[v] == 0) {
    lca[top[v]].erase({dist[v], v});
  }
}
vector<bool> matched;
vector<long long> vec;
long long cnt = 0;
void dfs3(long long v, long long p = -1) {
  if (!matched[v]) {
    vec.push_back(v);
  }
  for (long long i = 0; i < g1[v].size(); i++) {
    long long to = g1[v][i];
    if (to == p) {
      continue;
    }
    dfs3(to, v);
  }
}
signed main() {
  cin >> n >> k;
  g.resize(n);
  _sz.resize(n);
  dist.resize(n);
  deg.resize(n);
  lca.resize(n);
  g1.resize(n);
  par.resize(n);
  top.resize(n);
  for (long long i = 0; i < n - 1; i++) {
    long long a, b;
    cin >> a >> b;
    a--;
    b--;
    g1[a].push_back(b);
    g1[b].push_back(a);
    g[a].push_back(b);
    g[b].push_back(a);
  }
  dfs1(0);
  long long c = centroid(0);
  set<pair<long long, long long> > sizes;
  for (long long i = 0; i < g[c].size(); i++) {
    long long to = g[c][i];
    dfs2(to, c, to);
    sizes.insert({_sz[to], to});
  }
  if (k < minfunct || k > maxfunct || (maxfunct - k) % 2 != 0) {
    cout << "NO";
    return 0;
  }
  cout << "YES\n";
  matched.resize(n, 0);
  while (maxfunct > k) {
    long long v = sizes.rbegin()->second;
    sizes.erase(*sizes.rbegin());
    long long maxdist = lca[v].rbegin()->first;
    if (maxfunct - 2 * maxdist <= k) {
      long long u = lca[v].lower_bound({(maxfunct - k) / 2, -1})->second;
      vector<long long> mass;
      while (g[u].size() > 0 && mass.size() < 2) {
        long long to = g[u].back();
        g[u].pop_back();
        if (!matched[to]) {
          mass.push_back(to);
        }
      }
      if (mass.size() < 2) {
        mass.push_back(u);
      }
      cout << mass[0] + 1 << " " << mass[1] + 1 << "\n";
      matched[mass[0]] = 1;
      matched[mass[1]] = 1;
      _sz[v] -= 2;
      Delete(mass[0]);
      Delete(mass[1]);
      break;
    } else {
      maxfunct -= 2 * maxdist;
      long long u = lca[v].rbegin()->second;
      vector<long long> mass;
      while (g[u].size() > 0 && mass.size() < 2) {
        long long to = g[u].back();
        g[u].pop_back();
        if (!matched[to]) {
          mass.push_back(to);
        }
      }
      if (mass.size() < 2) {
        mass.push_back(u);
      }
      assert(matched[mass[0]] == 0);
      assert(matched[mass[1]] == 0);
      cout << mass[0] + 1 << " " << mass[1] + 1 << "\n";
      matched[mass[0]] = 1;
      matched[mass[1]] = 1;
      _sz[v] -= 2;
      Delete(mass[0]);
      Delete(mass[1]);
      if (_sz[v]) {
        sizes.insert({_sz[v], v});
      }
    }
  }
  dfs3(c);
  long long h = vec.size() / 2;
  for (long long i = 0; i < vec.size() / 2; i++) {
    cout << vec[i] + 1 << " " << vec[i + h] + 1 << "\n";
  }
  return 0;
}