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>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
long long Min = 0, Max = 0;
vector<int> v[100005];
vector<int> v1, v2;
int n;
int Size[100005];
void dfs(int first, int f) {
  Size[first] = 1;
  for (auto it : v[first]) {
    if (it != f) {
      dfs(it, first);
      Size[first] += Size[it];
    }
  }
  if (Size[first] & 1)
    Min++, v1.push_back(first);
  else
    v2.push_back(first);
  Max += min(Size[first], n - Size[first]);
}
int need[100005];
int go[100005];
bool cmp(const int &first, const int &second) {
  return need[first] > need[second];
}
vector<pair<int, int> > ans;
set<int> dfs2(int first, int f) {
  for (auto &it : v[first]) {
    if (it == f) {
      swap(v[first].back(), it);
      break;
    }
  }
  if (v[first].back() == f) v[first].pop_back();
  priority_queue<pair<int, int>, vector<pair<int, int> >,
                 greater<pair<int, int> > >
      pq;
  int tot = 0;
  for (auto it : v[first]) {
    if (need[it]) pq.push(make_pair(need[it], it));
    tot += need[it];
  }
  tot++;
  while (tot > need[first]) {
    if (tot == need[first] + 2 && pq.size() <= 1) break;
    pair<int, int> p = pq.top();
    pq.pop();
    pair<int, int> q = pq.top();
    pq.pop();
    p.first--;
    q.first--;
    go[p.second]++;
    go[q.second]++;
    if (p.first) pq.push(p);
    if (q.first) pq.push(q);
    tot -= 2;
  }
  set<int> s;
  vector<int> v1;
  if (tot == need[first])
    s.insert(first);
  else {
    v1.push_back(first);
    pair<int, int> p = pq.top();
    pq.pop();
    go[p.second]++;
  }
  for (auto it : v[first]) {
    if (it != f) {
      set<int> s2 = dfs2(it, first);
      while (go[it]) {
        v1.push_back(*s2.begin());
        s2.erase(s2.begin());
        go[it]--;
      }
      if (s2.size() > s.size()) swap(s2, s);
      for (auto it : s2) s.insert(it);
    }
  }
  for (int i = 0; i < v1.size() / 2; i++) {
    ans.push_back(make_pair(v1[i], v1[v1.size() / 2 + i]));
  }
  return s;
}
void solve() {
  long long k;
  scanf("%d %lld", &n, &k);
  for (int i = 1; i < n; i++) {
    int first, second;
    scanf("%d %d", &first, &second);
    v[first].push_back(second);
    v[second].push_back(first);
  }
  dfs(1, 0);
  if (k < Min || k > Max || (k % 2) != (Min % 2)) {
    printf("NO\n");
  } else {
    printf("YES\n");
    int Max = n, Min = 1;
    while (Max >= Min) {
      int mid = (Max + Min) / 2;
      if (mid % 2) {
        long long l = 0, r = 0;
        for (auto it : v1) {
          l += min(mid, min(Size[it], n - Size[it]));
        }
        r = l;
        for (auto it : v2) {
          int Max = min(Size[it], n - Size[it]);
          if (Max >= mid + 1) {
            r += mid + 1;
            l += mid - 1;
          } else {
            r += Max;
            l += Max;
          }
        }
        if (k >= l && k <= r) {
          for (auto it : v1) {
            need[it] = min(mid, min(Size[it], n - Size[it]));
          }
          k -= l;
          for (auto it : v2) {
            int Max = min(Size[it], n - Size[it]);
            if (Max >= mid + 1) {
              if (k)
                need[it] = mid + 1, k -= 2;
              else
                need[it] = mid - 1;
            } else {
              need[it] = Max;
            }
          }
          break;
        }
        if (k < l)
          Max = mid;
        else
          Min = mid;
      } else {
        long long l = 0, r = 0;
        for (auto it : v2) {
          l += min(mid, min(Size[it], n - Size[it]));
        }
        r = l;
        for (auto it : v1) {
          int Max = min(Size[it], n - Size[it]);
          if (Max >= mid + 1) {
            r += mid + 1;
            l += mid - 1;
          } else {
            r += Max;
            l += Max;
          }
        }
        if (k >= l && k <= r) {
          for (auto it : v2) {
            need[it] = min(mid, min(Size[it], n - Size[it]));
          }
          k -= l;
          for (auto it : v1) {
            int Max = min(Size[it], n - Size[it]);
            if (Max >= mid + 1) {
              if (k)
                need[it] = mid + 1, k -= 2;
              else
                need[it] = mid - 1;
            } else {
              need[it] = Max;
            }
          }
          break;
        }
        if (k < l)
          Max = mid;
        else
          Min = mid;
      }
    }
    dfs2(1, 0);
    for (auto it : ans) {
      printf("%d %d\n", it.first, it.second);
    }
  }
}
int main() {
  int t = 1;
  while (t--) {
    solve();
  }
}