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;
long long fa[100005], siz[100005], w[100005], dep[100005], rt;
vector<long long> edge[100005], fk[100005];
set<pair<long long, long long> > S[100005];
set<long long> Edg[100005];
long long n, k, Minans, Maxans;
void dfs1(long long first, long long fa) {
  siz[first] = 1;
  for (long long i = 0; i < edge[first].size(); ++i) {
    long long v = edge[first][i];
    if (v == fa) continue;
    dfs1(v, first);
    siz[first] += siz[v];
    if (siz[v] > siz[w[first]]) w[first] = v;
  }
  if (max(siz[w[first]], n - siz[first]) <= n / 2) rt = first;
}
void dfs2(long long first, long long F) {
  siz[first] = 1;
  for (long long i = 0; i < edge[first].size(); ++i) {
    long long v = edge[first][i];
    if (v == F) continue;
    fa[v] = first;
    Edg[first].insert(edge[first][i]);
    dep[v] = dep[first] + 1;
    dfs2(v, first);
    siz[first] += siz[v];
    Maxans += siz[v];
    Minans += (siz[v] & 1);
  }
}
void dfs3(long long first, long long t) {
  if (Edg[first].size()) S[t].insert(make_pair(dep[first], first));
  for (set<long long>::iterator it = Edg[first].begin(); it != Edg[first].end();
       ++it) {
    dfs3(*it, t);
  }
}
long long vis[100005];
void dfs4(long long first, long long t) {
  if (!vis[first]) fk[t].push_back(first);
  for (long long i = 0; i < edge[first].size(); ++i)
    if (fa[first] != edge[first][i]) dfs4(edge[first][i], t);
}
void maintain(long long first, long long t) {
  if (!Edg[first].size()) S[t].erase(make_pair(dep[first], first));
}
priority_queue<pair<long long, long long> > Q;
signed main() {
  scanf("%lld%lld", &n, &k);
  for (long long i = 1; i < n; ++i) {
    long long u, v;
    scanf("%lld%lld", &u, &v);
    edge[u].push_back(v);
    edge[v].push_back(u);
  }
  dfs1(1, 0);
  dep[rt] = 0;
  dfs2(rt, 0);
  if (!(Minans <= k && k <= Maxans && k % 2 == Maxans % 2)) {
    puts("NO");
    return 0;
  }
  puts("YES");
  long long rst = (Maxans - k) / 2;
  for (long long i = 0; i < edge[rt].size(); ++i) {
    dfs3(edge[rt][i], edge[rt][i]);
    if (siz[edge[rt][i]]) Q.push(make_pair(siz[edge[rt][i]], edge[rt][i]));
  }
  while (rst) {
    long long first = Q.top().second;
    Q.pop();
    siz[first] -= 2;
    long long a = (*--S[first].end()).second;
    while (dep[a] > rst) {
      S[first].erase(--S[first].end());
      a = (*--S[first].end()).second;
    }
    if (Edg[a].size() > 1) {
      long long X = (*Edg[a].begin());
      Edg[a].erase(Edg[a].begin());
      long long Y = (*Edg[a].begin());
      Edg[a].erase(Edg[a].begin());
      printf("%lld %lld\n", X, Y);
      vis[X] = vis[Y] = 1;
      maintain(a, first);
    } else {
      long long X = (*Edg[a].begin());
      Edg[a].erase(Edg[a].begin());
      vis[a] = vis[X] = 1;
      printf("%lld %lld\n", a, X);
      S[first].erase(make_pair(dep[a], a));
      long long p = fa[a];
      Edg[p].erase(a);
      maintain(p, first);
    }
    rst -= dep[a];
    if (siz[first]) Q.push(make_pair(siz[first], first));
  }
  for (long long i = 0; i < edge[rt].size(); ++i)
    dfs4(edge[rt][i], edge[rt][i]);
  while (1) {
    long long first = Q.top().second;
    Q.pop();
    siz[first]--;
    if (Q.empty()) {
      printf("%lld %lld\n", rt, fk[first].back());
      return 0;
    }
    long long second = Q.top().second;
    Q.pop();
    siz[second]--;
    printf("%lld %lld\n", fk[first].back(), fk[second].back());
    fk[first].pop_back();
    fk[second].pop_back();
    if (siz[first]) Q.push(make_pair(siz[first], first));
    if (siz[second]) Q.push(make_pair(siz[second], second));
  }
  return 0;
}