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;
const int MAX_N = 1e5 + 5;
int N;
LL K;
vector<int> G[MAX_N], buc[MAX_N];
set<int> S[MAX_N];
int rt, rmx, sz[MAX_N];
void getrt(int x, int fa) {
  sz[x] = 1;
  int mx = 1;
  for (int v : G[x])
    if (v != fa) getrt(v, x), sz[x] += sz[v], mx = max(mx, sz[v]);
  mx = max(N - sz[x], mx);
  if (mx < rmx) rt = x, rmx = mx;
}
int fa[MAX_N], dep[MAX_N];
void dfs(int x, int cur) {
  sz[x] = 1, dep[x] = dep[fa[x]] + 1;
  buc[cur].push_back(x);
  for (int v : G[x]) {
    if (v == fa[x]) continue;
    fa[v] = x, dfs(v, cur), sz[x] += sz[v];
  }
  for (int v : G[x])
    if (v != fa[x]) S[x].insert(v);
}
int vis[MAX_N];
struct compare {
  bool operator()(const int &x, const int &y) { return sz[x] < sz[y]; }
};
vector<int> pot;
void getpot(int x, int fa) {
  if (!vis[x]) pot.push_back(x);
  for (int v : G[x])
    if (v != fa) getpot(v, x);
}
int main() {
  scanf("%d %lld", &N, &K);
  for (int i = 1; i < N; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    G[u].push_back(v), G[v].push_back(u);
  }
  rmx = N, getrt(1, 0), sz[rt] = 0;
  priority_queue<int, vector<int>, compare> global;
  for (int x : G[rt]) {
    fa[x] = rt, dfs(x, x);
    sort(buc[x].begin(), buc[x].end(),
         [](const int &i, const int &j) { return dep[i] < dep[j]; });
    global.push(x);
  }
  LL L = 0, R = 0;
  for (int i = 1; i <= N; i++) L += sz[i] & 1, R += sz[i];
  if (K < L || K > R || ((R - K) & 1)) return puts("NO") & 0;
  vector<pair<int, int> > ans;
  while (K != R) {
    int bel = global.top();
    global.pop();
    while (!S[buc[bel].back()].size()) buc[bel].pop_back();
    int x = buc[bel].back();
    if (K + 2 * dep[x] < R) {
      if (S[x].size() >= 2) {
        int a = *S[x].begin(), b = *next(S[x].begin());
        S[x].erase(a), S[x].erase(b), sz[bel] -= 2;
        vis[a] = vis[b] = 1;
        ans.emplace_back(a, b);
      } else {
        int a = *S[x].begin();
        S[x].erase(a);
        if (fa[x] != rt) S[fa[x]].erase(x);
        sz[bel] -= 2, vis[a] = vis[x] = 1;
        ans.emplace_back(a, x);
      }
      K += 2 * dep[x];
    } else {
      for (int i : buc[bel]) {
        if (vis[i] || !S[i].size() || K + 2 * dep[i] != R) continue;
        ans.emplace_back(i, *S[i].begin());
        vis[i] = vis[*S[i].begin()] = 1;
        break;
      }
      break;
    }
    global.push(bel);
  }
  getpot(rt, 0);
  for (int i = 0; i < (int)pot.size() / 2; i++)
    ans.emplace_back(pot[i], pot[i + pot.size() / 2]);
  puts("YES");
  for (auto it : ans) printf("%d %d\n", it.first, it.second);
  return 0;
}