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 std::cin;
using std::cout;
constexpr int nmax = 100000;
int n;
long long k, lobound, upbound;
std::vector<int> adjl[nmax + 1], nodes[nmax + 1];
int dad[nmax + 1], sub[nmax + 1], dep[nmax + 1], subtree_of[nmax + 1];
int root;
struct pii {
  int u, dep;
};
bool operator<(const pii &l, const pii &r) {
  return (l.dep != r.dep) ? (l.dep > r.dep) : (l.u < r.u);
}
std::set<pii> non_leaves[nmax + 1];
void input() {
  cin >> n >> k;
  for (int i = 1; i < n; ++i) {
    int u, v;
    cin >> u >> v;
    adjl[u].push_back(v);
    adjl[v].push_back(u);
  }
}
void dfs0(int u) {
  sub[u] = 1;
  for (int v : adjl[u])
    if (sub[v] == 0) {
      dfs0(v);
      sub[u] += sub[v];
    }
}
void root_at_centroid() {
  dfs0(1);
  root = 1;
  while (1) {
    bool ok = true;
    for (int v : adjl[root])
      if (sub[v] < sub[root] && sub[v] * 2 > n) root = v, ok = false;
    if (ok) break;
  }
}
void dfs(int u) {
  sub[u] = 1;
  for (int &v : adjl[u]) {
    if (v == dad[u]) {
      if (v == adjl[u].back()) {
        adjl[u].pop_back();
        break;
      }
      std::swap(v, adjl[u].back());
    }
    dad[v] = u;
    dep[v] = dep[u] + 1;
    dfs(v);
    sub[u] += sub[v];
  }
  if (u != root) {
    lobound += sub[u] % 2;
    upbound += sub[u];
  }
}
struct pii2 {
  int u, pop;
  operator int() const { return pop; }
};
std::priority_queue<pii2> pq;
void dfs_add(int u, int r) {
  subtree_of[u] = r;
  if (!adjl[u].empty()) non_leaves[r].insert({u, dep[u]});
  for (int v : adjl[u]) dfs_add(v, r);
}
int current_max_subtree() {
  auto p = pq.top();
  pq.pop();
  p.pop -= 2;
  if (p.pop) pq.push(p);
  return p.u;
}
bool bigger_first(int l, int r) { return nodes[l].size() > nodes[r].size(); }
int extract_any_element_from(std::vector<int> &v) {
  int res = v.back();
  v.pop_back();
  return res;
}
int &semi_back(std::vector<int> &v) { return v[v.size() - 2]; }
std::pair<int, int> extract_at_most_2_available_nodes(std::vector<int> &v) {
  std::pair<int, int> res{};
  int cnt = 0;
  while (cnt < 2 && !v.empty()) {
    if (subtree_of[v.back()]) {
      (cnt ? res.second : res.first) = v.back();
      ++cnt;
    }
    v.pop_back();
  }
  return res;
}
void match_2_nodes_from(int root1, int root2) {
  cout << extract_any_element_from(nodes[root1]) << ' '
       << extract_any_element_from(nodes[root2]) << '\n';
}
int main() {
  input();
  root_at_centroid();
  dfs(root);
  if (k < lobound || k > upbound || (k + lobound) % 2 == 1) {
    cout << "NO";
    return 0;
  }
  cout << "YES\n";
  for (int u : adjl[root]) {
    dfs_add(u, u);
    pq.push({u, sub[u]});
  }
  for (long long cur = upbound; cur > k;) {
    int s = current_max_subtree();
    bool finish = false;
    while (1) {
      int u = non_leaves[s].begin()->u;
      std::pair<int, int> p = extract_at_most_2_available_nodes(adjl[u]);
      if (p.first == 0)
        non_leaves[s].erase(non_leaves[s].begin());
      else {
        if (cur - dep[u] * 2 >= k) {
          cur -= dep[u] * 2;
          if (p.second) {
            subtree_of[p.first] = 0;
            subtree_of[p.second] = 0;
            cout << p.first << ' ' << p.second << '\n';
          } else {
            subtree_of[u] = 0;
            subtree_of[p.first] = 0;
            cout << u << ' ' << p.first << '\n';
          }
          if (adjl[u].empty()) non_leaves[s].erase(non_leaves[s].begin());
          break;
        } else {
          if (p.first) adjl[u].push_back(p.first);
          if (p.second) adjl[u].push_back(p.second);
          finish = true;
          break;
        }
      }
    }
    if (finish) {
      while (1) {
        auto it = non_leaves[s].lower_bound({0, int((cur - k) / 2)});
        int u = it->u;
        while (!adjl[u].empty() && !subtree_of[adjl[u].back()])
          adjl[u].pop_back();
        if (adjl[u].empty())
          non_leaves[s].erase(it);
        else {
          cout << u << ' ' << adjl[u].back() << '\n';
          subtree_of[u] = 0;
          subtree_of[adjl[u].back()] = 0;
          break;
        }
      }
      cur = k;
    }
  }
  for (int u = 1; u <= n; ++u)
    if (subtree_of[u]) nodes[subtree_of[u]].push_back(u);
  nodes[root].push_back(root);
  std::vector<int> sub_root;
  for (int u = 1; u <= n; ++u)
    if (!nodes[u].empty()) sub_root.push_back(u);
  std::sort(sub_root.begin(), sub_root.end(), bigger_first);
  std::vector<int> border;
  for (int i = sub_root.size() - 1; i >= 0; --i)
    if (i == sub_root.size() - 1 ||
        nodes[sub_root[i]].size() > nodes[sub_root[i + 1]].size())
      border.push_back(i);
  while (!border.empty()) {
    if (border.back() == 0) {
      int b2 = semi_back(border);
      match_2_nodes_from(sub_root[0], sub_root[b2]);
      if ((b2 == sub_root.size() - 1 && !nodes[sub_root[b2]].empty()) ||
          (b2 < sub_root.size() - 1 &&
           nodes[sub_root[b2]].size() > nodes[sub_root[b2 + 1]].size())) {
        border.push_back(0);
        semi_back(border) = b2;
      }
      b2 = --semi_back(border);
      if (b2 == 0 || nodes[sub_root[0]].size() == nodes[sub_root[b2]].size())
        border.pop_back();
    } else {
      match_2_nodes_from(sub_root[border.back()], sub_root[border.back() - 1]);
      int b = border.back();
      if ((b == sub_root.size() - 1 && !nodes[sub_root[b]].empty()) ||
          (b < sub_root.size() - 1 &&
           nodes[sub_root[b]].size() > nodes[sub_root[b + 1]].size()))
        border.push_back(b);
      border.back() -= 2;
      if (border.back() == -1) border.pop_back();
    }
  }
  return 0;
}