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;
template <typename T>
bool chkmin(T &x, T y) {
  return x > y ? x = y, 1 : 0;
}
template <typename T>
bool chkmax(T &x, T y) {
  return x < y ? x = y, 1 : 0;
}
long long readint() {
  long long x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
int n, tot, rt;
long long k, mina, maxa;
int v[200005], nxt[200005], h[100005], dep[100005], f[100005], siz[100005],
    son[100005];
bool leaf[100005], vis[100005];
vector<int> vec[100005];
set<pair<int, int> > pt[100005], s;
vector<pair<int, int> > ans;
void addedge(int x, int y) {
  v[++tot] = y;
  nxt[tot] = h[x];
  h[x] = tot;
  v[++tot] = x;
  nxt[tot] = h[y];
  h[y] = tot;
}
void dfs1(int u, int fa) {
  siz[u] = 1;
  int mx = 0;
  for (int p = h[u]; p; p = nxt[p]) {
    if (v[p] == fa) continue;
    dfs1(v[p], u);
    siz[u] += siz[v[p]];
    chkmax(mx, siz[v[p]]);
  }
  if (max(mx, n - siz[u]) <= n / 2) rt = u;
}
void dfs2(int u, int fa, int t) {
  siz[u] = 1;
  for (int p = h[u]; p; p = nxt[p]) {
    if (v[p] == fa) continue;
    f[v[p]] = u, dep[v[p]] = dep[u] + 1;
    dfs2(v[p], u, t < 0 ? v[p] : t);
    siz[u] += siz[v[p]], son[u]++;
    if (leaf[v[p]]) vec[u].push_back(v[p]);
    mina += siz[v[p]] & 1;
    maxa += siz[v[p]];
  }
  if (son[u] == 0) leaf[u] = 1;
  if (t >= 0 && son[u] > 0) pt[t].insert(make_pair(dep[u], u));
}
void dfs3(int u, int fa, int t) {
  for (int p = h[u]; p; p = nxt[p]) {
    if (v[p] == fa) continue;
    dfs3(v[p], u, t < 0 ? v[p] : t);
  }
  if (t >= 0 && !vis[u]) pt[t].insert(make_pair(u, 0));
}
int main() {
  n = readint();
  k = readint();
  for (int i = 1; i < n; i++) addedge(readint(), readint());
  dfs1(1, -1);
  dfs2(rt, -1, -1);
  if (k % 2 != mina % 2 || k < mina || k > maxa) return printf("NO\n"), 0;
  printf("YES\n");
  for (int p = h[rt]; p; p = nxt[p]) s.insert(make_pair(siz[v[p]], v[p]));
  long long rem = (maxa - k) / 2;
  while (rem) {
    auto it = --s.end();
    pair<int, int> tmp = *it;
    s.erase(it);
    if (tmp.first - 2 > 0) s.insert(make_pair(tmp.first - 2, tmp.second));
    auto pl = pt[tmp.second].lower_bound(make_pair(rem, 0));
    if (pl == pt[tmp.second].end()) pl--;
    int u = pl->second;
    rem -= dep[u];
    if (vec[u].size() >= 2) {
      ans.push_back(
          make_pair(vec[u][vec[u].size() - 1], vec[u][vec[u].size() - 2]));
      vis[vec[u][vec[u].size() - 1]] = vis[vec[u][vec[u].size() - 2]] = 1;
      vec[u].pop_back(), vec[u].pop_back();
      son[u] -= 2;
      if (son[u] == 0) {
        pt[tmp.second].erase(make_pair(dep[u], u));
        if (f[u] != rt) vec[f[u]].push_back(u);
      }
    } else if (vec[u].size() == 1) {
      ans.push_back(make_pair(vec[u][0], u));
      vis[vec[u][0]] = vis[u] = 1;
      pt[tmp.second].erase(make_pair(dep[u], u));
      if (f[u] != rt) {
        son[f[u]]--;
        if (son[f[u]] == 0) {
          pt[tmp.second].erase(make_pair(dep[f[u]], f[u]));
          if (f[f[u]] != rt) vec[f[f[u]]].push_back(f[u]);
        }
      }
    } else {
      assert(rem == 0);
      for (int p = h[u]; p; p = nxt[p]) {
        if (!vis[v[p]] && v[p] != f[u]) {
          vis[v[p]] = vis[u] = 1;
          ans.push_back(make_pair(u, v[p]));
          break;
        }
      }
    }
  }
  for (int p = h[rt]; p; p = nxt[p]) pt[v[p]].clear();
  dfs3(rt, -1, -1);
  s.clear();
  for (int p = h[rt]; p; p = nxt[p])
    if (pt[v[p]].size()) s.insert(make_pair(pt[v[p]].size(), v[p]));
  while (1) {
    if (s.size() == 1) {
      assert(pt[s.begin()->second].size() == 1);
      ans.push_back(make_pair(pt[s.begin()->second].begin()->first, rt));
      break;
    }
    auto it1 = --s.end(), it2 = it1;
    it2--;
    ans.push_back(make_pair(pt[it1->second].begin()->first,
                            pt[it2->second].begin()->first));
    pt[it1->second].erase(pt[it1->second].begin());
    pt[it2->second].erase(pt[it2->second].begin());
    if (it1->first > 1) s.insert(make_pair(it1->first - 1, it1->second));
    if (it2->first > 1) s.insert(make_pair(it2->first - 1, it2->second));
    s.erase(it1), s.erase(it2);
  }
  for (auto r : ans) printf("%d %d\n", r.first, r.second);
  return 0;
}