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 maxn = 100009;
int n;
long long K;
vector<int> G[maxn];
int siz[maxn], g[maxn];
int getroot(int x, int fa) {
  siz[x] = 1;
  int c = 0;
  for (int i = 0; i < G[x].size(); ++i) {
    int v = G[x][i];
    if (v == fa) continue;
    int vc = getroot(v, x);
    if (!c || g[vc] < g[c]) c = vc;
    siz[x] += siz[v];
    g[x] = max(g[x], siz[v]);
  }
  g[x] = max(g[x], n - siz[x]);
  if (!c || g[x] < g[c]) c = x;
  return c;
}
vector<int> son[maxn];
int dep[maxn];
int father[maxn];
void dp0(int x, int fa) {
  siz[x] = 1;
  dep[x] = dep[fa] + 1;
  father[x] = fa;
  for (int i = 0; i < G[x].size(); ++i) {
    int v = G[x][i];
    if (v == fa) continue;
    dp0(v, x);
    son[x].push_back(v);
    siz[x] += siz[v];
  }
}
long long CurrentK;
struct Point {
  int x, siz;
  Point(int _x, int _siz) {
    x = _x;
    siz = _siz;
  }
  bool operator<(const Point &rhs) const { return siz < rhs.siz; }
};
priority_queue<Point> q;
struct Node {
  int x, d;
  Node(int _x, int _d) {
    x = _x;
    d = _d;
  }
  bool operator<(const Node &rhs) const { return d < rhs.d; }
};
priority_queue<Node> S[maxn];
int del[maxn];
vector<pair<int, int>> ans;
void dfs1(int x, int subroot) {
  if (!del[x]) S[subroot].push(Node(x, dep[x]));
  for (int i = 0; i < G[x].size(); ++i) {
    int v = G[x][i];
    if (v == father[x]) continue;
    dfs1(v, subroot);
  }
}
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);
  }
  int root = getroot(1, 0);
  dp0(root, 0);
  int low = 0;
  for (int i = 1; i <= n; ++i) {
    if (i != root) {
      CurrentK += siz[i];
      low += siz[i] % 2;
    }
  }
  if (low > K || CurrentK < K || (CurrentK - K) % 2) {
    printf("NO\n");
    return 0;
  }
  for (int i = 0; i < G[root].size(); ++i) {
    int v = G[root][i];
    q.push(Point(v, siz[v]));
    dfs1(v, v);
  }
  while (CurrentK != K) {
    int mxd = min((CurrentK - K) / 2, 1LL * n);
    int v = q.top().x;
    q.pop();
    siz[v] -= 2;
    q.push(Point(v, siz[v]));
    for (;;) {
      int x = S[v].top().x;
      S[v].pop();
      int a = 0, b = 0;
      while (son[x].size()) {
        int t = son[x].back();
        son[x].pop_back();
        if (del[t]) continue;
        a = t;
        break;
      }
      while (son[x].size()) {
        int t = son[x].back();
        son[x].pop_back();
        if (del[t]) continue;
        b = t;
        break;
      }
      if (!a && !b) continue;
      if (dep[x] - 1 >= mxd) {
        b = x;
        while (dep[b] - 1 > mxd) b = father[b];
        ans.push_back({a, b});
        del[a] = del[b] = 1;
        CurrentK = K;
        break;
      }
      if (a && b) {
        ans.push_back({a, b});
        del[a] = del[b] = 1;
        CurrentK -= 2 * (dep[x] - 1);
        S[v].push(Node(x, dep[x]));
        break;
      } else {
        ans.push_back({x, a});
        del[x] = del[a] = 1;
        CurrentK -= 2 * (dep[x] - 1);
        break;
      }
    }
  }
  for (int i = 0; i < G[root].size(); ++i) {
    int v = G[root][i];
    while (S[v].size()) S[v].pop();
    dfs1(v, v);
  }
  while (ans.size() < n / 2) {
    int x = q.top().x;
    q.pop();
    int y = (q.size()) ? q.top().x : 0;
    if (q.size()) q.pop();
    if (!y || !siz[y]) {
      ans.push_back({root, S[x].top().x});
      break;
    }
    --siz[x];
    --siz[y];
    q.push(Point(x, siz[x]));
    q.push(Point(y, siz[y]));
    int u = S[x].top().x;
    S[x].pop();
    int v = S[y].top().x;
    S[y].pop();
    ans.push_back({u, v});
  }
  printf("YES\n");
  for (int i = 0; i < ans.size(); ++i) {
    printf("%d %d\n", ans[i].first, ans[i].second);
  }
  return 0;
}