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;
const long long MAXN = 1e5 + 10;
template <typename T>
void chkmax(T &a, T b) {
  a = max(a, b);
}
template <typename T>
void chkmin(T &a, T b) {
  a = min(a, b);
}
long long head[MAXN], nxt[MAXN << 1], to[MAXN << 1], ind;
inline void add_edge(long long u, long long v) {
  nxt[++ind] = head[u];
  head[u] = ind;
  to[ind] = v;
}
inline void add(long long u, long long v) {
  add_edge(u, v);
  add_edge(v, u);
}
long long n, k, maxk, mink;
long long siz[MAXN], maxs[MAXN], rt;
void dfs(long long u, long long fa) {
  siz[u] = 1;
  for (long long i = head[u]; i; i = nxt[i]) {
    long long v = to[i];
    if (v == fa) continue;
    dfs(v, u);
    siz[u] += siz[v];
    chkmax(maxs[u], siz[v]);
  }
  chkmax(maxs[u], n - siz[u]);
  if (maxs[u] * 2 <= n) rt = u;
}
inline void init(void) {
  scanf("%lld%lld", &n, &k);
  long long u, v;
  for (long long i = 1; i < n; ++i) scanf("%lld%lld", &u, &v), add(u, v);
  dfs(1, 0);
}
set<long long> son[MAXN];
long long fa[MAXN], depth[MAXN];
set<long long> sub[MAXN];
vector<long long> vaild[MAXN];
void dfs2(long long u, long long pa) {
  siz[u] = 1;
  fa[u] = pa;
  for (long long i = head[u]; i; i = nxt[i]) {
    long long v = to[i];
    if (v == pa) continue;
    son[u].insert(v);
    dfs2(v, u);
    siz[u] += siz[v];
    maxk += min(n - siz[v], siz[v]);
    mink += (siz[v] & 1);
  }
}
long long comp1(long long x, long long y) { return depth[x] < depth[y]; }
struct comp2 {
  bool operator()(const long long x, const long long y) const {
    return sub[x].size() < sub[y].size();
  }
};
priority_queue<long long, vector<long long>, comp2> Q;
void dfs3(long long u, long long topn) {
  vaild[topn].push_back(u);
  depth[u] = depth[fa[u]] + 1;
  for (long long i = head[u]; i; i = nxt[i]) {
    long long v = to[i];
    if (v == fa[u]) continue;
    dfs3(v, topn);
  }
}
long long mate[MAXN], vis[MAXN], dfn[MAXN], cnt;
void dfs4(long long u) {
  if (!vis[u]) dfn[++cnt] = u;
  for (long long i = head[u]; i; i = nxt[i]) {
    long long v = to[i];
    if (v == fa[u]) continue;
    dfs4(v);
  }
}
inline void work(void) {
  dfs2(rt, 0);
  if (!(k >= mink && k <= maxk && ((maxk - k) % 2 == 0))) {
    printf("NO\n");
    return;
  }
  for (long long i = head[rt]; i; i = nxt[i]) {
    long long v = to[i];
    dfs3(v, v);
    sub[v] = set<long long>(vaild[v].begin(), vaild[v].end());
    sort(vaild[v].begin(), vaild[v].end(), comp1);
    Q.push(v);
  }
  long long nowk = maxk;
  while (nowk != k) {
    long long tmp = Q.top();
    Q.pop();
    while (!vaild[tmp].empty()) {
      long long x = vaild[tmp].back();
      if (son[x].empty())
        vaild[tmp].pop_back();
      else
        break;
    }
    long long x = vaild[tmp].back();
    if (k + depth[x] * 2 < maxk) {
      maxk -= depth[x] * 2;
      if (son[x].size() >= 2) {
        long long u = *son[x].begin();
        son[x].erase(u);
        long long v = *son[x].begin();
        son[x].erase(v);
        mate[u] = v;
        mate[v] = u;
        vis[u] = vis[v] = 1;
        sub[tmp].erase(u);
        sub[tmp].erase(v);
      } else {
        long long v = *son[x].begin();
        son[x].erase(v);
        son[fa[x]].erase(x);
        mate[v] = x;
        mate[x] = v;
        vis[v] = vis[x] = 1;
        vaild[tmp].pop_back();
        sub[tmp].erase(v);
        sub[tmp].erase(x);
      }
      Q.push(tmp);
    } else {
      for (auto x : vaild[tmp]) {
        if (maxk - 2 * depth[x] == k && !son[x].empty()) {
          maxk -= 2 * depth[x];
          long long u = *son[x].begin();
          son[x].erase(u);
          mate[x] = u;
          mate[u] = x;
          vis[u] = vis[x] = 1;
          break;
        }
      }
      break;
    }
  }
  assert(maxk == k);
  dfs4(rt);
  for (long long i = 1; i <= cnt / 2; ++i) {
    mate[dfn[i]] = dfn[i + cnt / 2];
    mate[dfn[i + cnt / 2]] = dfn[i];
  }
  printf("YES\n");
  for (long long i = 1; i <= n; ++i)
    if (i < mate[i]) printf("%lld %lld\n", i, mate[i]);
}
signed main() {
  init();
  work();
  return 0;
}