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 = 1e5 + 10;
int n, root, sz[N], c[N], f[N];
long long k, mn, mx;
struct edge {
  int y, next;
} a[N * 2];
int len, last[N];
void ins(int x, int y) {
  a[++len] = (edge){y, last[x]};
  last[x] = len;
}
void dfs(int x, int fa) {
  sz[x] = f[x] = 1;
  for (int k = last[x], y; k; k = a[k].next)
    if ((y = a[k].y) ^ fa)
      dfs(y, x), sz[x] += sz[y], f[x] = max(f[x], sz[y]), mn += sz[y] & 1,
                                 mx += min(sz[y], n - sz[y]);
  f[x] = max(f[x], n - sz[x]);
}
void DFS(int x, int fa) {
  sz[x] = 1;
  for (int k = last[x], y; k; k = a[k].next)
    if ((y = a[k].y) ^ fa) DFS(y, x), sz[x] += sz[y];
  c[sz[x]]++;
}
int son[N], tot, A[N], B[N];
vector<int> d[N];
void solve(int x, int fa) {
  sz[x] = 1;
  for (int k = last[x], y; k; k = a[k].next)
    if ((y = a[k].y) ^ fa) solve(y, x), sz[x] += c[y];
  son[tot = 1] = x;
  d[x].push_back(x);
  for (int k = last[x], y; k; k = a[k].next)
    if ((y = a[k].y) ^ fa) son[++tot] = y;
  int st = 1, ed = tot, tt = (sz[x] - c[x]) / 2;
  for (int i = 1; i <= tt; i++) {
    while (d[son[st]].empty()) st++;
    A[i] = d[son[st]].back();
    d[son[st]].pop_back();
    while (d[son[ed]].empty()) ed--;
    B[i] = d[son[ed]].back();
    d[son[ed]].pop_back();
  }
  for (int i = 1; i <= tt; i++) printf("%d %d\n", A[i], B[tt - i + 1]);
  for (int i = max(st, 2); i <= ed; i++) {
    if (d[son[i]].size() > d[x].size()) swap(d[son[i]], d[x]);
    for (int j : d[son[i]]) d[x].push_back(j);
  }
}
int main() {
  cin >> n >> k;
  for (int i = 1, x, y; i < n; i++) scanf("%d%d", &x, &y), ins(x, y), ins(y, x);
  dfs(1, 0);
  root = 1;
  for (int i = 2; i <= n; i++)
    if (f[i] < f[root]) root = i;
  if (!(mn <= k && k <= mx) || (k - mn) & 1) puts("NO"), exit(0);
  DFS(root, 0);
  int p = n - 1;
  for (; p > 1; p--)
    if (mx - 2 * c[p] >= k) {
      mx -= 2 * c[p];
      c[p - 2] += c[p];
    } else
      break;
  for (int i = 1; i <= n; i++) c[i] = min(sz[i], p - (p + sz[i]) % 2);
  c[root] = 0;
  for (int i = 1; i <= n; i++)
    if (c[i] == p && mx > k) {
      c[i] -= 2;
      mx -= 2;
    }
  puts("YES");
  solve(root, 0);
}