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 ch = getchar();
  long long nega = 1;
  while (!isdigit(ch)) {
    if (ch == '-') nega = -1;
    ch = getchar();
  }
  long long ans = 0;
  while (isdigit(ch)) {
    ans = ans * 10 + ch - 48;
    ch = getchar();
  }
  if (nega == -1) return -ans;
  return ans;
}
vector<long long> G[100005];
long long n, k, siz[100005];
long long rt, sum;
void dfs1(long long u, long long f) {
  siz[u] = 1;
  long long maxn = 0;
  for (long long v : G[u]) {
    if (v == f) continue;
    dfs1(v, u);
    siz[u] += siz[v];
    maxn = max(maxn, siz[v]);
  }
  maxn = max(maxn, n - siz[u]);
  if (maxn * 2 <= n) rt = u;
}
long long fa[100005], dep[100005], cnt[100005], bl[100005];
void dfs2(long long u, long long f) {
  fa[u] = f, dep[u] = dep[f] + 1, siz[u] = 1;
  sum += dep[u] - 1;
  for (long long v : G[u]) {
    if (v == f) continue;
    dfs2(v, u);
    siz[u] += siz[v];
    if (G[v].size() > 1) cnt[u]++;
  }
}
struct Node {
  long long id, siz;
  Node(long long x, long long y) { id = x, siz = y; }
  bool operator<(const Node &x) const { return siz < x.siz; }
};
priority_queue<Node> qn;
struct Fa {
  long long id, dep;
  Fa(long long x, long long y) { id = x, dep = y; }
  bool operator<(const Fa &x) const { return dep < x.dep; }
};
priority_queue<Fa> q[100005];
vector<long long> sn[100005];
void dfs3(long long u, long long f, long long id) {
  if (cnt[u] == 0 && G[u].size() != 1) q[id].emplace(u, dep[u]);
  bl[u] = id;
  for (long long v : G[u]) {
    if (v == f) continue;
    if (G[v].size() == 1) sn[u].push_back(v);
    dfs3(v, u, id);
  }
}
vector<pair<long long, long long> > ans;
bool vis[100005];
long long dfs4(long long u, long long f, long long ned) {
  if (!vis[u] && dep[u] == ned && (cnt[u] > 0 || sn[u].size() > 0)) return u;
  for (long long v : G[u]) {
    if (v == f) continue;
    long long R = dfs4(v, u, ned);
    if (R) return R;
  }
  return 0;
}
vector<long long> res[100005];
void dfs5(long long u, long long f, long long id) {
  if (!vis[u]) res[id].push_back(u);
  for (long long v : G[u]) {
    if (v == f) continue;
    dfs5(v, u, id);
  }
}
signed main() {
  cin >> n >> k;
  for (long long i = 1; i < n; i++) {
    long long u = read(), v = read();
    G[u].push_back(v), G[v].push_back(u);
  }
  dfs1(1, 0);
  dfs2(rt, 0);
  for (long long v : G[rt]) qn.emplace(v, siz[v]);
  for (long long v : G[rt]) dfs3(v, rt, v);
  long long Ans = 0;
  for (long long i = 1; i <= n; i++) Ans += siz[i] & 1;
  if ((sum - k) & 1) {
    cout << "NO\n";
    return 0;
  }
  if (sum < k) {
    cout << "NO\n";
    return 0;
  }
  while (sum > k) {
    Node u = qn.top();
    qn.pop();
    if (u.siz == 1) break;
    long long b = u.id;
    if (q[b].empty()) break;
    Fa x = q[b].top();
    q[b].pop();
    long long id = x.id;
    if (sum - (dep[id] - 1) * 2 < k) {
      u.siz -= 2;
      if (u.siz > 0) qn.push(u);
      long long r = dfs4(b, rt, (sum - k) / 2 + 1);
      vector<long long> t;
      t.push_back(r);
      for (long long v : G[r]) {
        if (v == fa[r]) continue;
        if (!vis[v]) t.push_back(v);
      }
      sum = k;
      ans.emplace_back(t[0], t[1]);
      vis[t[0]] = vis[t[1]] = 1;
      break;
    }
    if (!sn[id].size()) {
      qn.push(u);
      continue;
    }
    u.siz -= 2;
    if (u.siz > 0) qn.push(u);
    sum -= (dep[id] - 1) * 2;
    if (sn[id].size() == 1) {
      ans.emplace_back(id, sn[id][0]);
      sn[id].clear();
      if (fa[id] != rt) {
        long long f = fa[id];
        cnt[f]--;
        if (!cnt[f]) {
          if (sn[f].size())
            q[b].emplace(f, dep[f]);
          else {
            long long ff = fa[f];
            if (ff != rt) {
              cnt[ff]--, sn[ff].push_back(f);
              q[b].emplace(ff, dep[ff]);
            }
          }
        }
      }
    } else if (sn[id].size() == 2) {
      ans.emplace_back(sn[id][0], sn[id][1]);
      sn[id].clear();
      if (fa[id] != rt) {
        cnt[fa[id]]--;
        sn[fa[id]].push_back(id);
        if (!cnt[fa[id]]) q[bl[id]].emplace(fa[id], dep[fa[id]]);
      }
    } else {
      long long X = sn[id].back();
      sn[id].pop_back();
      long long Y = sn[id].back();
      sn[id].pop_back();
      q[b].emplace(id, dep[id]);
      ans.emplace_back(X, Y);
    }
    auto [A, B] = ans.back();
    vis[A] = vis[B] = 1;
  }
  if (sum != k) {
    cout << "NO\n";
    return 0;
  }
  for (long long v : G[rt]) dfs5(v, rt, v);
  while (qn.size() > 1) {
    auto [id1, _] = qn.top();
    qn.pop();
    auto [id2, __] = qn.top();
    qn.pop();
    if (_ != 1) qn.emplace(id1, _ - 1);
    if (__ != 1) qn.emplace(id2, __ - 1);
    ans.emplace_back(res[id1].back(), res[id2].back());
    res[id1].pop_back(), res[id2].pop_back();
  }
  auto [id1, _] = qn.top();
  qn.pop();
  assert(_ == 1);
  ans.emplace_back(res[id1].back(), rt);
  cout << "YES\n";
  for (auto [x, y] : ans) printf("%lld %lld\n", x, y);
  return 0;
}