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, c;
vector<vector<int>> g;
int dfs(int x, int p) {
  bool ok = true;
  int s = 1;
  for (int y : g[x]) {
    if (y == p) continue;
    int ss = dfs(y, x);
    if (ss * 2 > n) ok = false;
    s += ss;
  }
  if (s * 2 < n) ok = false;
  if (ok) c = x;
  return s;
}
vector<long long int> d;
int dfs2(int x, int p) {
  int s = 1;
  for (int y : g[x]) {
    if (y == p) continue;
    int ss = dfs2(y, x);
    s += ss;
  }
  if (x != c) d[x] = s;
  return s;
}
vector<vector<int>> r;
vector<pair<int, int>> res;
void dfs3(int x, int p) {
  r[x].push_back(x);
  int s = 1;
  set<pair<int, int>> q;
  q.insert({-1, x});
  for (int y : g[x]) {
    if (y == p) continue;
    dfs3(y, x);
    q.insert({-r[y].size(), y});
    s += r[y].size();
  }
  while (s > d[x]) {
    s -= 2;
    auto p1 = *q.begin();
    q.erase(p1);
    auto p2 = *q.begin();
    q.erase(p2);
    assert(p1.first < 0 && p2.first < 0);
    p1.first++;
    p2.first++;
    q.insert(p1);
    q.insert(p2);
    int xx = r[p1.second].back();
    int yy = r[p2.second].back();
    res.push_back({xx, yy});
    r[p1.second].pop_back();
    r[p2.second].pop_back();
  }
  for (auto p : q) {
    int xx = p.second;
    if (xx != x) {
      if (r[xx].size() > r[x].size()) {
        r[x].swap(r[xx]);
      }
      for (int t : r[xx]) {
        r[x].push_back(t);
      }
    }
  }
  assert(r[x].size() == d[x]);
}
int main() {
  ios::sync_with_stdio(false);
  long long int k;
  cin >> n >> k;
  g.resize(n);
  for (int i = 0; i < n - 1; i++) {
    int x, y;
    cin >> x >> y;
    x--;
    y--;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  dfs(0, -1);
  d.resize(n);
  dfs2(c, -1);
  long long int smax = 0;
  for (auto x : d) smax += x;
  long long int smin = 0;
  for (auto x : d) smin += x % 2;
  cerr << smin << " " << smax << "\n";
  if (k < smin || k > smax || k % 2 != smin % 2) {
    cout << "NO\n";
    return 0;
  }
  long long int l = 0;
  long long int r = n + 1;
  while (r > l + 1) {
    long long int m = (l + r) / 2;
    long long int s = 0;
    for (auto x : d) {
      if (x <= m) {
        s += x;
      } else {
        long long int y = (x - m + 1) / 2;
        s += x - 2 * y;
      }
    }
    if (s < k)
      l = m;
    else
      r = m;
  }
  for (auto &x : d) {
    if (x > r) {
      long long int y = (x - r + 1) / 2;
      x -= 2 * y;
    }
  }
  long long int s = 0;
  for (auto x : d) s += x;
  for (auto &x : d) {
    if (s > k && x == r) {
      x -= 2;
      s -= 2;
    }
  }
  assert(s == k);
  ::r.resize(n);
  dfs3(c, -1);
  cout << "YES\n";
  for (auto e : res) {
    cout << e.first + 1 << " " << e.second + 1 << "\n";
  }
  return 0;
}