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;
struct edge {
  int t, nxt;
} e[200010];
int n, u, v, rt, rs, be[100010], cnt, vis[100010], sz[100010], ms[100010],
    ne[100010], val[100010], num[100010], id[100010], mn, lm, t1, t2, ns;
long long K, mx;
priority_queue<pair<int, int> > pq;
vector<int> d[100010];
void add(const int& x, const int& y) {
  e[++cnt] = (edge){y, be[x]}, be[x] = cnt;
}
void getrt(const int& x) {
  vis[x] = sz[x] = 1;
  for (int i = be[x]; i; i = e[i].nxt)
    if (!vis[e[i].t])
      getrt(e[i].t), sz[x] += sz[e[i].t], ms[x] = max(ms[x], sz[e[i].t]);
  if (max(n - sz[x], ms[x]) < rs) rs = max(n - sz[x], ms[x]), rt = x;
  vis[x] = 0;
}
void dfs(const int& x) {
  vis[x] = sz[x] = 1;
  for (int i = be[x]; i; i = e[i].nxt)
    if (!vis[e[i].t]) dfs(e[i].t), sz[x] += sz[e[i].t];
  val[x] = min(sz[x], n - sz[x]), x != rt ? ++num[val[x]] : 0,
  mn += (val[x] & 1), mx += val[x];
  vis[x] = 0;
}
void Solve(const int& x) {
  for (int i = be[x]; i; i = e[i].nxt)
    if (sz[e[i].t] < sz[x]) Solve(e[i].t);
  if (!e[be[x]].nxt && x != rt) return (void)(id[x] = x, d[x].push_back(x));
  ns = 0;
  for (int i = be[x]; i; i = e[i].nxt)
    if (sz[e[i].t] < sz[x] && d[id[e[i].t]].size())
      pq.push((pair<int, int>){d[id[e[i].t]].size(), id[e[i].t]}),
          ns += d[id[e[i].t]].size();
  d[x].push_back(x), pq.push((pair<int, int>){1, x}), ++ns;
  while (pq.size() > 1 && ns > val[x]) {
    t1 = pq.top().second, pq.pop(), t2 = pq.top().second, pq.pop();
    printf("%d %d\n", d[t1][d[t1].size() - 1], d[t2][d[t2].size() - 1]),
        d[t1].pop_back(), d[t2].pop_back(), ns -= 2;
    if (d[t1].size()) pq.push((pair<int, int>){d[t1].size(), t1});
    if (d[t2].size()) pq.push((pair<int, int>){d[t2].size(), t2});
  }
  if (pq.empty())
    id[x] = x;
  else {
    id[x] = pq.top().second, pq.pop();
    while (!pq.empty()) {
      t1 = pq.top().second, pq.pop();
      for (int i = 0; i < d[t1].size(); ++i) d[id[x]].push_back(d[t1][i]);
    }
  }
}
int main() {
  scanf("%d%d", &n, &K);
  for (int i = 1; i < n; ++i) scanf("%d%d", &u, &v), add(u, v), add(v, u);
  rs = 1e9, getrt(1), dfs(rt);
  if (K < mn || K > mx || ((mx - K) & 1)) return puts("NO"), 0;
  puts("YES"), lm = (n >> 1);
  for (int i = (n >> 1); i >= 1 && mx - (num[i] << 1) >= K; --i)
    lm = i - 1, num[i - 2] += num[i], mx -= (num[i] << 1);
  for (int i = 1; i <= n; ++i)
    if (i != rt)
      val[i] = min(val[i], lm - (abs(val[i] - lm) & 1)),
      val[i] == lm&& mx > K ? mx -= 2, val[i] -= 2 : 0;
  val[rt] = 0, Solve(rt);
  return 0;
}