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 = 100005;
using ll = long long;
using pii = pair<int, int>;
int n;
ll kk;
vector<int> v[N];
int sz[N], dep[N], fa[N], rt;
ll mn = N, mx = 0;
void dfs1(int pos, int fa) {
  sz[pos] = 1;
  int mxsz = 0;
  for (auto &i : v[pos])
    if (i != fa) dfs1(i, pos), sz[pos] += sz[i], mxsz = max(mxsz, sz[i]);
  mxsz = max(mxsz, n - sz[pos]);
  if (mn > mxsz) mn = mxsz, rt = pos;
}
int top[N], deg[N];
set<pii> s[N], r;
void dfs2(int pos, int tp) {
  sz[pos] = 1;
  top[pos] = tp;
  if (tp && int(v[pos].size()) - 1 >= 1) s[tp].insert({dep[pos], pos});
  for (auto &i : v[pos])
    if (i != fa[pos]) {
      if (pos == rt) tp = i;
      ++deg[pos];
      dep[i] = dep[pos] + 1;
      fa[i] = pos;
      dfs2(i, tp);
      sz[pos] += sz[i];
    }
}
void del(int pos) {
  if (!--deg[fa[pos]]) s[top[pos]].erase({dep[fa[pos]], fa[pos]});
}
int vis[N];
vector<int> rem;
void dfs3(int pos) {
  if (!vis[pos]) rem.push_back(pos);
  for (auto &i : v[pos])
    if (i != fa[pos]) dfs3(i);
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> kk;
  int t1, t2;
  for (int i = 1; i < n; i++)
    cin >> t1 >> t2, v[t1].push_back(t2), v[t2].push_back(t1);
  dfs1(1, -1);
  dep[rt] = 0;
  dfs2(rt, 0);
  mn = mx = 0;
  for (int i = 1; i <= n; i++)
    if (i != rt) mx += sz[i], mn += sz[i] % 2;
  if (kk > mx || kk < mn || (mx - kk) & 1) {
    puts("NO");
    return 0;
  }
  puts("YES");
  for (auto &i : v[rt])
    if (sz[i] > 1) r.insert({sz[i], i});
  ll rs = mx - kk;
  while (rs) {
    int cur = r.rbegin()->second;
    r.erase(--r.end());
    int pos = s[cur].rbegin()->second;
    if (2 * dep[pos] > rs) {
      rs /= 2;
      pos = s[cur].lower_bound({rs, 0})->second;
      vector<int> vv;
      for (auto &i : v[pos])
        if (!vis[i] && fa[pos] != i) vv.push_back(i);
      if (vv.size() < 2) vv.push_back(pos);
      printf("%d %d\n", vv[0], vv[1]);
      vis[vv[0]] = vis[vv[1]] = 1;
      rs -= dep[pos];
      break;
    } else {
      vector<int> vv;
      for (auto &i : v[pos])
        if (!vis[i] && fa[pos] != i) vv.push_back(i);
      if (vv.size() < 2) vv.push_back(pos);
      printf("%d %d\n", vv[0], vv[1]);
      vis[vv[0]] = vis[vv[1]] = 1;
      rs -= dep[pos] * 2;
      del(vv[0]);
      del(vv[1]);
    }
    sz[cur] -= 2;
    if (sz[cur] > 1) r.insert({sz[cur], cur});
  }
  dfs3(rt);
  int tt = rem.size() / 2;
  for (int i = 0; i < tt; i++) printf("%d %d\n", rem[i], rem[i + tt]);
  return 0;
}