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;
template <typename T>
inline void read(T &num) {
  T x = 0, f = 1;
  char ch = getchar();
  for (; ch > '9' || ch < '0'; ch = getchar())
    if (ch == '-') f = -1;
  for (; ch <= '9' && ch >= '0'; ch = getchar())
    x = (x << 3) + (x << 1) + (ch ^ '0');
  num = x * f;
}
int n, rt, head[200005], pre[200005 << 1], to[200005 << 1], sz;
int siz[200005], fa[200005], dep[200005], vis[200005], son[200005], top[200005];
long long k, mn, mx;
priority_queue<pair<int, int> > q;
set<pair<int, int> > s[200005];
vector<int> tmp;
inline void addedge(int u, int v) {
  pre[++sz] = head[u];
  head[u] = sz;
  to[sz] = v;
  pre[++sz] = head[v];
  head[v] = sz;
  to[sz] = u;
}
void findrt(int x, int Fa) {
  siz[x] = 1;
  int M = 0;
  for (int i = head[x]; i; i = pre[i]) {
    int y = to[i];
    if (y == Fa) continue;
    findrt(y, x);
    siz[x] += siz[y];
    M = max(M, siz[y]);
  }
  M = max(M, n - siz[x]);
  if (M < mn) mn = M, rt = x;
}
void dfs1(int x, int Rt) {
  siz[x] = 1;
  if (fa[x] == rt) Rt = x;
  for (int i = head[x]; i; i = pre[i]) {
    int y = to[i];
    if (y == fa[x]) continue;
    fa[y] = x;
    dep[y] = dep[x] + 1;
    son[x]++;
    dfs1(y, Rt);
    siz[x] += siz[y];
  }
  if (x != rt) mn += siz[x] % 2, mx += siz[x];
  if (fa[x] == rt && siz[x] > 1) q.push(make_pair(siz[x], x));
  if (Rt && son[x]) s[Rt].insert(make_pair(dep[x], x)), top[x] = Rt;
}
inline void del(int x) {
  if (!(--son[fa[x]])) s[top[fa[x]]].erase(make_pair(dep[fa[x]], fa[x]));
}
void dfs2(int x) {
  if (!vis[x]) tmp.push_back(x);
  for (int i = head[x]; i; i = pre[i]) {
    int y = to[i];
    if (y == fa[x]) continue;
    dfs2(y);
  }
}
int main() {
  read(n);
  read(k);
  for (int i = 1, u, v; i < n; i++) {
    read(u);
    read(v);
    addedge(u, v);
  }
  mn = 0x3f3f3f3f;
  findrt(1, 0);
  mn = mx = 0;
  dfs1(rt, 0);
  if (mn > k || mx < k || (mx - k) & 1) {
    puts("NO");
    return 0;
  }
  puts("YES");
  k = (mx - k) >> 1;
  while (k) {
    int Rt = q.top().second;
    q.pop();
    int x = s[Rt].rbegin()->second;
    if (dep[x] > k) x = s[Rt].lower_bound(make_pair(k, 0))->second;
    tmp.clear();
    for (int i = head[x]; i; i = pre[i]) {
      int y = to[i];
      if (y == fa[x] || vis[y]) continue;
      tmp.push_back(y);
    }
    if (tmp.size() < 2) tmp.push_back(x);
    printf("%d %d\n", tmp[0], tmp[1]);
    vis[tmp[0]] = vis[tmp[1]] = 1;
    del(tmp[0]);
    del(tmp[1]);
    siz[Rt] -= 2;
    k -= dep[x];
    if (siz[Rt] > 1) q.push(make_pair(siz[Rt], Rt));
    if (!k) break;
  }
  tmp.clear();
  dfs2(rt);
  for (int i = 0; i < tmp.size() / 2; i++)
    printf("%d %d\n", tmp[i], tmp[i + tmp.size() / 2]);
  return 0;
}