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;
char buf[1048576], *p0, *p1;
inline int read() {
  int r = 0;
  char c =
      (p0 == p1 && (p1 = (p0 = buf) + fread(buf, 1, 1048576, stdin), p0 == p1)
           ? EOF
           : *p0++);
  while (c < 48 || c > 57)
    c = (p0 == p1 && (p1 = (p0 = buf) + fread(buf, 1, 1048576, stdin), p0 == p1)
             ? EOF
             : *p0++);
  while (c > 47 && c < 58) {
    r = (r << 3) + (r << 1) + (c ^ 48);
    c = (p0 == p1 && (p1 = (p0 = buf) + fread(buf, 1, 1048576, stdin), p0 == p1)
             ? EOF
             : *p0++);
  }
  return r;
}
inline long long rlong() {
  long long r = 0;
  char c =
      (p0 == p1 && (p1 = (p0 = buf) + fread(buf, 1, 1048576, stdin), p0 == p1)
           ? EOF
           : *p0++);
  while (c < 48 || c > 57)
    c = (p0 == p1 && (p1 = (p0 = buf) + fread(buf, 1, 1048576, stdin), p0 == p1)
             ? EOF
             : *p0++);
  while (c > 47 && c < 58) {
    r = (r << 3) + (r << 1) + (c ^ 48);
    c = (p0 == p1 && (p1 = (p0 = buf) + fread(buf, 1, 1048576, stdin), p0 == p1)
             ? EOF
             : *p0++);
  }
  return r;
}
int n, rot, mxs = 0x3fffffff, siz[100005], fat[100005], dep[100005],
            top[100005], deg[100005];
bool vis[100005];
set<pair<int, int> > rst, lst[100005];
vector<int> tmp, edg[100005];
void sdfa(int u) {
  int mss = 0;
  siz[u] = 1;
  for (auto i : edg[u])
    if (!siz[i]) {
      sdfa(i);
      siz[u] += siz[i];
      mss = max(mss, siz[i]);
    }
  if (mxs > max(mss, n - siz[u])) mxs = max(mss, n - siz[rot = u]);
}
void sqfa(int u, int v) {
  siz[u] = 1;
  deg[u] = edg[u].size() - 1;
  if ((top[u] = v) && deg[u]) lst[v].insert(make_pair(dep[u], u));
  for (auto i : edg[u])
    if (i != fat[u]) {
      dep[i] = dep[fat[i] = u] + 1;
      sqfa(i, u == rot ? i : v);
      siz[u] += siz[i];
    }
}
void sbfa(int u) {
  if (!vis[u]) tmp.emplace_back(u);
  for (auto i : edg[u])
    if (i != fat[u]) sbfa(i);
}
inline void remove(int u) {
  vis[u] = true;
  if (!(--deg[fat[u]])) lst[top[u]].erase(make_pair(dep[fat[u]], fat[u]));
}
int main() {
  int u, v;
  long long m, w = 0;
  n = read();
  m = rlong();
  for (int i = 1; i < n; ++i) {
    u = read();
    v = read();
    edg[u].emplace_back(v);
    edg[v].emplace_back(u);
  }
  sdfa(1);
  sqfa(rot, u = 0);
  for (int i = 1; i <= n; ++i)
    if (i != rot) {
      u += siz[i] & 1;
      w += siz[i];
    }
  if (m < u || m > w || ((w - m) & 1)) {
    puts("NO");
    return 0;
  }
  puts("YES");
  w -= m;
  for (auto i : edg[rot])
    if (siz[i] > 1) rst.emplace(siz[i], i);
  while (w) {
    u = rst.rbegin()->second;
    rst.erase(--rst.end());
    v = lst[u].rbegin()->second;
    if ((dep[v] << 1) > w) {
      v = lst[u].lower_bound(make_pair((int)(w >>= 1), 0))->second;
      tmp.clear();
      for (auto i : edg[v])
        if (i != fat[v] && (!vis[i])) tmp.emplace_back(i);
      if (tmp.size() < 2) tmp.emplace_back(v);
      printf("%d %d\n", tmp.at(0), tmp.at(1));
      vis[tmp.at(0)] = vis[tmp.at(1)] = true;
      w -= dep[v];
      break;
    } else {
      tmp.clear();
      for (auto i : edg[v])
        if (i != fat[v] && (!vis[i])) tmp.emplace_back(i);
      if (tmp.size() < 2) tmp.emplace_back(v);
      printf("%d %d\n", tmp.at(0), tmp.at(1));
      remove(tmp.at(0));
      remove(tmp.at(1));
      w -= dep[v] << 1;
      if ((siz[u] -= 2) > 1) rst.emplace(siz[u], u);
    }
  }
  tmp.clear();
  sbfa(rot);
  u = tmp.size() >> 1;
  for (int i = 0; i < u; ++i) printf("%d %d\n", tmp.at(i), tmp.at(u + i));
  return 0;
}