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 N = 100005;
int n, fa[N], id[N];
int f[N], sz[N], tab[N];
vector<int> e[N];
set<int> S[N];
long long k, lo, hi;
void dfs(int x) {
  sz[x] = 1;
  for (auto i : e[x])
    if (i != fa[x]) {
      fa[i] = x;
      dfs(i);
      sz[x] += sz[i];
      f[i] = min(sz[i], n - sz[i]);
      lo += sz[i] & 1;
      hi += f[i];
    }
}
int q[N], q1[N], q2[N];
void merge(int &x, int &y) {
  if (S[x].size() < S[y].size()) swap(x, y);
  for (auto i : S[y]) S[x].insert(i);
}
void dfs2(int x) {
  for (auto i : e[x])
    if (i != fa[x]) dfs2(i);
  q[0] = 1;
  q[1] = x;
  int sz = 1;
  id[x] = x;
  S[x].insert(x);
  for (auto i : e[x])
    if (i != fa[x]) q[++*q] = i, sz += f[i];
  int ned = (sz - f[x]) / 2;
  int p1 = 1, p2 = *q;
  for (int j = (int)(1); j <= (int)(ned); j++) {
    for (; !S[id[q[p1]]].size(); ++p1)
      ;
    q1[j] = *S[id[q[p1]]].begin();
    S[id[q[p1]]].erase(q1[j]);
    for (; !S[id[q[p2]]].size(); --p2)
      ;
    q2[j] = *S[id[q[p2]]].begin();
    S[id[q[p2]]].erase(q2[j]);
  }
  for (auto i : e[x])
    if (i != fa[x]) merge(id[x], id[i]);
  for (int j = (int)(1); j <= (int)(ned); j++)
    printf("%d %d\n", q1[j], q2[ned - j + 1]);
}
int main() {
  scanf("%d%lld", &n, &k);
  for (int i = (int)(1); i <= (int)(n - 1); i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    e[x].push_back(y);
    e[y].push_back(x);
  }
  dfs(1);
  if (k < lo || k > hi || (k + lo) % 2) return puts("NO"), 0;
  puts("YES");
  for (int i = (int)(2); i <= (int)(n); i++) ++tab[f[i]];
  int p = n;
  for (; p >= 2; --p)
    if (hi - 2 * tab[p] >= k) {
      tab[p - 2] += tab[p];
      hi -= 2 * tab[p];
    } else
      break;
  for (int i = (int)(2); i <= (int)(n); i++)
    f[i] = min(f[i], p - (p + f[i]) % 2);
  for (int i = (int)(2); i <= (int)(n); i++)
    if (f[i] == p && hi > k) hi -= 2, f[i] -= 2;
  dfs2(1);
}