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>
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int n;
  std::cin >> n;
  int64_t k;
  std::cin >> k;
  std::vector<std::vector<int>> e(n);
  for (int i = 0; i < n - 1; ++i) {
    int u, v;
    std::cin >> u >> v;
    --u;
    --v;
    e[u].push_back(v);
    e[v].push_back(u);
  }
  std::vector<int> siz(n), w(n);
  std::function<void(int, int)> dfs = [&](int u, int p) {
    siz[u] = 1;
    for (auto v : e[u]) {
      if (v == p) continue;
      dfs(v, u);
      siz[u] += siz[v];
    }
  };
  dfs(0, -1);
  int64_t L = 0, R = 0;
  for (int i = 1; i < n; ++i) {
    L += siz[i] % 2;
    R += w[i] = std::min(siz[i], n - siz[i]);
  }
  if (k < L || k > R || (k - L) % 2 == 1) {
    std::cout << "NO\n";
    return 0;
  }
  std::cout << "YES\n";
  int l = 0, r = n;
  while (l < r) {
    int m = (l + r) / 2;
    int64_t s = 0;
    for (int i = 1; i < n; ++i) {
      if (w[i] >= m) {
        s += m + (w[i] - m) % 2;
      } else {
        s += w[i];
      }
    }
    if (s >= k) {
      r = m;
    } else {
      l = m + 1;
    }
  }
  int64_t s = 0;
  for (int i = 1; i < n; ++i) {
    if (w[i] > l) w[i] = l + (w[i] - l) % 2;
    s += w[i];
  }
  for (int i = 1; i < n; ++i) {
    if (w[i] == l + 1 && s > k) {
      s -= 2;
      w[i] -= 2;
    }
  }
  std::vector<std::vector<int>> t(n);
  std::function<void(int, int)> solve = [&](int u, int p) {
    int tot = 1;
    t[u].push_back(u);
    std::set<std::pair<int, int>> s;
    s.emplace(1, u);
    for (auto v : e[u]) {
      if (v == p) continue;
      solve(v, u);
      tot += t[v].size();
      s.emplace(t[v].size(), v);
    }
    int need = (tot - w[u]) / 2;
    while (need--) {
      int u = s.rbegin()->second;
      s.erase(*s.rbegin());
      int v = s.rbegin()->second;
      s.erase(*s.rbegin());
      std::cout << t[u].back() + 1 << " " << t[v].back() + 1 << "\n";
      t[u].pop_back();
      t[v].pop_back();
      s.emplace(t[u].size(), u);
      s.emplace(t[v].size(), v);
    }
    for (auto v : e[u]) {
      if (v == p) continue;
      if (t[v].size() > t[u].size()) std::swap(t[u], t[v]);
      t[u].insert(t[u].end(), t[v].begin(), t[v].end());
    }
  };
  solve(0, -1);
  return 0;
}