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 long long mod = 1000000007;
const unsigned gen_seed =
    std::chrono::system_clock::now().time_since_epoch().count();
std::mt19937_64 gen(gen_seed);
std::vector<std::vector<int> > g;
int n, l;
std::vector<int> tin, tout;
int timer;
vector<vector<int> > up;
std::vector<int> lev;
void dfs(int v, int p, int curl) {
  lev[v] = curl;
  tin[v] = ++timer;
  up[v][0] = p;
  for (int i = 1; i <= l; ++i) up[v][i] = up[up[v][i - 1]][i - 1];
  for (size_t i = 0; i < g[v].size(); ++i) {
    int to = g[v][i];
    if (to != p) dfs(to, v, curl + 1);
  }
  tout[v] = ++timer;
}
std::vector<int> maj;
std::vector<int> st;
int go(int v, int p) {
  st[v] = 1;
  for (auto u : g[v]) {
    if (u == p) continue;
    st[v] += go(u, v);
  }
  for (auto u : g[v]) {
    if (st[u] * 2 >= n) maj[v] = u;
  }
  return st[v];
}
bool upper(int a, int b) { return tin[a] <= tin[b] && tout[a] >= tout[b]; }
int lca(int a, int b) {
  if (upper(a, b)) return a;
  if (upper(b, a)) return b;
  for (int i = l; i >= 0; --i)
    if (!upper(up[a][i], b)) a = up[a][i];
  return up[a][0];
}
int dist(int a, int b) {
  int c = lca(a, b);
  return lev[a] + lev[b] - 2 * lev[c];
}
std::vector<int> getpath(int a, int b) {
  int c = lca(a, b);
  std::vector<int> ret;
  std::vector<int> rev;
  while (a != c) {
    ret.push_back(a);
    a = up[a][0];
  }
  while (b != c) {
    rev.push_back(b);
    b = up[b][0];
  }
  reverse((rev).begin(), (rev).end());
  ret.push_back(c);
  for (auto x : rev) ret.push_back(x);
  return ret;
}
long long todist(std::vector<int>& x) {
  long long ret = 0;
  for (int i = 0; i < n; i++)
    if (x[i] > i) ret += dist(x[i], i);
  return ret;
}
std::vector<std::pair<int, int> > prmin;
int greed(int v, int p) {
  std::vector<int> stray;
  for (auto u : g[v]) {
    if (u == p) continue;
    int ret = greed(u, v);
    if (ret != -1) stray.push_back(ret);
  }
  stray.push_back(v);
  while (stray.size() >= 2) {
    int p = stray.size();
    prmin.push_back(make_pair(stray[p - 1], stray[p - 2]));
    stray.pop_back();
    stray.pop_back();
  }
  int ret = -1;
  if (stray.size() == 1) ret = stray[0];
  return ret;
}
std::vector<int> tomin;
int main() {
  long long k;
  scanf("%d %lld", &n, &k);
  l = 1;
  while ((1 << l) <= n) ++l;
  tin.resize(n), tout.resize(n), up.resize(n);
  for (int i = 0; i < n; ++i) up[i].resize(l + 1);
  lev.resize(n);
  st = std::vector<int>(n, 0);
  g.resize(n);
  for (int i = 0; i < n - 1; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    u--;
    v--;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  if (n == 2) {
    if (k != 1)
      cout << "NO\n";
    else {
      cout << "YES\n";
      cout << "1 2\n";
    }
    exit(0);
  }
  for (int i = 0; i < n; i++) maj.push_back(i);
  go(0, 0);
  int root = 0;
  while (maj[root] != root) root = maj[root];
  dfs(root, root, 0);
  long long mx = 0;
  for (int i = 0; i < n; i++) mx += lev[i];
  std::vector<std::pair<int, int> > ord;
  for (int i = 0; i < n; i++) ord.push_back(make_pair(tin[i], i));
  sort((ord).begin(), (ord).end());
  std::vector<std::pair<int, int> > prmax;
  for (int i = 0; i < n / 2; i++)
    prmax.push_back(make_pair(ord[i].second, ord[i + n / 2].second));
  greed(root, root);
  long long mn = 0;
  for (int i = 0; i < n / 2; i++) {
    mn += dist(prmin[i].first, prmin[i].second);
  }
  std::vector<int> tomax(n);
  tomin.resize(n);
  for (int i = 0; i < n / 2; i++) {
    tomin[prmin[i].first] = prmin[i].second;
    tomin[prmin[i].second] = prmin[i].first;
    tomax[prmax[i].first] = prmax[i].second;
    tomax[prmax[i].second] = prmax[i].first;
  }
  if (k % 2 != mn % 2 || k < mn || k > mx) {
    cout << "NO\n";
    exit(0);
  }
  int eq = 0;
  while (1) {
    if (eq == n) break;
    if (tomin[eq] == tomax[eq]) {
      eq++;
      continue;
    }
    int cp = tomin[tomax[eq]];
    int neq = tomin[eq];
    int xeq = tomax[eq];
    if (mn == k) break;
    swap(tomin[cp], tomin[eq]);
    swap(tomin[xeq], tomin[neq]);
    long long md =
        mn - dist(eq, neq) - dist(xeq, cp) + dist(eq, xeq) + dist(cp, neq);
    if (md == k)
      break;
    else if (md < k) {
      eq++;
      mn = md;
      continue;
    } else {
      swap(tomin[cp], tomin[eq]);
      swap(tomin[xeq], tomin[neq]);
      std::vector<int> path = getpath(eq, cp);
      for (auto x : path) {
        if (x == tomin[eq]) {
          eq = tomin[eq];
          path = getpath(eq, cp);
          break;
        }
      }
      int q = path.size();
      for (int i = 0; i < q - 1; i++) {
        int a = path[i];
        int b = path[i + 1];
        int ca = tomin[a];
        int cb = tomin[b];
        swap(tomin[a], tomin[b]);
        swap(tomin[ca], tomin[cb]);
        if (ca != b)
          mn += dist(a, cb) + dist(b, ca) - dist(a, ca) - dist(b, cb);
        if (mn == k) {
          printf("YES\n");
          for (int i = 0; i < n; i++) {
            if (tomin[i] > i) printf("%d %d\n", i + 1, tomin[i] + 1);
          }
          exit(0);
        }
      }
      for (int i = q - 3; i >= 0; i--) {
        int a = path[i];
        int b = path[i + 1];
        int ca = tomin[a];
        int cb = tomin[b];
        swap(tomin[a], tomin[b]);
        swap(tomin[ca], tomin[cb]);
        if (ca != b)
          mn += dist(a, cb) + dist(b, ca) - dist(a, ca) - dist(b, cb);
        if (mn == k) {
          printf("YES\n");
          for (int i = 0; i < n; i++) {
            if (tomin[i] > i) printf("%d %d\n", i + 1, tomin[i] + 1);
          }
          exit(0);
        }
      }
      printf("NO\n");
      exit(0);
    }
  }
  printf("YES\n");
  for (int i = 0; i < n; i++) {
    if (tomin[i] > i) printf("%d %d\n", i + 1, tomin[i] + 1);
  }
}