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 = 1e5 + 5;
int n, rt, p[N], sz[N], fa[N], dep[N], cur;
long long lower, upper, k;
set<int> g[N];
set<pair<int, int>> leaves[N], subs, last;
vector<pair<int, int>> pairs;
vector<int> rest[N];
bool del[N];
void find(int u, int fa) {
  int max_size = 1;
  sz[u] = 1;
  for (auto v : g[u])
    if (v != fa) find(v, u), max_size = max(max_size, sz[v]), sz[u] += sz[v];
  if (max(max_size, n - sz[u]) <= (n + 1) / 2) rt = u;
}
void dfs(int u) {
  sz[u] = 1;
  if (fa[u]) g[u].erase(fa[u]);
  for (auto v : g[u])
    fa[v] = u, dep[v] = dep[u] + 1, dfs(v), sz[u] += sz[v], lower += sz[v] & 1,
    upper += sz[v];
}
void push_leaf(int u, int belong) {
  if (sz[u] == 1) leaves[belong].insert({dep[u], u});
  for (auto v : g[u]) push_leaf(v, belong);
}
void push_rest(int u, int belong) {
  if (!del[u]) rest[belong].emplace_back(u);
  for (auto v : g[u]) push_rest(v, belong);
}
void insert(int u, int v) {
  pairs.emplace_back(u, v);
  del[u] = del[v] = true;
}
int main() {
  cin >> n >> k;
  for (int i = 1, u, v; i < n; ++i)
    cin >> u >> v, g[u].insert(v), g[v].insert(u);
  find(1, 0), dfs(rt);
  if (lower > k || upper < k || (k = upper - k) & 1) return cout << "NO\n", 0;
  cout << "YES\n", k /= 2;
  for (auto v : g[rt]) push_leaf(v, v), subs.insert({sz[v], v});
  while (k) {
    auto biggest = *subs.rbegin();
    subs.erase(biggest);
    int v = biggest.second;
    subs.insert({sz[v] -= 2, v});
    auto leaf = *leaves[v].rbegin();
    int x = leaf.second, father = fa[x], d = leaf.first - 1;
    if (k >= d) {
      k -= d;
      auto erase = [&](int x) {
        leaves[v].erase({dep[x], x});
        g[fa[x]].erase(x);
      };
      erase(x);
      auto push = [&](int x) {
        if (g[x].empty()) leaves[v].insert({dep[x], x});
      };
      if (g[father].empty())
        g[fa[father]].erase(father), insert(x, father), push(fa[father]);
      else
        insert(x, *g[father].begin()), erase(*g[father].begin()), push(father);
    } else {
      int cur = x;
      while (dep[cur] > k + 1) cur = fa[cur];
      insert(cur, fa[cur]);
      break;
    }
  }
  rest[cur++] = {rt};
  for (auto v : g[rt]) push_rest(v, cur++);
  for (int i = 0; i < cur; ++i)
    if (!rest[i].empty()) last.insert({rest[i].size(), i});
  auto pair = [&](int x, int y) {
    insert(rest[x].back(), rest[y].back());
    rest[x].pop_back(), rest[y].pop_back();
  };
  while (!last.empty()) {
    assert(last.size() >= 2);
    auto it = --last.end(), ij = it--;
    last.erase(it), last.erase(ij);
    auto p = *it, q = *ij;
    assert(p.first == rest[p.second].size());
    assert(q.first == rest[q.second].size());
    pair(p.second, q.second);
    if (--p.first) last.insert(p);
    if (--q.first) last.insert(q);
  }
  for (auto &p : pairs) cout << p.first << " " << p.second << "\n";
  return 0;
}