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 = 1e5 + 5;
struct Edge {
  int to, nxt;
} e[MAXN << 1];
int head[MAXN], bk[MAXN], cnt;
inline void add(int u, int v) {
  e[++cnt] = (Edge){v, head[u]};
  head[u] = cnt;
  e[++cnt] = (Edge){u, head[v]};
  head[v] = cnt;
}
int n;
long long k;
int sz[MAXN], mx[MAXN], rt;
inline void dfs1(int v, int fa = 0) {
  sz[v] = 1;
  for (int i = head[v]; i; i = e[i].nxt) {
    if (e[i].to == fa) continue;
    dfs1(e[i].to, v);
    sz[v] += sz[e[i].to];
    mx[v] = std::max(mx[v], sz[e[i].to]);
  }
  mx[v] = std::max(mx[v], n - sz[v]);
  if (mx[rt] > mx[v]) rt = v;
}
long long ansl, ansr;
int tp[MAXN], dep[MAXN], deg[MAXN], fa[MAXN];
std::set<std::pair<int, int> > S[MAXN];
inline void dfs2(int v, int fa, int rr) {
  sz[v] = 1;
  tp[v] = rr;
  dep[v] = dep[fa] + 1;
  ::fa[v] = fa;
  for (int i = head[v]; i; i = e[i].nxt) {
    if (e[i].to == fa) continue;
    deg[v]++;
    dfs2(e[i].to, v, rr);
    sz[v] += sz[e[i].to];
  }
  if (deg[v]) S[rr].insert(std::make_pair(dep[v], v));
  ansl += (sz[v] & 1);
  ansr += sz[v];
}
bool vis[MAXN];
std::set<std::pair<int, int> > q;
inline void del(int v) {
  if (!--deg[fa[v]]) {
    S[tp[fa[v]]].erase(std::make_pair(dep[fa[v]], fa[v]));
  }
}
std::vector<int> rem;
inline void dfs3(int v, int fa = 0) {
  if (!vis[v]) rem.push_back(v);
  for (int i = head[v]; i; i = e[i].nxt) {
    if (e[i].to == fa) continue;
    dfs3(e[i].to, v);
  }
}
int main() {
  scanf("%d%lld", &n, &k);
  for (int i = 2; i <= n; ++i) {
    int u, v;
    scanf("%d%d", &u, &v);
    add(u, v);
  }
  memcpy(bk, head, sizeof(bk));
  mx[0] = n;
  dfs1(1);
  sz[rt] = n;
  for (int i = head[rt]; i; i = e[i].nxt) {
    dfs2(e[i].to, rt, e[i].to);
    if (sz[e[i].to] > 1) {
      q.insert(std::make_pair(sz[e[i].to], e[i].to));
    }
  }
  deg[rt] = 114514;
  if (k < ansl || k > ansr || (ansr - k) & 1) {
    puts("NO");
    return 0;
  }
  puts("YES");
  long long d = ansr - k;
  while (d) {
    int r = q.rbegin()->second;
    q.erase(--q.end());
    int v, gx;
    std::tie(gx, v) = *S[r].rbegin();
    if (d < 2 * gx) {
      d >>= 1;
      v = S[r].lower_bound(std::make_pair(d, 0))->second;
      std::vector<int> t;
      for (int &i = head[v]; i && t.size() < 2; i = e[i].nxt)
        if (e[i].to != fa[v] && !vis[e[i].to]) t.push_back(e[i].to);
      if (t.size() < 2) t.push_back(v);
      vis[t[0]] = vis[t[1]] = 1;
      printf("%d %d\n", t[0], t[1]);
      break;
    } else {
      d -= 2 * gx;
      std::vector<int> t;
      for (int &i = head[v]; i && t.size() < 2; i = e[i].nxt)
        if (e[i].to != fa[v] && !vis[e[i].to]) t.push_back(e[i].to);
      if (t.size() < 2) t.push_back(v);
      printf("%d %d\n", t[0], t[1]);
      vis[t[0]] = vis[t[1]] = 1;
      del(t[0]);
      del(t[1]);
    }
    sz[r] -= 2;
    if (sz[r]) q.insert(std::make_pair(sz[r], r));
  }
  memcpy(head, bk, sizeof(head));
  dfs3(rt);
  int t = rem.size() / 2;
  for (int i = 0; i <= t - 1; ++i) printf("%d %d\n", rem[i], rem[i + t]);
  return 0;
}