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 int N = 100005;
long long k;
int n, h[N], cnt, low;
struct edge {
  int v, n;
} e[N << 1];
int mx[N], siz[N], root, f[N], d[N], tot;
set<int> son[N];
struct data {
  int x, cnt;
  bool operator<(const data &t) const {
    return cnt == t.cnt ? x < t.x : cnt > t.cnt;
  }
};
set<data> st, vt[N];
void addedge(int u, int v) {
  e[cnt] = (edge){v, h[u]}, h[u] = cnt++;
  e[cnt] = (edge){u, h[v]}, h[v] = cnt++;
}
void dfs(int x, int fa) {
  siz[x] = 1;
  for (int i = h[x]; i != -1; i = e[i].n)
    if (e[i].v != fa)
      dfs(e[i].v, x), siz[x] += siz[e[i].v], mx[x] = max(mx[x], siz[e[i].v]);
}
void getroot() {
  dfs(1, 0);
  for (int i = 1; i <= n; ++i) {
    mx[i] = max(mx[i], n - siz[i]);
    if (!root || mx[root] > mx[i]) root = i;
  }
}
void dfs(int tp, int x, int fa, int dep) {
  f[x] = fa, d[x] = dep, siz[x] = 1;
  k -= dep, vt[tp].insert((data){x, dep});
  for (int i = h[x]; i != -1; i = e[i].n)
    if (e[i].v != fa)
      dfs(tp, e[i].v, x, dep + 1), siz[x] += siz[e[i].v], son[x].insert(e[i].v);
  low += (siz[x] & 1);
}
void find(int p) {
  for (set<data>::iterator x = vt[p].begin(); x != vt[p].end(); ++x) {
    if (x->cnt == k && !son[x->x].empty()) {
      int u = x->x, v = *son[u].begin();
      vt[p].erase((data){u, d[u]}), vt[p].erase((data){v, d[v]});
      printf("%d %d\n", u, v);
      return;
    }
  }
}
void fin() {
  while ((st.begin()->cnt) > 0) {
    int p1 = st.begin()->x, cnt1 = st.begin()->cnt;
    st.erase(st.begin());
    int p2 = st.begin()->x, cnt2 = st.begin()->cnt;
    st.erase(st.begin());
    st.insert((data){p1, cnt1 - 1});
    st.insert((data){p2, cnt2 - 1});
    int u = vt[p1].begin()->x, v = vt[p2].begin()->x;
    vt[p1].erase(vt[p1].begin());
    vt[p2].erase(vt[p2].begin());
    printf("%d %d\n", u, v);
  }
}
int main() {
  scanf("%d%lld", &n, &k);
  memset(h, -1, sizeof(h));
  for (int i = 1; i <= n - 1; ++i) {
    int u, v;
    scanf("%d%d", &u, &v);
    addedge(u, v);
  }
  getroot();
  long long lowk = k;
  for (int i = h[root]; i != -1; i = e[i].n)
    dfs(++tot, e[i].v, root, 1), st.insert((data){tot, siz[e[i].v]});
  st.insert((data){++tot, 1}), vt[tot].insert((data){root, 0});
  if (k = -k, lowk < low || k < 0 || k & 1) return puts("NO"), 0;
  puts("YES"), k >>= 1;
  while (k) {
    int p = st.begin()->x, cnt = st.begin()->cnt;
    st.erase(st.begin()), st.insert((data){p, cnt - 2});
    int x, u, v;
    x = f[vt[p].begin()->x];
    if (k - d[x] < 0) {
      find(p);
      break;
    }
    k -= d[x];
    if ((int)(son[x].size()) > 1) {
      u = *son[x].begin(), son[x].erase(son[x].begin());
      v = *son[x].begin(), son[x].erase(son[x].begin());
    } else {
      if (f[u = x] != root) son[f[u]].erase(u);
      v = *son[x].begin(), son[x].erase(son[x].begin());
    }
    vt[p].erase((data){u, d[u]}), vt[p].erase((data){v, d[v]});
    printf("%d %d\n", u, v);
  }
  fin();
  return 0;
}