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 = 100005;
int n, w[N], size[N], id[N];
long long k;
vector<int> vec[N], e[N];
priority_queue<pair<int, int> > que;
void pre(int x, int fa) {
  size[x] = 1;
  for (int to : e[x])
    if (to != fa) pre(to, x), size[x] += size[to];
  w[x] = min(size[x], n - size[x]);
}
void binary() {
  int l = 0, r = n;
  while (l <= r) {
    int mid = (l + r) / 2;
    long long s = 0;
    for (int i = 1; i <= n; i++)
      s += w[i] >= mid ? mid + ((w[i] - mid) & 1) : w[i];
    if (s >= k)
      r = mid - 1;
    else
      l = mid + 1;
  }
  r++;
  long long s = 0;
  for (int i = 1; i <= n; i++) {
    if (w[i] >= r) w[i] = r + ((w[i] - r) & 1);
    s += w[i];
  }
  for (int i = 1; i <= n; i++)
    if (s > k && w[i] == r + 1) w[i] -= 2, s -= 2;
}
void solve(int x, int fa) {
  id[x] = x;
  vec[x].push_back(x);
  int s = 1;
  for (int to : e[x])
    if (to != fa) {
      solve(to, x);
      s += vec[id[to]].size();
    }
  while (!que.empty()) que.pop();
  que.push(make_pair(1, x));
  for (int to : e[x])
    if (to != fa && vec[id[to]].size())
      que.push(make_pair(vec[id[to]].size(), id[to]));
  while (s > w[x]) {
    pair<int, int> u = que.top();
    que.pop();
    pair<int, int> v = que.top();
    que.pop();
    printf("%d %d\n", vec[u.second].back(), vec[v.second].back());
    vec[u.second].pop_back();
    vec[v.second].pop_back();
    u.first--;
    v.first--;
    if (u.first) que.push(u);
    if (v.first) que.push(v);
    s -= 2;
  }
  for (int to : e[x])
    if (to != fa && vec[id[to]].size()) {
      if (vec[id[to]].size() > vec[id[x]].size()) swap(id[x], id[to]);
      for (int p : vec[id[to]]) vec[id[x]].push_back(p);
      vec[id[to]].clear();
    }
}
int main() {
  scanf("%d%lld", &n, &k);
  for (int i = 1; i < n; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    e[x].push_back(y);
    e[y].push_back(x);
  }
  pre(1, 0);
  long long L = 0, R = 0;
  for (int i = 1; i <= n; i++) L += w[i] & 1, R += w[i];
  if (k % 2 != R % 2 || k < L || k > R) {
    puts("NO");
    return 0;
  }
  binary();
  puts("YES");
  solve(1, 0);
  return 0;
}