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 std::max;
using std::min;
const int inf = 0x3f3f3f3f, Inf = 0x7fffffff;
const long long INF = 0x3f3f3f3f3f3f3f3f;
__inline__ __attribute__((always_inline)) unsigned int rnd() {
  static unsigned int seed = 416;
  return seed ^= seed >> 5, seed ^= seed << 17, seed ^= seed >> 13;
}
template <typename _Tp>
_Tp gcd(const _Tp &a, const _Tp &b) {
  return (!b) ? a : gcd(b, a % b);
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) _Tp abs(const _Tp &a) {
  return a >= 0 ? a : -a;
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) void chmax(_Tp &a, const _Tp &b) {
  (a < b) && (a = b);
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) void chmin(_Tp &a, const _Tp &b) {
  (b < a) && (a = b);
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) void read(_Tp &x) {
  char ch(getchar());
  bool f(false);
  while (!isdigit(ch)) f |= ch == 45, ch = getchar();
  x = ch & 15, ch = getchar();
  while (isdigit(ch)) x = (((x << 2) + x) << 1) + (ch & 15), ch = getchar();
  f && (x = -x);
}
template <typename _Tp, typename... Args>
__inline__ __attribute__((always_inline)) void read(_Tp &t, Args &...args) {
  read(t);
  read(args...);
}
template <typename _Tp, typename... Args>
__inline__ __attribute__((always_inline)) _Tp min(const _Tp &a, const _Tp &b,
                                                  const Args &...args) {
  return a < b ? min(a, args...) : min(b, args...);
}
template <typename _Tp, typename... Args>
__inline__ __attribute__((always_inline)) _Tp max(const _Tp &a, const _Tp &b,
                                                  const Args &...args) {
  return a < b ? max(b, args...) : max(a, args...);
}
__inline__ __attribute__((always_inline)) int read_str(char *s) {
  char ch(getchar());
  while (ch == ' ' || ch == '\r' || ch == '\n') ch = getchar();
  char *tar = s;
  *tar = ch, ch = getchar();
  while (ch != ' ' && ch != '\r' && ch != '\n' && ch != EOF)
    *(++tar) = ch, ch = getchar();
  return tar - s + 1;
}
const int N = 100005;
std::set<int> e[N];
int siz[N], n;
int maxx, rt;
void getrt(int x, int fa) {
  siz[x] = 1;
  int tmp = 0;
  for (auto v : e[x]) {
    if (v == fa) continue;
    getrt(v, x);
    siz[x] += siz[v];
    chmax(tmp, siz[v]);
  }
  chmax(tmp, n - siz[x]);
  if (tmp < maxx) maxx = tmp, rt = x;
}
int dep[N];
long long sum;
void dfs1(int x, int fa) {
  sum += dep[x], siz[x] = 1;
  for (auto v : e[x]) {
    if (v == fa) continue;
    dep[v] = dep[x] + 1;
    dfs1(v, x);
    siz[x] += siz[v];
  }
}
int bel[N], id, Fa[N];
void dfs2(int x, int fa) {
  bel[x] = id, siz[x] = 1, Fa[x] = fa;
  for (auto v : e[x]) {
    if (v == fa) continue;
    dfs2(v, x);
    siz[x] += siz[v];
  }
  if (fa) e[x].erase(e[x].find(fa));
}
struct node {
  int id, val;
  __inline__ __attribute__((always_inline)) bool operator<(
      const node &o) const {
    return val < o.val;
  }
};
std::priority_queue<node> q1, q2[N];
int dg[N], ddg[N];
int head[N];
bool used[N];
int tar;
int resA, resB;
void dfs3(int x, int dep) {
  ++dep;
  if (!used[x] && !resA) {
    if (dep == tar && !e[x].empty()) {
      resA = x;
      resB = *e[x].begin();
    }
  }
  for (auto v : e[x]) dfs3(v, dep);
}
std::priority_queue<node> q;
std::vector<int> sons[N];
int main() {
  long long k;
  read(n, k);
  int x, y;
  for (int i = 1; i < n; ++i) {
    read(x, y);
    e[x].insert(y);
    e[y].insert(x);
  }
  maxx = inf;
  getrt(1, 0);
  dfs1(rt, 0);
  for (auto it : e[rt]) {
    ++id;
    head[id] = it;
    dfs2(it, rt);
    q1.push((node){id, siz[it]});
  }
  for (int i = 1; i <= n; ++i)
    if (i != rt) dg[i] = ((int)e[i].size());
  for (int i = 1; i <= n; ++i) {
    if (i == rt) continue;
    for (auto v : e[i]) ddg[i] += dg[v];
    if (!ddg[i] && dg[i]) q2[bel[i]].push((node){i, dep[i]});
  }
  if (k > sum) return puts("NO"), 0;
  std::vector<std::pair<int, int> > ans;
  auto upd = [&](int x) { --dg[Fa[x]], --ddg[Fa[Fa[x]]]; };
  auto check = [&](int x) {
    if (!ddg[x] && dg[x]) q2[bel[x]].push((node){x, dep[x]});
  };
  if ((sum & 1) != (k & 1)) return puts("NO"), 0;
  int goal = 0;
  while (sum > k) {
    if (q1.empty()) return puts("NO"), 0;
    node x = q1.top();
    q1.pop();
    if (x.val < 2) return puts("NO"), 0;
    x.val -= 2;
    if (x.val) q1.push(x);
    int o = x.id;
    node y = q2[o].top();
    q2[o].pop();
    int nd = y.id;
    if (sum - y.val * 2 < k) {
      goal = o;
      break;
    }
    sum -= y.val * 2;
    if (((int)e[nd].size()) >= 2) {
      int A = *e[nd].begin();
      e[nd].erase(e[nd].begin());
      int B = *e[nd].begin();
      e[nd].erase(e[nd].begin());
      ans.push_back(std::make_pair(A, B));
      upd(A), upd(B);
      check(nd), check(Fa[nd]);
    } else if (((int)e[nd].size()) == 1) {
      int A = *e[nd].begin();
      e[nd].erase(e[nd].begin());
      e[Fa[nd]].erase(nd);
      ans.push_back(std::make_pair(A, nd));
      upd(A), upd(nd);
      check(Fa[nd]), check(Fa[Fa[nd]]);
    } else {
      printf("Wrong answer\n");
      return 0;
    }
  }
  for (auto it : ans) used[it.first] = used[it.second] = true;
  tar = (sum - k) >> 1;
  if (tar) {
    dfs3(head[goal], 0);
    used[resA] = used[resB] = true;
    ans.push_back(std::make_pair(resA, resB));
  }
  int cnt = 0;
  for (int i = 1; i <= n; ++i)
    if (!used[i] && i != rt) sons[bel[i]].push_back(i), ++cnt;
  ++cnt;
  for (int i = 1; i <= id; ++i)
    if (((int)sons[i].size()))
      q.push((node){i, ((int)sons[i].size())}),
          assert(((int)sons[i].size()) * 2 <= cnt);
  sons[0].push_back(rt);
  q.push((node){0, 1});
  while (!q.empty()) {
    node x = q.top();
    q.pop();
    if (q.empty()) {
      puts("A");
      return 0;
    }
    node y = q.top();
    q.pop();
    --x.val, --y.val;
    ans.push_back(std::make_pair(sons[x.id].back(), sons[y.id].back()));
    sons[x.id].pop_back();
    sons[y.id].pop_back();
    if (x.val) q.push(x);
    if (y.val) q.push(y);
  }
  printf("YES\n");
  for (auto it : ans) printf("%d %d\n", it.first, it.second);
  return 0;
}