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 = 1e5 + 5;
vector<int> adj[maxn];
int N, sz[maxn], big[maxn];
int root;
long long K;
int depth[maxn];
int belong[maxn];
bool matched[maxn];
set<pair<int, int> > same[maxn];
int par[maxn];
void prep(int u, int par = -1) {
  sz[u] = 1;
  big[u] = -1;
  for (int v : adj[u]) {
    if (v != par) {
      prep(v, u);
      sz[u] += sz[v];
      if (big[u] == -1 || sz[big[u]] < sz[v]) {
        big[u] = v;
      }
    }
  }
}
int centroid(void) {
  prep(1, 0);
  int u = 1;
  while (big[u] != -1 && sz[big[u]] >= N / 2) u = big[u];
  return u;
}
long long bound(void) {
  long long lo = 0, hi = 0;
  function<void(int, int, int)> dfs = [&](int u, int p, int r) {
    depth[u] = depth[p] + 1;
    belong[u] = r;
    par[u] = p;
    auto it = find(adj[u].begin(), adj[u].end(), p);
    adj[u].erase(it);
    sz[u] = 1;
    for (int v : adj[u]) {
      dfs(v, u, r);
      sz[u] += sz[v];
    }
    lo += (sz[u] % 2);
    hi += sz[u];
  };
  for (int v : adj[root]) {
    dfs(v, root, v);
  }
  if (lo > K || hi < K || (hi - K) % 2 == 1) {
    cout << "NO\n";
    exit(0);
  }
  return hi;
}
signed main(void) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> N >> K;
  for (int i = 1; i < N; ++i) {
    int u, v;
    cin >> u >> v;
    adj[u].emplace_back(v);
    adj[v].emplace_back(u);
  }
  root = centroid();
  long long cur = bound();
  vector<int> deg(N + 1, 0);
  for (int i = 1; i <= N; ++i) deg[i] = adj[i].size();
  for (int v = 1; v <= N; ++v) {
    if (deg[v] != 0 && v != root) {
      same[belong[v]].insert(make_pair(depth[v], v));
    }
  }
  set<pair<int, int> > child;
  for (int v : adj[root]) {
    child.insert(make_pair(sz[v], v));
  }
  auto rem = [&](int v) {
    --deg[par[v]];
    if (deg[par[v]] == 0) {
      v = par[v];
      same[belong[v]].erase(make_pair(depth[v], v));
    }
  };
  cout << "YES\n";
  while (cur > K) {
    int v = (*child.rbegin()).second;
    child.erase(make_pair(sz[v], v));
    int dec = (*same[v].rbegin()).first;
    if (cur - 2 * dec <= K) {
      int x = same[v].lower_bound(make_pair((cur - K) / 2, -1))->second;
      int y = -1;
      assert(depth[x] == (cur - K) / 2);
      for (int u : adj[x]) {
        if (!matched[u]) {
          y = u;
        }
      }
      assert(y != -1);
      cur = K;
      assert(matched[x] == matched[y] && matched[x] == false);
      cout << x << ' ' << y << '\n';
      matched[x] = matched[y] = true;
    } else {
      cur -= 2 * dec;
      vector<int> vi;
      int u = same[v].rbegin()->second;
      while (vi.size() < 2 && adj[u].size() > 0) {
        int tmp = adj[u].back();
        adj[u].pop_back();
        if (!matched[tmp]) {
          vi.emplace_back(tmp);
        }
      }
      if (vi.size() < 2) vi.emplace_back(u);
      cout << vi[0] << ' ' << vi[1] << '\n';
      assert(matched[vi[0]] == matched[vi[1]] && matched[vi[0]] == false);
      matched[vi[0]] = matched[vi[1]] = true;
      rem(vi[0]);
      rem(vi[1]);
      sz[v] -= 2;
      if (sz[v]) child.insert(make_pair(sz[v], v));
    }
  }
  vector<int> remain;
  function<void(int)> dfs = [&](int u) {
    if (!matched[u]) remain.emplace_back(u);
    for (int v : adj[u]) dfs(v);
  };
  dfs(root);
  for (int i = 0; i < (int)remain.size() / 2; ++i) {
    cout << remain[i] << ' ' << remain[i + remain.size() / 2] << '\n';
  }
}