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;
template <typename T>
void chkmin(T &first, T second) {
  second < first ? first = second : T();
}
template <typename T>
void chkmax(T &first, T second) {
  first < second ? first = second : T();
}
template <typename T>
void readint(T &first) {
  int f = 1;
  char c;
  first = 0;
  for (c = getchar(); !isdigit(c); c = getchar())
    if (c == '-') f = -1;
  for (; isdigit(c); c = getchar()) first = first * 10 + (c - '0');
  first *= f;
}
const int MOD = 998244353;
inline int dmy(int first) { return first >= MOD ? first - MOD : first; }
inline void inc(int &first, int second) { first = dmy(first + second); }
int qmi(int first, int second) {
  int ans = 1;
  for (; second; second >>= 1, first = 1ll * first * first % MOD)
    if (second & 1) ans = 1ll * ans * first % MOD;
  return ans;
}
const int MAXN = 100005;
int n;
long long k;
vector<int> G[MAXN], vc[MAXN];
unordered_set<int> son[MAXN];
int size[MAXN], weight[MAXN], root, dep[MAXN], pa[MAXN];
priority_queue<pair<int, int>, vector<pair<int, int> >, less<pair<int, int> > >
    q[MAXN], pq;
bool vis[MAXN];
int whi[MAXN];
void dfs1(int u, int pa) {
  size[u] = 1;
  for (auto v : G[u]) {
    if (v == pa) continue;
    dfs1(v, u);
    size[u] += size[v];
    chkmax(weight[u], size[v]);
  }
  chkmax(weight[u], n - size[u]);
}
void dfs2(int u, int f) {
  whi[u] = f;
  size[u] = 1;
  for (auto v : G[u]) {
    if (v == pa[u]) continue;
    pa[v] = u;
    dep[v] = dep[u] + 1;
    dfs2(v, f ? f : v);
    son[u].insert(v);
    size[u] += size[v];
  }
}
int main() {
  readint(n), readint(k);
  for (int i = 1; i < n; ++i) {
    int u, v;
    readint(u), readint(v);
    G[u].push_back(v), G[v].push_back(u);
  }
  dfs1(1, -1);
  long long mn = 0, mx = 0;
  weight[0] = 1 << 30;
  for (int i = 1; i <= n; ++i) {
    if (weight[i] <= weight[root]) root = i;
    mn += size[i] & 1, mx += min(size[i], n - size[i]);
  }
  if ((mn & 1) != (k & 1) || k < mn || k > mx) return 0 * printf("NO\n");
  printf("YES\n");
  k = (mx - k) / 2;
  dfs2(root, 0);
  for (int i = 1; i <= n; ++i)
    if (!son[i].empty()) q[whi[i]].push(make_pair(dep[i], i));
  for (auto v : G[root])
    if (size[v] >= 2) pq.push(make_pair(size[v], v));
  size[0] = 1;
  while (k) {
    int w = pq.top().second;
    pq.pop();
    pair<int, int> p = q[w].top();
    q[w].pop();
    if (p.first > k) break;
    int u = p.second;
    if (son[u].empty()) {
      if (size[w] >= 2) pq.push(make_pair(size[w], w));
      continue;
    }
    k -= dep[u];
    if (son[u].size() >= 2) {
      int first = *son[u].begin();
      son[u].erase(first);
      int second = *son[u].begin();
      son[u].erase(second);
      printf("%d %d\n", first, second);
      vis[first] = vis[second] = 1;
    } else {
      int first = *son[u].begin();
      son[u].erase(first);
      son[pa[u]].erase(u);
      printf("%d %d\n", u, first);
      vis[u] = vis[first] = 1;
    }
    if (!son[u].empty()) q[w].push(make_pair(dep[u], u));
    size[w] -= 2;
    if (size[w] >= 2) pq.push(make_pair(size[w], w));
  }
  int best = 1;
  for (auto v : G[root]) chkmax(best, size[v]);
  for (int i = 1; i <= n; ++i)
    if (!vis[i] && dep[i] == k && !son[i].empty() && size[whi[i]] == best) {
      int first = *son[i].begin();
      son[i].erase(first);
      printf("%d %d\n", i, first);
      vis[i] = vis[first] = 1;
      size[whi[i]]--, size[whi[first]]--;
      break;
    }
  while (!pq.empty()) pq.pop();
  for (int i = 1; i <= n; ++i)
    if (!vis[i]) vc[whi[i]].push_back(i);
  for (int i = 0; i <= n; ++i)
    if (!vc[i].empty()) pq.push(make_pair(vc[i].size(), i));
  while (!pq.empty()) {
    int u = pq.top().second;
    pq.pop();
    int v = pq.top().second;
    pq.pop();
    printf("%d %d\n", vc[u].back(), vc[v].back());
    vc[u].pop_back(), vc[v].pop_back();
    if (!vc[u].empty()) pq.push(make_pair(vc[u].size(), u));
    if (!vc[v].empty()) pq.push(make_pair(vc[v].size(), v));
  }
  return 0;
}