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;
using ll = long long;
inline ll read() {
  ll x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = (x << 1) + (x << 3) + ch - '0';
    ch = getchar();
  }
  return x * f;
}
const ll N = 1e5 + 10;
ll n, root, sz[N], c[N], f[N];
ll k, mn, mx;
struct edge {
  ll y, next;
} a[N * 2];
ll len, last[N];
inline void ins(ll x, ll y) {
  a[++len] = (edge){y, last[x]};
  last[x] = len;
}
inline void dfs(ll x, ll fa) {
  sz[x] = f[x] = 1;
  for (ll k = last[x], y; k; k = a[k].next)
    if ((y = a[k].y) ^ fa) {
      dfs(y, x);
      sz[x] += sz[y];
      f[x] = f[x] > sz[y] ? f[x] : sz[y];
      mn += sz[y] & 1;
      mx += min(sz[y], n - sz[y]);
    }
  f[x] = f[x] > n - sz[x] ? f[x] : n - sz[x];
}
inline void DFS(ll x, ll fa) {
  sz[x] = 1;
  for (ll 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]]++;
}
ll son[N], tot, A[N], B[N];
vector<ll> d[N];
inline void solve(ll x, ll fa) {
  sz[x] = 1;
  for (ll 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 (ll k = last[x], y; k; k = a[k].next)
    if ((y = a[k].y) ^ fa) son[++tot] = y;
  ll st = 1, ed = tot, tt = (sz[x] - c[x]) / 2;
  for (ll 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 (ll i = 1; i <= tt; i++) printf("%lld %lld\n", A[i], B[tt - i + 1]);
  for (ll i = st > 2 ? st : 2; i <= ed; i++) {
    if (d[son[i]].size() > d[x].size()) swap(d[son[i]], d[x]);
    for (ll j : d[son[i]]) d[x].push_back(j);
  }
}
int main() {
  n = read();
  k = read();
  for (ll i = 1, x, y; i < n; i++) {
    x = read();
    y = read();
    ins(x, y);
    ins(y, x);
  }
  dfs(1, 0);
  root = 1;
  for (ll 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);
  ll 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 (ll i = 1; i <= n; i++) c[i] = min(sz[i], p - (p + sz[i]) % 2);
  c[root] = 0;
  for (ll i = 1; i <= n; i++)
    if (c[i] == p && mx > k) {
      c[i] -= 2;
      mx -= 2;
    }
  puts("YES");
  solve(root, 0);
  return 0;
}