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() {
  char c = getchar();
  long long x = 0;
  bool f = 0;
  for (; !isdigit(c); c = getchar()) f ^= !(c ^ 45);
  for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
  if (f) x = -x;
  return x;
}
long long n, m;
vector<long long> e[100005];
vector<long long> res;
long long sz[100005], mxp[100005], rt;
void getrt(long long u, long long pa) {
  sz[u] = 1;
  for (auto v : e[u]) {
    if (v == pa) continue;
    getrt(v, u), sz[u] += sz[v], mxp[u] = max(mxp[u], sz[v]);
  }
  mxp[u] = max(mxp[u], n - sz[u]);
  if (mxp[rt] > mxp[u]) rt = u;
}
long long deg[100005], dep[100005], fa[100005], top[100005];
set<pair<long long, long long> > s, S[100005];
void dfs(long long u, long long pa, long long tp) {
  top[u] = tp;
  fa[u] = pa;
  if (tp && (long long)e[u].size() >= 2) S[tp].insert(make_pair(dep[u], u));
  for (auto v : e[u]) {
    if (v == pa) continue;
    dep[v] = dep[u] + 1, deg[u]++, fa[v] = u;
    dfs(v, u, tp);
  }
}
bool vis[100005];
inline void del(long long x) {
  vis[x] = 1;
  deg[fa[x]]--;
  if (!deg[fa[x]]) S[top[x]].erase(make_pair(dep[fa[x]], fa[x]));
}
void getrest(long long u) {
  if (!vis[u]) res.push_back(u);
  for (auto v : e[u])
    if (v != fa[u]) getrest(v);
}
signed main() {
  n = read(), m = read();
  for (register long long i = (2); i <= (n); ++i) {
    long long u = read(), v = read();
    e[u].push_back(v), e[v].push_back(u);
  }
  mxp[rt = 0] = n + 1, getrt(1, 0), getrt(rt, 0);
  long long mx = 0, mn = 0;
  for (register long long i = (1); i <= (n); ++i)
    if (i != rt) mx += sz[i], mn += (sz[i] & 1);
  if (m > mx || m < mn || (mx - m) % 2 != 0) return puts("NO") & 0;
  puts("YES");
  long long k = mx - m;
  for (auto v : e[rt])
    if (sz[v] > 1) s.insert(make_pair(sz[v], v));
  for (auto v : e[rt]) dep[v] = 1, dfs(v, rt, v);
  while (k) {
    long long u = (--s.end())->second;
    s.erase(--s.end());
    long long x = (--S[u].end())->second;
    vector<long long> o;
    if (2 * dep[x] > k) {
      x = (S[u].lower_bound(make_pair(k / 2, 0)))->second;
      for (auto v : e[x])
        if (v != fa[x] && !vis[v]) o.push_back(v);
      if (o.size() < 2) o.push_back(x);
      cout << o[0] << ' ' << o[1] << endl;
      vis[o[0]] = vis[o[1]] = 1;
      break;
    }
    for (auto v : e[x])
      if (v != fa[x] && !vis[v]) o.push_back(v);
    if (o.size() < 2) o.push_back(x);
    cout << o[0] << ' ' << o[1] << endl;
    del(o[0]), del(o[1]);
    sz[u] -= 2;
    k -= dep[x] * 2;
    if (sz[u] > 1) s.insert(make_pair(sz[u], u));
  }
  getrest(rt);
  for (long long i = 0; i < res.size() / 2; ++i)
    cout << res[i] << ' ' << res[i + (res.size() / 2)] << endl;
  return 0;
}