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 + 10;
char buf[1 << 23], *p1 = buf, *p2 = buf;
int fst[N], nxt[N + N], u[N + N], v[N + N], tot;
int siz[N], mx[N], dep[N], top[N], ff[N], ind[N], rt, n;
int vs[N];
long long as1, as2, k;
struct aa {
  bool operator()(const int &a, const int &b) const {
    return dep[a] == dep[b] ? a < b : dep[a] > dep[b];
  }
};
struct bb {
  int x, sz;
  bool operator<(const bb &b) const { return sz == b.sz ? x < b.x : sz > b.sz; }
};
set<bb> s;
set<int, aa> t[N];
unordered_set<int> e[N];
stack<int> tt[N];
void add(int lu, int lv) {
  u[++tot] = lu, v[tot] = lv, nxt[tot] = fst[lu], fst[lu] = tot;
  u[++tot] = lv, v[tot] = lu, nxt[tot] = fst[lv], fst[lv] = tot;
}
long long read() {
  long long res = 0, fl = 0;
  char a =
      (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)
           ? EOF
           : *p1++);
  while (a < '0' || a > '9')
    fl |= a == '-',
        a = (p1 == p2 &&
                     (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)
                 ? EOF
                 : *p1++);
  while (a >= '0' && a <= '9')
    res = res * 10 + a - '0',
    a = (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)
             ? EOF
             : *p1++);
  return fl ? -res : res;
}
void dfs(int x, int fa) {
  siz[x] = 1;
  for (int i = fst[x]; i; i = nxt[i])
    if (v[i] != fa)
      dfs(v[i], x), siz[x] += siz[v[i]], mx[x] = max(mx[x], siz[v[i]]);
  mx[x] = max(mx[x], n - siz[x]), (mx[x] < mx[rt] || !rt) && (rt = x);
}
void dfs2(int x, int fa) {
  siz[x] = 1, ff[x] = fa;
  for (int i = fst[x]; i; i = nxt[i])
    if (v[i] != fa)
      dep[v[i]] = dep[x] + 1, top[v[i]] = top[x], dfs2(v[i], x),
      siz[x] += siz[v[i]], e[x].insert(v[i]), ind[x]++;
  as1 += siz[x] & 1, as2 += siz[x];
  if (siz[x] > 1) t[top[x]].insert(x);
}
void ers(int x) {
  e[ff[x]].erase(x), (!--ind[ff[x]]) && (t[top[x]].erase(ff[x]));
}
int main() {
  int i, j;
  n = read(), k = read();
  if (n & 1) return cout << "NO", 0;
  for (i = 1; i < n; i++) add(read(), read());
  dfs(1, 0), top[rt] = rt;
  for (i = fst[rt]; i; i = nxt[i])
    top[v[i]] = v[i], dep[v[i]] = 1, dfs2(v[i], rt),
    s.insert(bb{v[i], siz[v[i]]});
  if (k < as1 || k > as2 || ((as2 - k) & 1)) return cout << "NO", 0;
  cout << "YES\n";
  long long res = (as2 - k) / 2, lp = n / 2;
  while (res) {
    int la = s.begin()->x, lb = *t[la].begin();
    s.erase(s.begin()), siz[la] -= 2, lp--, s.insert(bb{la, siz[la]});
    if (dep[lb] >= res) {
      dep[0] = res, lb = *t[la].lower_bound(0);
      int lc = *e[lb].begin(), ld = ind[lb] > 1 ? *(++e[lb].begin()) : lb;
      ers(lc), ers(ld), cout << lc << ' ' << ld << '\n', vs[lc] = vs[ld] = 1;
      break;
    } else {
      res -= dep[lb];
      int lc = *e[lb].begin(), ld = ind[lb] > 1 ? *(++e[lb].begin()) : lb;
      ers(lc), ers(ld), cout << lc << ' ' << ld << '\n', vs[lc] = vs[ld] = 1;
    }
  }
  s.insert(bb{rt, 1}), siz[rt] = 1;
  for (i = 1; i <= n; i++)
    if (!vs[i]) tt[top[i]].push(i);
  while (lp--) {
    int la = s.begin()->x, lb;
    s.erase(s.begin()), lb = s.begin()->x, s.erase(s.begin()), siz[la]--,
                        siz[lb]--;
    s.insert(bb{la, siz[la]}), s.insert(bb{lb, siz[lb]}),
        cout << tt[la].top() << ' ' << tt[lb].top() << '\n';
    tt[la].pop(), tt[lb].pop();
  }
  return 0;
}