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 Maxn = 100000;
int n;
long long k;
int head[Maxn + 5], arrive[Maxn << 1 | 5], nxt[Maxn << 1 | 5], tot;
void add_edge(int from, int to) {
  arrive[++tot] = to;
  nxt[tot] = head[from];
  head[from] = tot;
}
int sz[Maxn + 5];
int val[Maxn + 5];
void init_dfs(int u, int fa) {
  sz[u] = 1;
  for (int i = head[u]; i; i = nxt[i]) {
    int v = arrive[i];
    if (v == fa) {
      continue;
    }
    init_dfs(v, u);
    sz[u] += sz[v];
  }
}
list<int> work_dfs(int u, int fa) {
  list<int> all;
  all.push_back(u);
  for (int i = head[u]; i; i = nxt[i]) {
    int v = arrive[i];
    if (v == fa) {
      continue;
    }
    all.splice(all.end(), work_dfs(v, u));
  }
  int cnt = ((int)all.size() - val[u]) >> 1;
  vector<pair<int, int> > pairs(cnt);
  for (int i = 0; i < cnt; i++) {
    pairs[i].first = all.front();
    pairs[cnt - i - 1].second = all.back();
    all.pop_front();
    all.pop_back();
  }
  for (int i = 0; i < cnt; i++) {
    printf("%d %d\n", pairs[i].first, pairs[i].second);
  }
  return all;
}
int main() {
  scanf("%d%lld", &n, &k);
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    add_edge(u, v);
    add_edge(v, u);
  }
  init_dfs(1, 0);
  long long minn = 0, maxn = 0;
  for (int i = 2; i <= n; i++) {
    val[i] = min(sz[i], n - sz[i]);
    minn += (val[i] & 1);
    maxn += val[i];
  }
  if (k < minn || k > maxn || (k & 1) != (minn & 1)) {
    puts("NO");
    return 0;
  }
  puts("YES");
  int left = 0, right = (n >> 1);
  long long cost = -1;
  while (left <= right) {
    int mid = (left + right) >> 1;
    long long ans = 0;
    for (int i = 2; i <= n; i++) {
      if (val[i] <= mid) {
        ans += val[i];
      } else {
        ans += mid - ((val[i] & 1) != (mid & 1));
      }
    }
    if (ans >= k) {
      right = mid - 1;
      cost = ans;
    } else {
      left = mid + 1;
    }
  }
  for (int i = 2; i <= n; i++) {
    if (val[i] > left) {
      val[i] = left - ((val[i] & 1) != (left & 1));
    }
    if (val[i] == left && cost > k) {
      val[i] -= 2;
      cost -= 2;
    }
  }
  work_dfs(1, 0);
  return 0;
}