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;
inline long long read() {
  long long f = 1, x = 0;
  char s = getchar();
  while (s < '0' || s > '9') {
    if (s == '-') f = -1;
    s = getchar();
  }
  while (s >= '0' && s <= '9') {
    x = x * 10 + s - 48;
    s = getchar();
  }
  return f * x;
}
const int N = 2e5 + 5;
struct Graph {
  int tot, next[N], to[N], head[N], out[N];
  inline void add(int a, int b) {
    to[++tot] = b;
    next[tot] = head[a];
    head[a] = tot;
    out[a]++;
  }
  inline void link(int a, int b) {
    add(a, b);
    add(b, a);
  }
} T;
int size[N], n, top[N], root, fa[N], d[N], deg[N];
long long maxv, minv, k;
void dfs(int u, int fa) {
  size[u] = 1;
  int maxs = 0;
  for (int i = T.head[u]; i; i = T.next[i]) {
    int v = T.to[i];
    if (v == fa) continue;
    dfs(v, u);
    size[u] += size[v];
    maxv += min(size[v], n - size[v]);
    if (size[v] & 1) minv++;
    maxs = max(maxs, size[v]);
  }
  if (maxs <= (n >> 1) && (n - size[u]) <= (n >> 1)) root = u;
}
set<pair<int, int> > S[N], R;
void dfs2(int u, int from) {
  size[u] = 1;
  top[u] = from;
  if (from && (int)T.out[u] >= 2) S[from].insert(make_pair(d[u], u));
  for (int i = T.head[u]; i; i = T.next[i]) {
    int v = T.to[i];
    if (v == fa[u]) continue;
    if (u == root) from = v;
    deg[u]++;
    d[v] = d[u] + 1;
    fa[v] = u;
    dfs2(v, from);
    size[u] += size[v];
  }
}
int vis[N];
vector<int> rem;
void dfs3(int u) {
  if (!vis[u]) rem.push_back(u);
  for (int i = T.head[u]; i; i = T.next[i]) {
    int v = T.to[i];
    if (v == fa[u]) continue;
    dfs3(v);
  }
}
void del(int x) {
  if (!--deg[fa[x]]) S[top[x]].erase(make_pair(d[fa[x]], fa[x]));
}
int main() {
  n = read(), k = read();
  for (int i = 1; i < n; i++) {
    int a = read(), b = read();
    T.link(a, b);
  }
  dfs(1, 0);
  if (k > maxv || k < minv || (maxv - k) & 1) {
    puts("NO");
    return 0;
  }
  puts("YES");
  dfs2(root, 0);
  for (int i = T.head[root]; i; i = T.next[i]) {
    int v = T.to[i];
    if (size[v] > 1) R.insert(make_pair(size[v], v));
  }
  long long rest = maxv - k;
  while (rest) {
    int now = R.rbegin()->second;
    R.erase(--R.end());
    int pos = S[now].rbegin()->second;
    if (2 * d[pos] > rest) {
      rest /= 2;
      pos = S[now].lower_bound(make_pair(rest, 0))->second;
      vector<int> V;
      V.clear();
      for (int i = T.head[pos]; i; i = T.next[i]) {
        int v = T.to[i];
        if (v == fa[pos] || vis[v]) continue;
        V.push_back(v);
      }
      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 -= d[pos];
      break;
    } else {
      vector<int> V;
      V.clear();
      for (int i = T.head[pos]; i; i = T.next[i]) {
        int v = T.to[i];
        if (v == fa[pos] || vis[v]) continue;
        V.push_back(v);
      }
      if ((int)V.size() < 2) V.push_back(pos);
      rest -= d[pos] * 2;
      printf("%d %d\n", V[0], V[1]);
      vis[V[0]] = 1;
      vis[V[1]] = 1;
      del(V[0]);
      del(V[1]);
    }
    size[now] -= 2;
    if (size[now] > 1) R.insert(make_pair(size[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;
}