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;
const int inf = 0x3f3f3f3f;
const int MAXN = 100005;
template <typename T>
void read(T &x) {
  T flag = 1;
  char ch = getchar();
  for (; '0' > ch || ch > '9'; ch = getchar())
    if (ch == '-') flag = -1;
  for (x = 0; '0' <= ch && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
  x *= flag;
}
struct node {
  int pre, to;
} edge[MAXN << 1];
int head[MAXN], tot = 1;
int n;
long long m;
int sz[MAXN], mn, rt;
int dep[MAXN];
set<pair<int, int> > s[MAXN];
int Fa[MAXN];
pair<int, int> ans[MAXN];
void add_edge(int u, int v) {
  tot++;
  edge[tot].pre = head[u];
  edge[tot].to = v;
  head[u] = tot;
}
void get_root(int x, int fa) {
  sz[x] = 1;
  int mx = 0;
  for (int i = head[x]; i; i = edge[i].pre) {
    int y = edge[i].to;
    if (y == fa) continue;
    get_root(y, x);
    sz[x] += sz[y];
    mx = max(mx, sz[y]);
  }
  mx = max(mx, n - sz[x]);
  if (mn > mx) {
    mn = mx;
    rt = x;
  }
}
long long sum;
void dfs(int x, int fa, int top) {
  s[top].insert(make_pair(dep[x], x));
  Fa[x] = fa;
  sz[x] = 1;
  sum += dep[x];
  for (int i = head[x]; i; i = edge[i].pre) {
    int y = edge[i].to;
    if (y == fa) continue;
    dep[y] = dep[x] + 1;
    dfs(y, x, top);
    sz[x] += sz[y];
  }
}
priority_queue<pair<int, int> > q;
int main() {
  read(n);
  read(m);
  for (int i = 1; i < n; i++) {
    int a, b;
    read(a);
    read(b);
    add_edge(a, b);
    add_edge(b, a);
  }
  mn = inf;
  get_root(1, 0);
  for (int i = head[rt]; i; i = edge[i].pre) {
    int y = edge[i].to;
    dep[y] = 1;
    dfs(y, rt, y);
  }
  sum -= m;
  if (sum < 0 || sum % 2) {
    puts("NO");
    return 0;
  };
  m = sum >> 1;
  for (int i = head[rt]; i; i = edge[i].pre) {
    int y = edge[i].to;
    q.push(make_pair(sz[y], y));
  }
  int top = 0;
  while (m) {
    int x = q.top().second;
    q.pop();
    if (sz[x] <= 1) break;
    set<pair<int, int> >::iterator it = s[x].end();
    sz[x] -= 2;
    if (sz[x]) q.push(make_pair(sz[x], x));
    if ((*--it).first > m + 1) {
      it = s[x].lower_bound(make_pair(m, 0));
      bool flag = false;
      while ((*it).first == m) {
        int y = (*it).second;
        for (int i = head[y]; i; i = edge[i].pre) {
          int z = edge[i].to;
          if (z == Fa[y] || s[x].find(make_pair(dep[z], z)) == s[x].end())
            continue;
          s[x].erase(make_pair(dep[y], y));
          s[x].erase(make_pair(dep[z], z));
          ans[++top] = make_pair(y, z);
          flag = true;
          break;
        }
        if (flag) break;
        it++;
      }
      m = 0;
    } else {
      m -= (*it).first - 1;
      int y = (*it).second;
      int z = Fa[y];
      bool flag = false;
      for (int i = head[z]; i; i = edge[i].pre) {
        int w = edge[i].to;
        if (w == Fa[z] || w == y ||
            s[x].find(make_pair(dep[w], w)) == s[x].end())
          continue;
        flag = true;
        ans[++top] = make_pair(y, w);
        s[x].erase(make_pair(dep[w], w));
        s[x].erase(make_pair(dep[y], y));
        break;
      }
      if (!flag) {
        s[x].erase(make_pair(dep[z], z));
        s[x].erase(make_pair(dep[y], y));
        ans[++top] = make_pair(y, z);
      }
    }
  }
  while (!q.empty()) {
    int x = q.top().second;
    q.pop();
    if (q.empty()) {
      ans[++top] = make_pair((*s[x].begin()).second, rt);
      break;
    }
    int y = q.top().second;
    q.pop();
    sz[x]--;
    sz[y]--;
    ans[++top] = make_pair((*s[x].begin()).second, (*s[y].begin()).second);
    s[x].erase(s[x].begin());
    s[y].erase(s[y].begin());
    if (sz[x]) q.push(make_pair(sz[x], x));
    if (sz[y]) q.push(make_pair(sz[y], y));
  }
  puts("YES");
  for (int i = 1; i <= n / 2; i++) {
    printf("%d %d\n", ans[i].first, ans[i].second);
  }
  return 0;
}