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 + 100;
int n, depth[maxn], cnt[maxn], a[maxn];
long long k;
vector<int> g[maxn], *gg[maxn];
priority_queue<pair<int, int>> q;
vector<pair<int, int>> res;
void bfs(int s, int p) {
  depth[s] = 1;
  for (auto it : g[s]) {
    if (it == p) continue;
    bfs(it, s);
    depth[s] += depth[it];
  }
}
void dfs(int s, int p) {
  for (auto it : g[s]) {
    if (it == p) continue;
    dfs(it, s);
  }
  while (!q.empty()) q.pop();
  gg[s] = new vector<int>(1, s);
  q.push({1, s});
  int val = 1;
  for (auto it : g[s]) {
    if (it == p) continue;
    if (!gg[it]->empty()) {
      q.push({(int)(gg[it])->size(), it});
      val += gg[it]->size();
    }
  }
  while (val > a[s]) {
    int x = q.top().second;
    q.pop();
    int y = q.top().second;
    q.pop();
    res.push_back({gg[x]->back(), gg[y]->back()});
    gg[x]->pop_back();
    gg[y]->pop_back();
    val -= 2;
    if (!gg[x]->empty()) q.push({gg[x]->size(), x});
    if (!gg[y]->empty()) q.push({gg[y]->size(), y});
  }
  if (!q.empty()) {
    int u = q.top().second;
    q.pop();
    while (!q.empty()) {
      int w = q.top().second;
      q.pop();
      for (int i = 0; i < gg[w]->size(); i++) gg[u]->push_back((*gg[w])[i]);
      delete gg[w];
    }
    gg[s] = gg[u];
  }
}
int main() {
  int t = 1;
  while (t--) {
    cin >> n >> k;
    for (int i = 0; i < n - 1; i++) {
      int x, y;
      cin >> x >> y;
      --x;
      --y;
      g[x].push_back(y);
      g[y].push_back(x);
    }
    bfs(0, -1);
    long long cur = 0, mx = 0;
    for (int i = 0; i <= n; i++) cnt[i] = 0;
    for (int i = 0; i < n; i++) {
      cur += (depth[i] & 1);
      int x = min(depth[i], n - depth[i]);
      mx += x;
      ++cnt[x];
    }
    if (k < cur or k > mx or (k & 1) != (cur & 1)) {
      cout << "NO\n";
      continue;
    }
    int c[2] = {n - (int)cur, (int)cur};
    c[0] -= cnt[0];
    c[1] -= cnt[1];
    for (int i = 2; i <= n; i++) {
      if (cur + c[i & 1] * 2 >= k) {
        a[0] = 0;
        for (int v = 0; v < n; v++) {
          int val = ((depth[v] & 1) == (i & 1) ? i - 2 : i - 1);
          val = min(val, min(depth[v], n - depth[v]));
          a[v] = val;
        }
        int need = k - cur;
        for (int v = 0; v < n and need; v++) {
          if ((depth[v] & 1) == (i & 1) and
              a[v] + 2 <= min(depth[v], n - depth[v])) {
            a[v] += 2;
            need -= 2;
          }
        }
        break;
      }
      cur += c[i & 1] * 2;
      c[i & 1] -= cnt[i];
    }
    res.clear();
    dfs(0, -1);
    cout << "YES\n";
    for (int i = 0; i < res.size(); i++)
      cout << res[i].first + 1 << " " << res[i].second + 1 << endl;
  }
  return 0;
}