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 = 1e5 + 5, maxm = 2e5 + 5;
int head[maxn], nume;
struct edge {
  int v, w, c, next;
} e[maxm];
inline void init_edge() {
  memset(head, -1, sizeof head);
  nume = 0;
}
inline void add_edge(int u, int v, int w = 0, int c = 0) {
  e[nume].v = v;
  e[nume].w = w;
  e[nume].c = c;
  e[nume].next = head[u];
  head[u] = nume++;
}
int sz[maxn];
void dfs(int u, int f) {
  sz[u] = 1;
  for (int i = head[u]; ~i; i = e[i].next) {
    int v = e[i].v;
    if (v != f) {
      dfs(v, u);
      sz[u] += sz[v];
    }
  }
}
int s[maxn];
int dn[maxn], ed[maxn];
int DFS(int u, int f) {
  int g = 0;
  priority_queue<pair<int, int>, vector<pair<int, int> >,
                 less<pair<int, int> > >
      q;
  for (int i = head[u]; ~i; i = e[i].next) {
    int v = e[i].v;
    if (v != f) {
      int xx = DFS(v, u);
      int yy = s[v];
      if (s[v] > 0) {
        q.push(make_pair(yy, xx));
      }
      g += s[v];
    }
  }
  g++;
  ed[u] = u;
  q.push(make_pair(1, u));
  while (g > s[u]) {
    pair<int, int> p1, p2;
    p1 = q.top();
    q.pop();
    p2 = q.top();
    q.pop();
    printf("%d %d\n", p1.second, p2.second);
    if (p1.first > 1) {
      ed[dn[p1.second]] = ed[p1.second];
      p1.first--;
      p1.second = dn[p1.second];
      q.push(p1);
    }
    if (p2.first > 1) {
      ed[dn[p2.second]] = ed[p2.second];
      p2.first--;
      p2.second = dn[p2.second];
      q.push(p2);
    }
    g -= 2;
  }
  if (q.empty()) {
    return 0;
  } else {
    pair<int, int> pa = q.top();
    q.pop();
    int xx = pa.second;
    while (!q.empty()) {
      pair<int, int> pir = q.top();
      q.pop();
      dn[ed[xx]] = pir.second;
      ed[xx] = ed[pir.second];
    }
    return xx;
  }
}
int n;
int maxx[maxn];
long long k;
int main() {
  scanf("%d%lld", &n, &k);
  init_edge();
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    add_edge(u, v);
    add_edge(v, u);
  }
  dfs(1, 0);
  long long K = k, he = 0;
  for (int i = 2; i <= n; i++) {
    if (sz[i] & 1) {
      K--;
    }
    maxx[i] = min(sz[i], n - sz[i]) / 2;
    he += maxx[i] * 2;
  }
  if (K < 0 || K % 2 == 1 || K > he) {
    printf("NO");
    return 0;
  }
  K /= 2;
  printf("YES\n");
  int l = 0, r = n;
  while (l < r) {
    int m = l + r + 1 >> 1;
    long long sum = 0;
    for (int i = 2; i <= n; i++) {
      sum += min(m, maxx[i]);
    }
    if (sum < K)
      l = m;
    else
      r = m - 1;
  }
  for (int i = 2; i <= n; i++) {
    s[i] = min(l, maxx[i]);
    K -= s[i];
  }
  for (int i = 2; i <= n && K; i++) {
    if (s[i] < maxx[i] && (sz[i] & 1) == 0) {
      s[i]++;
      K--;
    }
  }
  for (int i = 2; i <= n && K; i++) {
    if (s[i] < maxx[i] && (sz[i] & 1) == 1) {
      s[i]++;
      K--;
    }
  }
  for (int i = 2; i <= n; i++) {
    s[i] = 2 * s[i] + (sz[i] & 1);
  }
  DFS(1, 0);
}