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;
int n;
long long k;
vector<int> e[100010];
long long lower_limit = 0, upper_limit = 0;
int c[100010], t[100010], mson[100010], rt = 0;
void dfs1(int x, int fa) {
  c[x] = 1;
  mson[x] = 0;
  for (int y : e[x])
    if (y != fa) {
      dfs1(y, x);
      c[x] += c[y];
      mson[x] = max(mson[x], c[y]);
      lower_limit += c[y] % 2;
      upper_limit += min(c[y], n - c[y]);
    }
  mson[x] = max(mson[x], n - c[x]);
  if (mson[x] <= mson[rt]) rt = x;
}
void dfs2(int x, int fa) {
  c[x] = 1;
  for (int y : e[x])
    if (y != fa) {
      dfs2(y, x);
      c[x] += c[y];
    }
  t[c[x]]++;
}
vector<int> d[100010], q, ans1, ans2;
void dfs3(int x, int fa) {
  int sz = 1;
  for (int y : e[x])
    if (y != fa) dfs3(y, x), sz += c[y];
  q.clear();
  d[x].push_back(x);
  q.push_back(x);
  for (int y : e[x])
    if (y != fa) q.push_back(y);
  int mat = (sz - c[x]) / 2, st = 0, ed = q.size() - 1;
  ans1.clear();
  ans2.clear();
  for (int i = 1; i <= mat; i++) {
    while (!d[q[st]].size()) st++;
    ans1.push_back(d[q[st]].back());
    d[q[st]].pop_back();
    while (!d[q[ed]].size()) ed--;
    ans2.push_back(d[q[ed]].back());
    d[q[ed]].pop_back();
  }
  for (int i = 0; i < mat; i++) printf("%d %d\n", ans1[i], ans2[mat - i - 1]);
  for (int i = 1; i < q.size(); i++) {
    if (d[x].size() < d[q[i]].size()) swap(d[x], d[q[i]]);
    for (int j : d[q[i]]) d[x].push_back(j);
  }
}
int main() {
  scanf("%d %lld", &n, &k);
  for (int i = 1, x, y; i < n; i++)
    scanf("%d %d", &x, &y), e[x].push_back(y), e[y].push_back(x);
  mson[0] = n + 1;
  dfs1(1, 0);
  if (k < lower_limit || k > upper_limit || k % 2 != upper_limit % 2) {
    printf("NO");
    return 0;
  }
  dfs2(rt, 0);
  int p = n - 1;
  for (; p > 1; p--) {
    if (upper_limit - 2 * t[p] >= k) {
      upper_limit -= 2 * t[p];
      t[p - 2] += t[p];
    } else
      break;
  }
  for (int i = 1; i <= n; i++) c[i] = min(c[i], p - (p + c[i]) % 2);
  c[rt] = 0;
  for (int i = 1; i <= n; i++)
    if (c[i] == p && upper_limit > k) c[i] -= 2, upper_limit -= 2;
  printf("YES\n");
  dfs3(rt, 0);
}