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>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
template <typename T1, typename T2>
void ckmin(T1 &a, T2 b) {
  if (a > b) a = b;
}
template <typename T1, typename T2>
void ckmax(T1 &a, T2 b) {
  if (a < b) a = b;
}
template <typename T>
T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
}
int read() {
  int x = 0, f = 0;
  char ch = getchar();
  while (!isdigit(ch)) f |= ch == '-', ch = getchar();
  while (isdigit(ch)) x = 10 * x + ch - '0', ch = getchar();
  return f ? -x : x;
}
const int N = 120000;
int n;
long long k;
vector<int> v[N];
int sz[N], dep[N], fa[N], root;
long long minn = N, maxn = 0;
void dfs1(int u, int f) {
  sz[u] = 1;
  int maxsz = 0;
  for (int i = 0; i < (int)v[u].size(); i++) {
    int to = v[u][i];
    if (to == f) continue;
    dfs1(to, u);
    sz[u] += sz[to];
    maxsz = max(maxsz, sz[to]);
  }
  if (minn > max(maxsz, n - sz[u])) minn = max(maxsz, n - sz[u]), root = u;
}
int top[N], deg[N];
set<pair<int, int> > S[N], R;
void dfs(int u, int from) {
  sz[u] = 1;
  top[u] = from;
  if (from && (int)v[u].size() - 1 >= 1) S[from].insert(make_pair(dep[u], u));
  for (int i = 0; i < (int)v[u].size(); i++) {
    int to = v[u][i];
    if (to == fa[u]) continue;
    if (u == root) from = to;
    deg[u]++;
    dep[to] = dep[u] + 1;
    fa[to] = u;
    dfs(to, from);
    sz[u] += sz[to];
  }
}
void del(int x) {
  if (!--deg[fa[x]]) S[top[x]].erase(make_pair(dep[fa[x]], fa[x]));
}
int vis[N];
vector<int> rem;
void dfs3(int u) {
  if (!vis[u]) rem.push_back(u);
  for (int i = 0; i < (int)v[u].size(); i++) {
    int to = v[u][i];
    if (to == fa[u]) continue;
    dfs3(to);
  }
}
int main() {
  scanf("%d%lld", &n, &k);
  for (int i = 1; i < n; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    v[x].push_back(y);
    v[y].push_back(x);
  }
  dfs1(1, -1);
  dep[root] = 0;
  dfs(root, 0);
  minn = 0, maxn = 0;
  for (int i = 1; i <= n; i++)
    if (i != root) maxn += sz[i], minn += sz[i] % 2;
  if (k > maxn || k < minn || (maxn - k) & 1) {
    puts("NO");
    return 0;
  }
  puts("YES");
  for (int i = 0; i < v[root].size(); i++) {
    int to = v[root][i];
    if (sz[to] > 1) R.insert(make_pair(sz[to], to));
  }
  long long rest = maxn - k;
  while (rest) {
    int now = R.rbegin()->second;
    R.erase(--R.end());
    int pos = S[now].rbegin()->second;
    if (2 * dep[pos] > rest) {
      rest /= 2;
      pos = S[now].lower_bound(make_pair(rest, 0))->second;
      vector<int> V;
      V.clear();
      for (int i = 0; i < (int)v[pos].size(); i++) {
        int to = v[pos][i];
        if (to == fa[pos] || vis[to]) continue;
        V.push_back(to);
      }
      if ((int)V.size() < 2) V.push_back(pos);
      printf("%d %d\n", V[0], V[1]);
      vis[V[0]] = 1;
      vis[V[1]] = 1;
      rest -= dep[pos];
      break;
    } else {
      vector<int> V;
      V.clear();
      for (int i = 0; i < (int)v[pos].size(); i++) {
        int to = v[pos][i];
        if (to == fa[pos] || vis[to]) continue;
        V.push_back(to);
      }
      if ((int)V.size() < 2) V.push_back(pos);
      rest -= dep[pos] * 2;
      printf("%d %d\n", V[0], V[1]);
      vis[V[0]] = 1;
      vis[V[1]] = 1;
      del(V[0]);
      del(V[1]);
    }
    sz[now] -= 2;
    if (sz[now] > 1) R.insert(make_pair(sz[now], now));
  }
  dfs3(root);
  int T = (int)rem.size() / 2;
  for (int i = 0; i < T; i++) printf("%d %d\n", rem[i], rem[i + T]);
  return 0;
}