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;
char _buf[100000], *_op(_buf), *_ed(_buf);
inline int getint() {
  int _s = 0;
  char _ch = (_op == _ed && (_ed = (_op = _buf) + fread(_buf, 1, 100000, stdin),
                             _op == _ed)
                  ? EOF
                  : *_op++);
  while (!('0' <= _ch && _ch <= '9'))
    _ch = (_op == _ed && (_ed = (_op = _buf) + fread(_buf, 1, 100000, stdin),
                          _op == _ed)
               ? EOF
               : *_op++);
  while (('0' <= _ch && _ch <= '9'))
    _s = _s * 10 + _ch - 48,
    _ch = (_op == _ed && (_ed = (_op = _buf) + fread(_buf, 1, 100000, stdin),
                          _op == _ed)
               ? EOF
               : *_op++);
  return _s;
}
const int N = 2e5 + 1, INF = 0x3f3f3f3f;
inline void cmax(int& x, int y) {
  if (x - y >> 31) x = y;
}
long long int k, lim;
set<pair<int, int> > mp;
vector<int> e[N];
int T, n, rt, now, tot, cnt, minn, flag, id[N];
int dep[N], val[N], siz[N], vis[N], tmp[N];
struct node {
  int x, y, w;
  inline int operator<(const node& u) const { return w < u.w; }
};
vector<node> t[N];
inline void add_edge(int x, int y) { e[x].push_back(y), e[y].push_back(x); }
inline void input() {
  cin >> n >> k, cnt = n >> 1;
  for (int i = 2; i <= n; i++) add_edge(getint(), getint());
}
inline void getrt(int u, int fa = 0) {
  int maxn(siz[u] = 1);
  for (int v : e[u])
    if (v != fa) getrt(v, u), cmax(maxn, siz[v]), siz[u] += siz[v];
  if (cmax(maxn, n - siz[u]), maxn < minn) minn = maxn, rt = u;
}
inline void init(int u, int fa) {
  siz[u] = 1, val[u] = u, lim += dep[u] = dep[fa] + 1, minn++, id[u] = now;
  for (int v : e[u])
    if (v != fa && (init(v, u), siz[u] += siz[v], val[v])) {
      if (!val[u])
        val[u] = val[v], minn++;
      else
        t[now].push_back((node){val[u], val[v], dep[u] << 1}), val[u] = 0,
                                                               minn--;
    }
}
inline void init() {
  minn = INF, getrt(1), minn = 0;
  for (int v : e[rt])
    init(now = v, rt), sort(t[v].begin(), t[v].end()),
        mp.insert(pair<int, int>(siz[v], v));
}
inline void solve(int x, int y) {
  k -= dep[x] + dep[y], lim -= dep[x] + dep[y], vis[x] = vis[y] = 1, cnt--,
                                                cout << x << ' ' << y << '\n';
}
inline void solve(const node& u) { k += u.w, solve(u.x, u.y); }
inline void find(int u, int w, int fa) {
  val[u] = !vis[u] * u;
  for (int v : e[u])
    if (v != fa && (find(v, w, u), val[v])) {
      if (!val[u])
        val[u] = val[v];
      else if (flag && dep[u] == w)
        solve(val[u], val[v]), k += w << 1, flag = 0;
    }
}
inline void dfs(int u, int fa = 0) {
  if (!vis[u]) tmp[++tot] = u;
  for (int v : e[u])
    if (v != fa) dfs(v, u);
}
inline void work() {
  if (lim < k || k < minn || (k - lim & 1)) return void(cout << "NO\n");
  cout << "YES\n", flag = 1;
  for (int u; lim != k;) {
    u = (*--mp.end()).second, mp.erase(pair<int, int>(siz[u], u)),
    mp.insert(pair<int, int>(siz[u] -= 2, u));
    if (lim - t[u].back().w >= k)
      solve(t[u].back()), t[u].pop_back();
    else
      find(u, lim - k >> 1, rt);
  }
  dfs(rt), tot >>= 1;
  for (int i = 1; i <= tot; i++) solve(tmp[i], tmp[i + tot]);
}
int main() {
  input();
  init();
  work();
  return 0;
}