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;
inline long long read() {
  long long x = 0, f = 1;
  char c = getchar();
  while ((c < '0' || c > '9') && (c != '-')) c = getchar();
  if (c == '-') f = -1, c = getchar();
  while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
  return x * f;
}
const int N = 1e5 + 10;
int n;
long long k;
vector<int> e[N];
inline void GG() {
  puts("NO");
  exit(0);
}
int rt, L, siz[N], mx[N];
long long R;
inline void dfs(int u, int fa) {
  siz[u] = 1;
  for (auto v : e[u])
    if (v != fa) {
      dfs(v, u), siz[u] += siz[v], mx[u] = max(mx[u], siz[v]);
    }
  mx[u] = max(mx[u], n - siz[u]);
  L += (siz[u] & 1), R += min(siz[u], n - siz[u]);
  if (mx[u] < mx[rt]) rt = u;
}
int fa[N], Rt[N], dep[N], deg[N];
multiset<pair<int, int> > s[N];
multiset<pair<int, int> > S;
inline void Dfs(int u, int fa, int rt) {
  Rt[u] = rt;
  ::fa[u] = fa, dep[u] = dep[fa] + 1, siz[u] = 1, deg[u] = 0;
  for (auto v : e[u])
    if (v != fa) Dfs(v, u, rt), siz[u] += siz[v], ++deg[u];
  if (deg[u] >= 1) s[rt].insert(make_pair(dep[u], u));
}
bool vis[N];
int cnt, p[N];
vector<int> vec[N];
inline void Dfs2(int u, int fa, int k) {
  if (!vis[u]) vec[k].push_back(u);
  for (auto v : e[u])
    if (v != fa) Dfs2(v, u, k);
}
inline void solve() {
  for (auto v : e[rt]) ++cnt, p[cnt] = cnt, Dfs2(v, rt, cnt);
  vec[++cnt].push_back(rt), p[cnt] = cnt;
  sort(p + 1, p + 1 + cnt, [](int a, int b) {
    return ((int)(vec[a]).size()) > ((int)(vec[b]).size());
  });
  int x = ((int)(vec[p[1]]).size()), y = 0;
  for (register int i = (2); i <= (cnt); i++) y += ((int)(vec[p[i]]).size());
  int l = 2, r = cnt;
  while (vec[p[r]].empty()) --r;
  while (y > x) {
    printf("%d %d\n", vec[p[l]].back(), vec[p[r]].back());
    vec[p[l]].pop_back(), vec[p[r]].pop_back();
    y -= 2;
    if (vec[p[l]].empty()) ++l;
    if (vec[p[r]].empty()) --r;
  }
  for (auto i : vec[p[1]]) {
    printf("%d %d\n", i, vec[p[l]].back());
    vec[p[l]].pop_back();
    if (vec[p[l]].empty()) ++l;
  }
}
int main() {
  n = read(), k = read();
  for (register int i = (1); i < (n); i++) {
    int x = read(), y = read();
    e[x].push_back(y), e[y].push_back(x);
  }
  mx[0] = 1e9, dfs(1, 0);
  if (k < L || k > R || k % 2 != L % 2) GG();
  puts("YES");
  if (k == R) return solve(), 0;
  for (auto v : e[rt]) Dfs(v, rt, v), S.insert(make_pair(siz[v], v));
  while (233) {
    int u = (*--S.end()).second;
    S.erase(--S.end());
    if (s[u].empty()) return solve(), 0;
    pair<int, int> tmp = *--s[u].end();
    int dep = tmp.first, p = tmp.second;
    if (k + 2 * dep < R) {
      if (deg[p] == 1) {
        vis[p] = 1;
        for (auto v : e[p])
          if (v != fa[p] && !vis[v]) {
            vis[v] = 1, printf("%d %d\n", p, v);
            break;
          }
        k--, L--, R--;
        s[u].erase(make_pair(::dep[p], p));
        if (p != u) {
          s[u].erase(make_pair(::dep[fa[p]], fa[p]));
          deg[fa[p]]--;
          if (deg[fa[p]] >= 1) s[u].insert(make_pair(::dep[fa[p]], fa[p]));
        }
      } else {
        int a = 0, b = 0;
        for (auto v : e[p])
          if (v != fa[p] && !vis[v]) {
            if (!a)
              a = v;
            else {
              b = v;
              break;
            }
          }
        printf("%d %d\n", a, b), vis[a] = vis[b] = 1;
        s[u].erase(make_pair(::dep[p], p));
        deg[p] -= 2, k -= 2, L -= 2, R -= 2;
        if (deg[p] >= 1) s[u].insert(make_pair(::dep[p], p));
      }
      siz[u] -= 2;
      if (siz[u] > 1) S.insert(make_pair(siz[u], u));
      R -= 2 * dep;
    } else {
      pair<int, int> tmp = *s[u].lower_bound(make_pair((R - k) / 2, 0));
      int a = tmp.second, b = 0;
      for (auto v : e[a])
        if (v != fa[a] && !vis[v]) {
          b = v;
          break;
        }
      vis[a] = vis[b] = 1, printf("%d %d\n", a, b);
      return solve(), 0;
    }
  }
}