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 = 100010;
set<pair<int, int>, greater<pair<int, int>>> s[N], S;
set<pair<int, int>> pool;
vector<int> g[N];
int a[N], c[N], dfn[N], siz[N], n, l, tot;
long long k, r;
void modify(int x, int y) {
  for (; x <= n; x += x & (-x)) c[x] += y;
}
int get(int x) {
  int s = 0;
  for (; x; x -= x & (-x)) s += c[x];
  return s;
}
void dfs(int p, int fa) {
  siz[p] = 1;
  for (auto i : g[p])
    if (i != fa) dfs(i, p), siz[p] += siz[i];
}
int find(int p, int fa) {
  for (auto i : g[p])
    if (i != fa && siz[i] > n - siz[i]) return find(i, p);
  return p;
}
void work(int p, int fa, set<pair<int, int>, greater<pair<int, int>>>& s,
          int dep) {
  dfn[p] = ++tot;
  siz[p] = 1;
  s.insert(make_pair(dep, p));
  for (auto i : g[p])
    if (i != fa) work(i, p, s, dep + 1), siz[p] += siz[i];
  l += siz[p] & 1;
  r += siz[p];
}
int main() {
  scanf("%d%lld", &n, &k);
  for (int i = 1; i <= n - 1; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    g[x].push_back(y);
    g[y].push_back(x);
  }
  dfs(1, 0);
  int R = find(1, 0);
  for (auto i : g[R]) work(i, R, s[i], 1), S.insert(make_pair(siz[i], i));
  for (int i = 1; i <= n; i++)
    if (i != R) pool.insert(make_pair(dfn[i], i));
  if (k < l || k > r || (k & 1) != (r & 1)) {
    puts("NO");
    return 0;
  }
  puts("YES");
  for (; k < r;) {
    auto it = S.begin();
    int u = it->second, re = it->first;
    S.erase(it);
    S.insert(make_pair(re - 2, u));
    it = s[u].begin();
    int id = it->second, dep = it->first;
    for (;;) {
      if (r - dep * 2 >= k &&
          get(dfn[id] + siz[id] - 1) - get(dfn[id] - 1) + 2 <= siz[id])
        break;
      s[u].erase(it);
      it = s[u].begin();
      id = it->second;
      dep = it->first;
    }
    auto it2 = pool.lower_bound(make_pair(dfn[id], id));
    int x = it2->second;
    it2++;
    int y = it2->second;
    pool.erase(make_pair(dfn[x], x));
    pool.erase(make_pair(dfn[y], y));
    modify(dfn[x], 1);
    modify(dfn[y], 1);
    printf("%d %d\n", x, y);
    r -= 2 * dep;
  }
  int cnt = 1;
  a[1] = R;
  for (auto i : pool) a[++cnt] = i.second;
  for (int i = 1; i <= cnt / 2; i++) printf("%d %d\n", a[i], a[i + cnt / 2]);
  return 0;
}