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 n;
long long k;
int hd[100005], _hd;
struct edge {
  int v, nxt;
} e[100005 << 1];
inline void addedge(int u, int v) {
  e[++_hd] = (edge){v, hd[u]};
  hd[u] = _hd;
}
int sz[100005], rt, mx;
inline void fndrt(int u, int fa) {
  sz[u] = 1;
  int tmp = 0;
  for (int i = hd[u]; i; i = e[i].nxt) {
    int v = e[i].v;
    if (v == fa) continue;
    fndrt(v, u);
    sz[u] += sz[v];
    tmp = std::max(tmp, sz[v]);
  }
  tmp = std::max(tmp, n - sz[u]);
  if (tmp < mx) {
    rt = u;
    mx = tmp;
  }
}
std::priority_queue<std::pair<int, int> > h;
int fa[100005], dep[100005];
bool vis[100005];
std::vector<int> son[100005];
std::set<std::pair<std::pair<int, int>, int> > s[100005];
inline void dfs(int u, int id) {
  dep[u] = dep[fa[u]] + 1;
  for (int i = hd[u]; i; i = e[i].nxt) {
    int v = e[i].v;
    if (v == fa[u]) continue;
    fa[v] = u;
    son[u].push_back(v);
    dfs(v, id);
  }
  sz[u] = son[u].size();
  s[id].insert(std::make_pair(std::make_pair(dep[u], sz[u]), u));
}
std::vector<std::pair<int, int> > ans;
int main() {
  scanf("%d%lld", &n, &k);
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    addedge(u, v);
    addedge(v, u);
  }
  mx = n;
  fndrt(1, 0);
  sz[rt] = 0;
  for (int i = hd[rt]; i; i = e[i].nxt) {
    int u = e[i].v;
    fa[u] = rt;
    dfs(u, u);
    h.push(std::make_pair(s[u].size(), u));
  }
  long long sum = 0;
  for (int i = 1; i <= n; i++) sum += dep[i];
  k = sum - k;
  if (k < 0 || k % 2 == 1) {
    puts("NO");
    return 0;
  }
  k /= 2;
  int tmp = 0;
  while (h.size() && k) {
    int t = h.top().second;
    tmp++;
    h.pop();
    int d = dep[s[t].rbegin()->second];
    if (k >= d - 1) {
      auto it = s[t].lower_bound(std::make_pair(std::make_pair(d - 1, 1), 0));
      int u = it->second;
      s[t].erase(it);
      if (sz[u] == 1) {
        int v = son[u].back();
        son[u].pop_back();
        while (vis[v]) {
          v = son[u].back();
          son[u].pop_back();
        }
        if (fa[u] != rt) {
          s[t].erase(
              std::make_pair(std::make_pair(dep[fa[u]], sz[fa[u]]), fa[u]));
          sz[fa[u]]--;
          s[t].insert(
              std::make_pair(std::make_pair(dep[fa[u]], sz[fa[u]]), fa[u]));
        }
        sz[u]--;
        vis[u] = vis[v] = 1;
        s[t].erase(std::make_pair(std::make_pair(dep[v], sz[v]), v));
        ans.push_back(std::make_pair(u, v));
      } else {
        int v = son[u].back();
        son[u].pop_back();
        while (vis[v]) {
          v = son[u].back();
          son[u].pop_back();
        }
        int w = son[u].back();
        son[u].pop_back();
        while (vis[w]) {
          w = son[u].back();
          son[u].pop_back();
        }
        sz[u] -= 2;
        vis[v] = vis[w] = 1;
        s[t].erase(std::make_pair(std::make_pair(dep[v], sz[v]), v));
        s[t].erase(std::make_pair(std::make_pair(dep[w], sz[w]), w));
        s[t].insert(std::make_pair(std::make_pair(dep[u], sz[u]), u));
        ans.push_back(std::make_pair(v, w));
      }
      k -= d - 1;
    } else {
      auto it = s[t].lower_bound(std::make_pair(std::make_pair(k, 1), 0));
      int u = it->second;
      s[t].erase(it);
      int v = son[u].back();
      son[u].pop_back();
      while (vis[v]) {
        v = son[u].back();
        son[u].pop_back();
      }
      if (fa[u] != rt) {
        s[t].erase(
            std::make_pair(std::make_pair(dep[fa[u]], sz[fa[u]]), fa[u]));
        sz[fa[u]]--;
        s[t].insert(
            std::make_pair(std::make_pair(dep[fa[u]], sz[fa[u]]), fa[u]));
      }
      sz[u]--;
      vis[u] = vis[v] = 1;
      s[t].erase(std::make_pair(std::make_pair(dep[v], sz[v]), v));
      ans.push_back(std::make_pair(u, v));
      k = 0;
    }
    if (s[t].size()) h.push(std::make_pair(s[t].size(), t));
  }
  while (h.size() > 1) {
    int u = h.top().second;
    h.pop();
    int v = h.top().second;
    h.pop();
    auto it1 = s[u].begin(), it2 = s[v].begin();
    ans.push_back(std::make_pair(it1->second, it2->second));
    s[u].erase(it1);
    s[v].erase(it2);
    if (s[u].size()) h.push(std::make_pair(s[u].size(), u));
    if (s[v].size()) h.push(std::make_pair(s[v].size(), v));
  }
  ans.push_back(std::make_pair(s[h.top().second].begin()->second, rt));
  puts("YES");
  for (auto it = ans.rbegin(); it != ans.rend(); it++)
    printf("%d %d\n", it->first, it->second);
}