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>
const int maxn = 100010;
int n;
long long k;
struct Edge {
  int to;
  Edge* next;
} E[maxn * 2], *ne = E, *fir[maxn];
void link(int u, int v) {
  *ne = (Edge){v, fir[u]};
  fir[u] = ne++;
}
namespace Core {
int Q[maxn], fa[maxn], siz[maxn];
int get_core() {
  int *h = Q, *t = Q;
  siz[*t++ = 1] = 1;
  for (; h < t; h++)
    for (Edge* e = fir[*h]; e; e = e->next)
      if (e->to != fa[*h]) fa[*t++ = e->to] = *h, siz[e->to] = 1;
  for (h = t; --h > Q;) siz[fa[*h]] += siz[*h];
  for (h = t; h-- > Q;) {
    bool fl = n - siz[*h] <= n / 2;
    for (Edge* e = fir[*h]; e; e = e->next)
      if (e->to != fa[*h] && siz[e->to] > n / 2) fl = 0;
    if (fl) return *h;
  }
}
}  // namespace Core
int g, rest_cnt, fa[maxn], dep[maxn], siz[maxn];
long long rest_sum;
long long init(int i) {
  long long s = 0;
  siz[i] = 1;
  for (Edge* e = fir[i]; e; e = e->next)
    if (e->to != fa[i]) {
      fa[e->to] = i;
      dep[e->to] = dep[i] + 1;
      s += init(e->to);
      siz[i] += siz[e->to];
    }
  return s + dep[i];
}
int p[maxn];
struct Tuple {
  int u, v, w;
  void make() {
    p[u] = v;
    p[v] = u;
    rest_cnt--;
    rest_sum -= dep[w];
  }
};
void make_jump(int i) {
  int j = i;
  while (dep[j] > rest_sum) j = fa[j];
  ((Tuple){i, j, j}).make();
}
namespace Subtree_Matching {
bool del[maxn];
std::vector<int> ch[maxn], sub[maxn];
void init_sub(int i, int c) {
  if (!del[i]) sub[c].push_back(i);
  for (Edge* e = fir[i]; e; e = e->next)
    if (e->to != fa[i]) init_sub(e->to, c ? c : e->to);
}
void work() {
  for (int i = 1; i <= n; i++) del[i] = p[i] > 0;
  init_sub(g, 0);
  for (Edge* e = fir[g]; e; e = e->next) ch[sub[e->to].size()].push_back(e->to);
  for (int s = n, y = 0, t = 1; rest_cnt; s--) {
    for (int i = 0; i < ch[s].size() && rest_cnt; i++) {
      int x = ch[s][i];
      if (!t) {
        for (t = 1; !ch[t].size(); t++)
          ;
        y = ch[t][ch[t].size() - 1];
        ch[t].pop_back();
      }
      ((Tuple){sub[x][s - 1], sub[y][t - 1], g}).make();
      sub[x].pop_back();
      sub[y].pop_back();
      --t;
      ch[s - 1].push_back(x);
    }
  }
}
}  // namespace Subtree_Matching
std::vector<Tuple> sub[maxn];
int fir_sub[maxn];
int get_sub(int i, int c) {
  std::vector<int> vec;
  vec.push_back(i);
  for (Edge* e = fir[i]; e; e = e->next)
    if (e->to != fa[i]) {
      int j = get_sub(e->to, c ? c : e->to);
      if (j != -1) vec.push_back(j);
    }
  int j = 0;
  for (; j + 1 < vec.size(); j += 2)
    sub[c].push_back((Tuple){vec[j], vec[j + 1], i});
  return j < vec.size() ? vec[j] : -1;
}
std::vector<int> ch_list[maxn];
void match_sub() {
  for (Edge* e = fir[g]; e; e = e->next) ch_list[siz[e->to]].push_back(e->to);
  for (int s = n; s; s--) {
    for (int i = 0; i < ch_list[s].size() && rest_sum; i++) {
      int c = ch_list[s][i];
      Tuple tp = sub[c][fir_sub[c]++];
      if (dep[tp.w] <= rest_sum)
        tp.make();
      else
        make_jump(tp.u);
      ch_list[s - 2].push_back(c);
    }
  }
}
bool used[maxn];
int main() {
  scanf("%d%lld", &n, &k);
  for (int i = 1, u, v; i < n; i++)
    scanf("%d%d", &u, &v), link(u, v), link(v, u);
  g = Core::get_core();
  rest_cnt = n / 2;
  rest_sum = init(g) - k;
  if (rest_sum < 0 || rest_sum % 2 == 1) return puts("NO"), 0;
  rest_sum /= 2;
  get_sub(g, 0);
  match_sub();
  if (rest_sum) return puts("NO"), 0;
  Subtree_Matching::work();
  puts("YES");
  for (int i = 1; i <= n; i++)
    if (!used[i]) used[i] = used[p[i]] = 1, printf("%d %d\n", i, p[i]);
}