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 = 1e5 + 10;
int n, siz[N], rt, mn = 1e9, dep[N], rem[N], fa[N];
long long k, L, R;
vector<int> E[N], can[N], vec;
set<int> son[N];
bool del[N];
void getrt(int u, int fa) {
  siz[u] = 1;
  int mx = 0;
  for (auto v : E[u])
    if (v != fa) {
      getrt(v, u);
      siz[u] += siz[v];
      mx = max(mx, siz[v]);
    }
  mx = max(mx, n - siz[u]);
  if (mx < mn) mn = mx, rt = u;
}
void dfs1(int u, int ff, int bel) {
  dep[u] = dep[ff] + 1;
  fa[u] = ff;
  siz[u] = 1;
  can[bel].push_back(u);
  for (auto v : E[u])
    if (v != ff) son[u].insert(v), dfs1(v, u, bel), siz[u] += siz[v];
}
void dfs2(int u, int ff) {
  if (!del[u]) vec.push_back(u);
  for (auto v : E[u])
    if (v != ff) dfs2(v, u);
}
struct cmp {
  bool operator()(int a, int b) { return rem[a] > rem[b]; }
};
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> k;
  for (int i = 1, u, v; i < n; i++)
    cin >> u >> v, E[u].push_back(v), E[v].push_back(u);
  getrt(1, 0);
  for (auto v : E[rt]) {
    dfs1(v, rt, v);
    sort(can[v].begin(), can[v].end(),
         [&](int a, int b) { return dep[a] < dep[b]; });
    rem[v] = siz[v];
  }
  for (int i = 1; i <= n; i++)
    if (i != rt) L += siz[i] & 1, R += siz[i];
  if (!(L <= k && k <= R && (L & 1) == (k & 1))) return cout << "NO", 0;
  cout << "YES\n";
  multiset<int, cmp> all;
  for (auto v : E[rt]) all.insert(v);
  vector<pair<int, int> > ans;
  while (k != R) {
    int v = *all.begin();
    all.erase(all.begin());
    while (son[can[v].back()].empty()) can[v].pop_back();
    int w = can[v].back();
    if (k + 2 * dep[w] <= R) {
      if (int(son[w].size()) > 1) {
        int a = *son[w].begin();
        son[w].erase(son[w].begin());
        int b = *son[w].begin();
        son[w].erase(son[w].begin());
        rem[v] -= 2;
        ans.push_back(make_pair(a, b));
        k -= 2;
        L -= 2;
        R -= 2 * dep[w] + 2;
        del[a] = del[b] = 1;
      } else {
        int a = w, b = *son[w].begin();
        son[w].clear();
        rem[v] -= 2;
        ans.push_back(make_pair(a, b));
        k -= 1;
        L -= 1;
        R -= 2 * dep[w] + 1;
        if (fa[w] != rt) son[fa[w]].erase(w);
        del[a] = del[b] = 1;
      }
    } else {
      for (auto t : can[v])
        if (k + 2 * dep[t] == R && !son[t].empty()) {
          w = t;
          break;
        }
      int a = w, b = *son[w].begin();
      ans.push_back(make_pair(a, b));
      del[a] = del[b] = 1;
      break;
    }
    all.insert(v);
  }
  dfs2(rt, 0);
  for (int i = 0; i < int(vec.size()) / 2; i++)
    ans.push_back(make_pair(vec[i], vec[i + int(vec.size()) / 2]));
  for (auto t : ans) cout << t.first << ' ' << t.second << '\n';
  return 0;
}