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;
int n, sz[100100], x[100100], y[100100], cnt[100100];
long long k;
vector<int> adj[100100];
int dfs(int u, int pa = 0) {
  int rlt = 1;
  for (auto e : adj[u]) {
    int v = x[e] ^ y[e] ^ u;
    if (v == pa) continue;
    int c = dfs(v, u);
    if (c & 1) cnt[e]++, k--;
    sz[e] = c, rlt += c;
  }
  return rlt;
}
int id[100100], up[100100];
vector<pair<int, int> > ans;
vector<int> vec[100100];
void dfs_solve(int u, int pa = 0, int up = 0) {
  vec[u].push_back(u);
  int tot = 0;
  priority_queue<pair<int, int> > pq;
  pq.emplace(1, u);
  for (auto e : adj[u]) {
    int v = x[e] ^ y[e] ^ u;
    if (v == pa) continue;
    dfs_solve(v, u, cnt[e]);
    assert(vec[v].size() == cnt[e]);
    tot += cnt[e];
    pq.emplace(cnt[e], v);
  }
  while (tot > up) {
    pair<int, int> pu = pq.top();
    pq.pop();
    pair<int, int> pv = pq.top();
    pq.pop();
    int u = pu.second, v = pv.second;
    tot -= 2;
    ans.emplace_back(vec[u].back(), vec[v].back()), vec[u].pop_back(),
        vec[v].pop_back();
    pq.emplace(pu.first - 1, u), pq.emplace(pv.first - 1, v);
  }
  for (auto e : adj[u]) {
    int v = x[e] ^ y[e] ^ u;
    if (v == pa) continue;
    if (vec[u].size() < vec[v].size()) swap(vec[u], vec[v]);
    for (auto x : vec[v]) vec[u].push_back(x);
  }
}
int main() {
  scanf("%d %lld", &n, &k);
  long long _k = k;
  for (int i = 1, u, v; i < n; i++) {
    scanf("%d %d", &u, &v);
    adj[u].push_back(i);
    adj[v].push_back(i);
    x[i] = u, y[i] = v;
  }
  dfs(1);
  if (k < 0 || (k & 1)) return puts("NO"), 0;
  long long sum = 0;
  k /= 2;
  for (int i = 1; i < n; i++)
    id[i] = i, up[i] = min(sz[i], n - sz[i]), sz[i] = min(sz[i], n - sz[i]) / 2,
    sum += sz[i];
  if (k > sum) return puts("NO"), 0;
  sort(id + 1, id + n, [&](int i, int j) { return sz[i] < sz[j]; });
  for (int i = 1, c = 0; i < n; i++) {
    if (1ll * (n - i) * (sz[id[i]] - c) >= k) {
      int q = k / (n - i), r = k % (n - i);
      for (int j = i; j < i + r; j++) cnt[id[j]] += 2;
      for (int j = i; j < n; j++) cnt[id[j]] += 2 * (c + q);
      for (int j = 1; j < i; j++) cnt[id[j]] += 2 * sz[id[j]];
      break;
    } else
      k -= 1ll * (n - i) * (sz[id[i]] - c), c = sz[id[i]];
  }
  while (1) {
    bool fg = false;
    for (int u = 1; u <= n; u++) {
      int mx = 0;
      long long s = 0;
      for (auto e : adj[u]) mx = max(mx, cnt[e]), s += cnt[e];
      if (mx > s - mx + 1) {
        fg = true;
        int e1;
        for (auto e : adj[u])
          if (mx == cnt[e]) {
            e1 = e;
            cnt[e] -= 2;
            break;
          }
        for (auto e : adj[u]) {
          if (e != e1 && cnt[e] + 2 <= up[e]) {
            cnt[e] += 2;
            break;
          }
        }
      }
    }
    if (!fg) break;
  }
  dfs_solve(1);
  puts("YES");
  for (auto p : ans) printf("%d %d\n", p.first, p.second);
  return 0;
}