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;
inline long long read() {
  long long x = 0, f = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = (x << 3) + (x << 1) + (c ^ 48);
    c = getchar();
  }
  return f == 1 ? x : -x;
}
inline void print(long long x) {
  if (x < 0) putchar('-'), x = ~x + 1;
  if (x >= 10) print(x / 10);
  putchar((x % 10) | 48);
}
long long n, k;
long long siz[100010], maxs[100010], sz[100010];
long long rt;
long long dep[100010], son[100010], fa[100010];
long long top[100010];
vector<long long> vec[100010], ans;
set<pair<long long, long long> > nod[100010], st;
void getrt(long long x, long long f) {
  siz[x] = 1;
  for (long long v : vec[x]) {
    if (v == f) continue;
    getrt(v, x);
    siz[x] += siz[v];
    maxs[x] = max(maxs[x], siz[v]);
  }
  maxs[x] = max(maxs[x], n - siz[x]);
  if (maxs[x] < maxs[rt]) rt = x;
}
long long maxn, minn;
void dfs1(long long x, long long f) {
  siz[x] = 1, dep[x] = dep[f] + 1, fa[x] = f;
  for (long long v : vec[x]) {
    if (v == f) continue;
    dfs1(v, x);
    if (siz[v] > siz[son[x]]) son[x] = v;
    siz[x] += siz[v];
    maxn += siz[v];
    minn += (siz[v] & 1);
    ++sz[x];
  }
}
void dfs2(long long x, long long topf) {
  top[x] = topf;
  if (son[x]) {
    dfs2(son[x], topf);
  } else
    return;
  for (long long v : vec[x]) {
    if (v == son[x] || v == fa[x]) continue;
    dfs2(v, v);
  }
}
void dfs3(long long x, long long f, long long r) {
  if (sz[x]) nod[r].insert(make_pair(dep[x], x));
  for (long long v : vec[x]) {
    if (v == f) continue;
    if (siz[v] == 1) continue;
    dfs3(v, x, r);
  }
}
bool vis[100010];
void getans(long long x, long long f) {
  if (!vis[x]) ans.push_back(x);
  for (long long v : vec[x]) {
    if (v == f) continue;
    getans(v, x);
  }
}
void del(long long x, long long r) {
  if (!--sz[fa[x]]) nod[r].erase(make_pair(dep[fa[x]], fa[x]));
}
signed main() {
  n = read(), k = read();
  for (long long i = 1; i < n; ++i) {
    long long u = read(), v = read();
    vec[u].push_back(v), vec[v].push_back(u);
  }
  maxs[0] = 0x3f3f3f3f;
  getrt(1, 1);
  dep[rt] = -1;
  dfs1(rt, rt);
  dfs2(rt, rt);
  if (k < minn || k > maxn || (k & 1) != (maxn & 1)) {
    printf("NO\n");
    return 0;
  }
  printf("YES\n");
  for (long long v : vec[rt]) {
    dfs3(v, rt, v);
    if (siz[v] > 1) st.insert(make_pair(siz[v], v));
  }
  long long rem = maxn - k;
  while (rem) {
    auto it = st.end();
    --it;
    long long r = (*it).second;
    st.erase(it);
    it = nod[r].end();
    --it;
    long long lca = (*it).second;
    if (2 * dep[lca] > rem) {
      rem >>= 1;
      lca = nod[r].lower_bound(make_pair(rem, 0))->second;
      vector<long long> V;
      V.clear();
      for (long long v : vec[lca]) {
        if (v == fa[lca] || vis[v]) continue;
        V.push_back(v);
      }
      if (V.size() < 2) V.push_back(lca);
      printf("%lld %lld\n", V[0], V[1]);
      vis[V[0]] = vis[V[1]] = 1;
      del(V[0], r);
      del(V[1], r);
      break;
    } else {
      vector<long long> V;
      V.clear();
      for (long long v : vec[lca]) {
        if (v == fa[lca] || vis[v]) continue;
        V.push_back(v);
      }
      if (V.size() < 2) V.push_back(lca);
      printf("%lld %lld\n", V[0], V[1]);
      del(V[0], r);
      del(V[1], r);
      vis[V[0]] = vis[V[1]] = 1;
      rem -= 2 * dep[lca];
    }
    siz[r] -= 2;
    if (siz[r] > 1) st.insert(make_pair(siz[r], r));
  }
  getans(rt, rt);
  long long T = ans.size() >> 1;
  for (long long i = 1; i <= T; ++i)
    printf("%lld %lld\n", ans[i - 1], ans[i + T - 1]);
  return 0;
}