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;
int n;
long long k;
int x, y;
vector<int> v[100086];
int cur[100086];
int fa[100086], siz[100086], mn, id;
long long sum, par;
void dfs1(int i, int fa) {
  siz[i] = 1;
  int val = 0;
  for (int j = 0; j < v[i].size(); j++) {
    int to = v[i][j];
    if (to == fa) continue;
    dfs1(to, i);
    val = max(val, siz[to]), siz[i] += siz[to];
  }
  val = max(val, n - siz[i]);
  if (val < mn) mn = val, id = i;
}
void dfs2(int i) {
  siz[i] = 1;
  for (int j = 0; j < v[i].size(); j++) {
    int to = v[i][j];
    if (to == fa[i]) continue;
    fa[to] = i, dfs2(to);
    siz[i] += siz[to];
  }
  if (siz[i] ^ n) sum += siz[i], par += siz[i] & 1;
}
priority_queue<pair<int, int> > q;
set<pair<int, int> > st[100086];
int dep[100086], cnt[100086];
void dfs3(int i, int x) {
  dep[i] = dep[fa[i]] + 1;
  for (int j = 0; j < v[i].size(); j++) {
    int to = v[i][j];
    if (to == fa[i]) continue;
    cnt[i]++, dfs3(to, x);
  }
  if (cnt[i]) st[x].insert({dep[i], i});
}
bool vis[100086];
vector<int> a;
void dfs4(int i) {
  if (!vis[i]) a.push_back(i);
  for (int j = 0; j < v[i].size(); j++) {
    int to = v[i][j];
    if (to == fa[i]) continue;
    dfs4(to);
  }
}
int main() {
  scanf("%d%lld", &n, &k), mn = n;
  for (int i = 1; i < n; i++) {
    scanf("%d%d", &x, &y);
    v[x].push_back(y), v[y].push_back(x);
  }
  dfs1(1, 0);
  dfs2(id);
  if (k < par || k > sum || ((k - sum) & 1)) return printf("NO"), 0;
  for (int i = 0; i < v[id].size(); i++) {
    int to = v[id][i];
    if (siz[to] == 1) continue;
    q.push({siz[to], to});
    dfs3(to, to);
  }
  puts("YES");
  long long d = sum - k;
  while (d) {
    int x = q.top().second;
    q.pop();
    int y = st[x].rbegin()->second;
    if (d < 2 * dep[y]) {
      d >>= 1;
      y = st[x].lower_bound({(int)d, 0})->second;
      vector<int> a;
      for (int &i = cur[y]; i < v[y].size() && a.size() < 2; i++) {
        int to = v[y][i];
        if (to == fa[y] || vis[to]) continue;
        a.push_back(to);
      }
      if (a.size() < 2) a.push_back(y);
      printf("%d %d\n", a[0], a[1]), vis[a[0]] = vis[a[1]] = true;
      break;
    } else {
      d -= 2 * dep[y];
      vector<int> a;
      for (int &i = cur[y]; i < v[y].size() && a.size() < 2; i++) {
        int to = v[y][i];
        if (to == fa[y] || vis[to]) continue;
        a.push_back(to);
      }
      if (a.size() < 2) a.push_back(y);
      printf("%d %d\n", a[0], a[1]), vis[a[0]] = vis[a[1]] = true;
      if (fa[a[0]] != id && !--cnt[fa[a[0]]])
        st[x].erase({dep[fa[a[0]]], fa[a[0]]});
      if (fa[a[1]] != id && !--cnt[fa[a[1]]])
        st[x].erase({dep[fa[a[1]]], fa[a[1]]});
    }
    if (siz[x] -= 2) q.push({siz[x], x});
  }
  dfs4(id);
  for (int i = 0; i + a.size() / 2 < a.size(); i++) {
    printf("%d %d\n", a[i], a[i + a.size() / 2]);
  }
}