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;
vector<int> L[100100];
int sub[100100];
int h[100100];
int anc[100100];
int sz[100100];
int foi[100100];
int pre[100100];
int cnt = 0;
void dfs(int x, int p = 0) {
  sub[x] = 1;
  for (int i : L[x])
    if (i != p) {
      dfs(i, x);
      sub[x] += sub[i];
    }
}
vector<pair<int, int> > match[100100];
int W;
int dfs1(int x, int p, int br) {
  sz[br]++;
  pre[x] = cnt++;
  if (p + 1) h[x] = 1 + h[p];
  anc[x] = p;
  vector<int> v;
  for (int i : L[x])
    if (i != p) {
      int u = dfs1(i, x, (p == -1) ? i : br);
      if (u + 1) v.push_back(u), W++;
    }
  v.push_back(x);
  for (int i = 0; i + 1 < v.size(); i += 2) {
    match[br].push_back({v[i], v[i + 1]});
    ;
  }
  if (v.size() % 2 == 1)
    return v[v.size() - 1];
  else
    return -1;
}
int lca(int a, int b) {
  if (h[a] < h[b]) return a;
  if (h[a] > h[b]) return b;
  return anc[a];
}
int main() {
  int n;
  long long k;
  scanf("%d%lld", &n, &k);
  for (int i = 0; i < n - 1; i++) {
    int a, b;
    scanf("%d%d", &a, &b), a--, b--;
    L[a].push_back(b);
    L[b].push_back(a);
  }
  dfs(0);
  int ts = 0, p = 0;
  while (1) {
    ;
    if (ts > 0 && L[ts].size() == 1) break;
    int mx = -1;
    for (int i : L[ts])
      if (i != p) {
        if (mx == -1 || sub[i] > sub[mx]) mx = i;
      }
    if (2 * sub[mx] >= n) {
      p = ts;
      ts = mx;
    } else
      break;
  }
  dfs1(ts, -1, ts);
  long long cur = 0;
  for (int i = 0; i < n; i++) cur += h[i];
  set<pair<int, int> > S;
  for (int i : L[ts]) {
    S.insert({sz[i], i});
    ;
  }
  for (int i = 0; i < n; i++)
    sort(match[i].begin(), match[i].end(),
         [](pair<int, int> x, pair<int, int> y) {
           return min(h[x.first], h[x.second]) < min(h[y.first], h[y.second]);
         });
  if (k > cur || k < W || k % 2 != cur % 2) {
    printf("NO\n");
    return 0;
  }
  vector<pair<int, int> > ans;
  while (cur > k) {
    ;
    pair<int, int> u = *--S.end();
    S.erase(u);
    int br = u.second;
    pair<int, int> p = match[br][match[br].size() - 1];
    ;
    match[br].pop_back();
    int dec = 2 * h[lca(p.first, p.second)];
    ;
    if (cur - dec >= k) {
      cur -= dec;
      ans.push_back(p);
      foi[p.first] = foi[p.second] = 1;
      sz[br] -= 2;
      S.insert({sz[br], br});
      continue;
    }
    int x = p.first;
    if (h[p.first] < h[p.second]) x = p.second;
    int y = x;
    while (cur - 2 * h[y] < k) y = anc[y];
    ;
    ans.push_back({x, y});
    foi[x] = foi[y] = 1;
    cur = k;
  }
  vector<int> outros;
  for (int i = 0; i < n; i++)
    if (!foi[i]) outros.push_back(i);
  sort(outros.begin(), outros.end(),
       [](int i, int j) { return pre[i] < pre[j]; });
  for (int i = 0; i < outros.size() / 2; i++)
    ans.push_back({outros[i], outros[i + outros.size() / 2]});
  printf("YES\n");
  for (pair<int, int> i : ans) printf("%d %d\n", i.first + 1, i.second + 1);
}