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;
int n;
long long K;
vector<int> E[200000 + 5];
void addEdge(int u, int v) {
  E[u].push_back(v);
  E[v].push_back(u);
}
int sz[200000 + 5], deep[200000 + 5], fa[200000 + 5];
int msz[200000 + 5], root;
void dfs1(int x, int f) {
  sz[x] = 1;
  msz[x] = 0;
  for (int y : E[x]) {
    if (y != f) {
      dfs1(y, x);
      sz[x] += sz[y];
      msz[x] = max(msz[x], sz[y]);
    }
  }
  msz[x] = max(msz[x], n - sz[x]);
  if (root == 0 || msz[x] < msz[root]) root = x;
}
set<pair<int, int> > S[200000 + 5];
long long minans = 0, maxans = 0;
int sons[200000 + 5];
void dfs2(int x, int f, int rt) {
  sz[x] = 1;
  fa[x] = f;
  deep[x] = deep[f] + 1;
  for (int y : E[x]) {
    if (y != f) {
      sons[x]++;
      dfs2(y, x, rt);
      sz[x] += sz[y];
    }
  }
  if (sz[x] > 1) S[rt].insert(make_pair(deep[x], x));
  minans += sz[x] % 2;
  maxans += sz[x];
}
bool vis[200000 + 5];
int getSon(int x) {
  for (int t : E[x]) {
    if (t != fa[x] && !vis[t]) {
      vis[t] = 1;
      return t;
    }
  }
  return x;
}
void del(int x, int rt) {
  vis[x] = 1;
  sons[fa[x]]--;
  if (sons[fa[x]] == 0) S[rt].erase(make_pair(deep[fa[x]], fa[x]));
}
priority_queue<pair<int, int> > q;
vector<int> ans;
void dfs3(int x) {
  if (!vis[x]) ans.push_back(x);
  for (int y : E[x])
    if (y != fa[x]) dfs3(y);
}
int main() {
  scanf("%d %lld", &n, &K);
  for (int i = 1, u, v; i < n; i++) {
    scanf("%d %d", &u, &v);
    addEdge(u, v);
  }
  dfs1(1, 0);
  for (int y : E[root]) {
    dfs2(y, root, y);
    q.push(make_pair(sz[y], y));
  }
  if (K >= minans && K <= maxans && (maxans - K) % 2 == 0) {
    puts("YES");
    K = (maxans - K) / 2;
    while (K) {
      int rt = q.top().second;
      q.pop();
      int lc = S[rt].rbegin()->second;
      int d = deep[lc];
      if (K >= d) {
        K -= d;
        int u = getSon(lc), v = getSon(lc);
        del(u, rt);
        del(v, rt);
        printf("%d %d\n", u, v);
      } else {
        int u = S[rt].lower_bound(make_pair(K, 0))->second;
        int v = getSon(u);
        del(u, rt);
        del(v, rt);
        printf("%d %d\n", u, v);
        break;
      }
      sz[rt] -= 2;
      if (sz[rt] > 1) q.push(make_pair(sz[rt], rt));
    }
    dfs3(root);
    for (int i = 0; i < (int)ans.size() / 2; i++)
      printf("%d %d\n", ans[i], ans[i + (int)ans.size() / 2]);
  } else
    puts("NO");
}