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;
template <typename G1, typename G2 = G1, typename G3 = G1>
struct triple {
  G1 first;
  G2 second;
  G3 T;
};
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n;
  long long h;
  cin >> n >> h;
  vector<vector<int>> g(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);
  }
  vector<int> sub(n), p(n), d(n), up(n);
  function<void(int, int)> dfs = [&](int c, int u) {
    sub[c] = 1;
    up[c] = u;
    for (auto v : g[c])
      if (v != p[c]) {
        p[v] = c;
        d[v] = d[c] + 1;
        if (p[c] == -1) u = v;
        dfs(v, u);
        sub[c] += sub[v];
      }
  };
  d[0] = 0;
  p[0] = -1;
  dfs(0, -1);
  int r = 0;
  while (true) {
    bool changed = false;
    for (auto v : g[r])
      if (v != p[r] && sub[v] >= n / 2) {
        changed = true;
        r = v;
        break;
      }
    if (!changed) break;
  }
  d[r] = 0;
  p[r] = -1;
  dfs(r, -1);
  long long ck = 0, mk = 0;
  for (int i = 0; i < n; i++)
    if (i != r) ck += sub[i], mk += sub[i] % 2;
  if (h < mk || h > ck || ck % 2 != h % 2) {
    cout << "NO\n";
    return 0;
  }
  cout << "YES\n";
  vector<vector<int>> t(n);
  for (int i = 0; i < n; i++)
    if (p[i] != -1) t[p[i]].push_back(i);
  vector<int> deg(n);
  for (int i = 0; i < n; i++) deg[i] = t[i].size();
  vector<set<pair<long long, long long>>> lca(n);
  for (int i = 0; i < n; i++)
    if (i != r && deg[i] != 0) lca[up[i]].insert({2 * d[i], i});
  set<pair<long long, long long>> s;
  for (auto i : t[r]) s.insert({sub[i], i});
  vector<bool> matched(n);
  auto kill = [&](int i) {
    if (--deg[p[i]] == 0) {
      i = p[i];
      lca[up[i]].erase({2 * d[i], i});
    }
  };
  vector<pair<long long, long long>> ans;
  while (ck > h) {
    int u = (--s.end())->second;
    s.erase(--s.end());
    pair<long long, long long> x = *(--lca[u].upper_bound({ck - h + 1, -1}));
    vector<int> temp;
    while (!t[x.second].empty() && temp.size() < 2) {
      if (!matched[t[x.second].back()]) temp.push_back(t[x.second].back());
      t[x.second].pop_back();
    }
    if (temp.size() < 2) temp.push_back(x.second);
    ans.push_back({temp[0], temp[1]});
    kill(temp[0]);
    kill(temp[1]);
    matched[temp[0]] = matched[temp[1]] = true;
    ck -= x.first;
    sub[u] -= 2;
    if (sub[u] > 1) s.insert({sub[u], u});
  }
  vector<vector<int>> w(n);
  for (int i = 0; i < n; i++)
    if (i != r && !matched[i]) w[up[i]].push_back(i);
  w[r].push_back(r);
  priority_queue<pair<long long, long long>> pq;
  for (int i = 0; i < n; i++)
    if (!w[i].empty()) pq.push({w[i].size(), i});
  while (!pq.empty()) {
    pair<long long, long long> a = pq.top();
    pq.pop();
    pair<long long, long long> b = pq.top();
    pq.pop();
    ans.push_back({w[a.second].back(), w[b.second].back()});
    w[a.second].pop_back();
    w[b.second].pop_back();
    if (!w[a.second].empty()) pq.push({w[a.second].size(), a.second});
    if (!w[b.second].empty()) pq.push({w[b.second].size(), b.second});
  }
  for (int i = 0; i < n / 2; i++)
    cout << ans[i].first + 1 << " " << ans[i].second + 1 << '\n';
  return 0;
}