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 = 1e6 + 7;
bool ft[N];
set<int> h[N];
int n, m, w, q, vas, p[N], fl[N], fa[N], siz[N], res[N], vac[N], opt[N], dep[N];
long long l, r, k;
vector<int> v[N];
struct node {
  int u, v;
} e[N];
inline bool operator<(node a, node b) { return a.v < b.v; }
priority_queue<node> f[N], g, s;
inline void dfs1(int u) {
  siz[u] = 1;
  int val = 0;
  for (int i = 0; i < v[u].size(); i++) {
    int x = v[u][i];
    if (fa[u] == x) continue;
    fa[x] = u, dfs1(x), siz[u] += siz[x], val = max(val, siz[x]);
  }
  if (siz[u] % 2) l++;
  val = max(val, n - siz[u]);
  if (val <= vas) vas = val, w = u;
}
inline void dfs2(int u) {
  siz[u] = 1;
  for (int i = 0; i < v[u].size(); i++) {
    int x = v[u][i];
    if (fa[u] == x) continue;
    fa[x] = u, dep[x] = dep[u] + 1, dfs2(x), siz[u] += siz[x];
  }
  r += dep[u], f[q].push({u, dep[u] * 2});
}
inline int merge(int u, int t) {
  if (vac[u] < vac[t]) swap(u, t);
  while (vac[t])
    vac[u]++, vac[t]--, h[u].insert(*h[t].begin()), h[t].erase(*h[t].begin());
  return u;
}
inline void dfs3(int u) {
  p[u] = u;
  for (int i = 0; i < v[u].size(); i++) {
    int x = v[u][i];
    if (fa[u] == x) continue;
    dfs3(x), p[u] = merge(p[u], p[x]);
  }
  if (fl[u])
    fl[u]--, m++, e[m].u = u, e[m].v = *h[p[u]].begin(), vac[p[u]]--,
                  h[p[u]].erase(*h[p[u]].begin());
  else
    h[p[u]].insert(u), vac[p[u]]++;
  while (fl[u]) {
    int x = *h[p[u]].begin();
    h[p[u]].erase(x);
    int y = *h[p[u]].begin();
    h[p[u]].erase(y);
    m++, e[m].u = x, e[m].v = y, fl[u]--, vac[p[u]] -= 2;
  }
}
int main() {
  cin >> n >> k;
  int u, t;
  vas = n;
  for (int i = 1; i < n; i++)
    scanf("%d%d", &u, &t), v[u].push_back(t), v[t].push_back(u);
  dfs1(1), memset(fa, 0, sizeof(fa));
  for (int i = 0; i < v[w].size(); i++)
    dep[v[w][i]] = 1, fa[v[w][i]] = w, q = v[w][i], dfs2(v[w][i]),
    g.push({v[w][i], siz[v[w][i]]}), opt[v[w][i]] = siz[v[w][i]];
  if (k < l || r < k || k % 2 != r % 2) {
    cout << "NO" << endl;
    return 0;
  }
  cout << "YES" << endl;
  k = r - k;
  while (k > 0) {
    node c = g.top();
    g.pop();
    while (1) {
      node w = f[c.u].top();
      if (w.v > k || siz[w.u] - res[w.u] <= 1)
        res[fa[w.u]] += res[w.u];
      else if (siz[w.u] - res[w.u] >= 2) {
        k -= w.v, fl[w.u]++, res[w.u] += 2;
        break;
      }
      f[c.u].pop();
    }
    c.v -= 2, g.push(c);
  }
  for (int i = 0; i < v[w].size(); i++)
    dfs3(v[w][i]), s.push({p[v[w][i]], vac[p[v[w][i]]]});
  h[w].insert(w), vac[w] = 1, s.push({w, 1});
  while (m < n / 2) {
    node a = s.top();
    s.pop();
    node b = s.top();
    s.pop();
    a.v--, b.v--;
    int x = *h[a.u].begin(), y = *h[b.u].begin();
    h[a.u].erase(x), h[b.u].erase(y);
    m++, e[m].u = x, e[m].v = y, s.push(a), s.push(b);
  }
  for (int i = 1; i <= m; i++) printf("%d %d\n", e[i].u, e[i].v);
  return 0;
}