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 = 100005, INF = 0X3F3F3F3F;
const long long INFLL = 0X3F3F3F3F3F3F3F3FLL;
int n;
long long K;
int pp = 1, lnk[N], nxt[N * 2], _lnk[N * 2], _nxt[N * 2], pre[N * 2], to[N * 2];
void ae(int k1, int k2) {
  to[++pp] = k2, nxt[pp] = lnk[k1], pre[lnk[k1]] = pp, lnk[k1] = pp;
}
void del_e(int k1, int k2) {
  if (k2 == lnk[k1]) {
    lnk[k1] = nxt[lnk[k1]];
  } else {
    nxt[pre[k2]] = nxt[k2];
    pre[nxt[k2]] = pre[k2];
  }
}
int rt, f[N], sz[N];
void grt(int k1, int k2) {
  f[k1] = 0, sz[k1] = 1;
  for (int i = lnk[k1]; i; i = nxt[i])
    if (to[i] != k2) {
      grt(to[i], k1);
      sz[k1] += sz[to[i]];
      if (f[k1] < sz[to[i]]) f[k1] = sz[to[i]];
    }
  if (f[k1] < n - sz[k1]) f[k1] = n - sz[k1];
  if (f[k1] < f[rt]) rt = k1;
}
int dep[N], tofa[N], bel[N], ban[N];
struct cmp {
  bool operator()(const int& k1, const int& k2) const {
    return dep[k1] ^ dep[k2] ? dep[k1] < dep[k2] : k1 < k2;
  }
};
set<int, cmp> S[N];
set<pair<int, int> > T;
void dfs1(int k1, int k2) {
  sz[k1] = 1;
  for (int i = lnk[k1]; i; i = nxt[i])
    if (to[i] != k2) {
      dep[to[i]] = dep[k1] + 1;
      dfs1(to[i], k1), sz[k1] += sz[to[i]];
    }
}
void dfs2(int k1, int k2, int k3) {
  for (int i = lnk[k1]; i; i = nxt[i])
    if (to[i] != k2) {
      tofa[to[i]] = i;
      dfs2(to[i], k1, k3 == -1 ? to[i] : k3);
    } else
      del_e(k1, i);
  if (k3 != -1) {
    bel[k1] = k3;
    if (lnk[k1]) S[bel[k1]].insert(k1);
  }
}
void del_v(int k1) {
  int k2 = to[tofa[k1] ^ 1];
  ban[k1] = 1;
  if (k1 != rt) {
    del_e(k2, tofa[k1]);
    S[bel[k1]].erase(k1);
    if (!lnk[k2]) {
      S[bel[k2]].erase(k2);
    }
  }
}
vector<int> vv;
void dfs3(int k1, int k2) {
  if (!ban[k1]) vv.push_back(k1);
  for (int i = lnk[k1]; i; i = nxt[i])
    if (to[i] != k2) dfs3(to[i], k1);
}
int main() {
  scanf("%d%lld", &n, &K);
  for (int i = (2); i <= (n); ++i) {
    int k1, k2;
    scanf("%d%d", &k1, &k2);
    ae(k1, k2), ae(k2, k1);
  }
  memcpy(_lnk, lnk, sizeof(lnk));
  memcpy(_nxt, nxt, sizeof(nxt));
  rt = 0, f[0] = INF;
  grt(1, 0);
  dfs1(rt, 0);
  long long mn = 0, mx = 0;
  for (int i = (1); i <= (n); ++i) {
    mx += dep[i];
    mn += sz[i] & 1;
  }
  if (K < mn || K > mx || (K & 1) != (mn & 1)) {
    puts("NO");
    return 0;
  }
  dfs2(rt, 0, -1);
  for (int i = lnk[rt]; i; i = nxt[i]) {
    T.insert(make_pair(sz[to[i]], to[i]));
  }
  puts("YES");
  long long rest = mx - K;
  while (rest) {
    ((void)0);
    auto big = (--T.end())->second;
    T.erase(--T.end());
    if ((int((S[big]).size())) == 0) {
      ((void)0);
    }
    int k1 = *--S[big].end();
    if (dep[k1] * 2 < rest) {
      rest -= dep[k1] * 2;
      vector<int> v;
      ((void)0);
      assert(lnk[k1]);
      for (int i = lnk[k1]; i; i = nxt[i])
        if (i != (tofa[k1] ^ 1)) {
          v.push_back(to[i]);
          if ((int((v).size())) > 1) break;
        }
      if ((int((v).size())) < 2) v.push_back(k1);
      assert(!ban[v[0]] && !ban[v[1]]);
      printf("%d %d\n", v[0], v[1]);
      ((void)0);
      del_v(v[0]), del_v(v[1]);
      if ((sz[big] -= 2) > 1) {
        T.insert(make_pair(sz[big], big));
      }
    } else {
      dep[0] = rest / 2;
      k1 = *S[big].lower_bound(0);
      vector<int> v;
      for (int i = lnk[k1]; i; i = nxt[i])
        if (i != (tofa[k1] ^ 1)) {
          v.push_back(to[i]);
          if ((int((v).size())) > 1) break;
        }
      if ((int((v).size())) < 2) v.push_back(k1);
      printf("%d %d\n", v[0], v[1]);
      ban[v[0]] = ban[v[1]] = 1;
      break;
    }
  }
  memcpy(lnk, _lnk, sizeof(lnk));
  memcpy(nxt, _nxt, sizeof(nxt));
  dfs3(rt, 0);
  for (int i = (0); i <= ((int((vv).size())) / 2 - 1); ++i)
    printf("%d %d\n", vv[i], vv[i + (int((vv).size())) / 2]);
  return 0;
}