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>
#pragma comment(linker, "/STACK:1000000000")
#pragma GCC optimize("Ofast,no-stack-protector")
using namespace std;
const int maxn = (int)1e5 + 10;
vector<int> ed[maxn];
int sz[maxn];
void dfs(int v, int p) {
  sz[v] = 1;
  for (int u : ed[v]) {
    if (u != p) {
      dfs(u, v);
      sz[v] += sz[u];
    }
  }
}
int h[maxn];
vector<pair<pair<int, int>, int> > g[maxn];
long long sum = 0;
set<int> vert[maxn];
int tt = -1;
int tin[maxn], tout[maxn];
void build(int v, int p, int pr, int hh) {
  tt++;
  tin[v] = tt;
  vert[pr].insert(v);
  sum += hh;
  h[v] = hh;
  sz[v] = 1;
  vector<int> a;
  for (int u : ed[v]) {
    if (u == p) {
      continue;
    }
    build(u, v, pr, hh + 1);
    sz[v] += sz[u];
    if (sz[u] & 1) {
      a.push_back(u);
    }
  }
  while ((int)a.size() >= 2) {
    int x = a.back();
    a.pop_back();
    int y = a.back();
    a.pop_back();
    g[pr].push_back(make_pair(make_pair(x, y), hh));
  }
  if (!a.empty()) {
    g[pr].push_back(make_pair(make_pair(a.back(), v), hh));
  }
  tout[v] = tt;
}
bool is_anc(int x, int y) { return tin[x] <= tin[y] && tout[y] <= tout[x]; }
int main() {
  int n;
  long long k;
  cin >> n >> k;
  for (int i = 0; i < n - 1; i++) {
    int x, y;
    scanf("%d %d", &x, &y);
    x--;
    y--;
    ed[x].push_back(y);
    ed[y].push_back(x);
  }
  dfs(0, -1);
  int v = 0;
  while (true) {
    bool ok = true;
    for (int u : ed[v]) {
      if (sz[u] < sz[v] && 2 * sz[u] > n) {
        v = u;
        ok = false;
        break;
      }
    }
    if (ok) {
      break;
    }
  }
  for (int u : ed[v]) {
    build(u, v, u, 1);
    reverse((g[u]).begin(), (g[u]).end());
  }
  if (k > sum) {
    cout << "NO\n" << '\n';
    return 0;
  }
  set<pair<int, int> > s;
  for (int u : ed[v]) {
    s.insert(make_pair(sz[u], u));
  }
  vector<pair<int, int> > res;
  if ((k - sum) & 1) {
    cout << "NO\n" << '\n';
    return 0;
  }
  while (!s.empty() && sum != k) {
    int u = s.rbegin()->second;
    s.erase(*s.rbegin());
    if (sz[u] == 1) {
      cout << "NO\n" << '\n';
      return 0;
    }
    if (sum - 2 * g[u].back().second >= k) {
      sum -= 2 * g[u].back().second;
      sz[u] -= 2;
      s.insert(make_pair(sz[u], u));
      res.push_back(g[u].back().first);
      vert[u].erase(g[u].back().first.first);
      vert[u].erase(g[u].back().first.second);
      g[u].pop_back();
      continue;
    }
    int x = g[u].back().first.first;
    int y = -1;
    for (int z : vert[u]) {
      if (sum - 2 * h[z] == k && is_anc(z, x)) {
        y = z;
        break;
      }
    }
    assert(y != -1);
    res.push_back(make_pair(x, y));
    vert[u].erase(x);
    vert[u].erase(y);
    break;
  }
  cout << "YES\n";
  s.clear();
  for (int u : ed[v]) {
    if (vert[u].size()) {
      s.insert(make_pair(vert[u].size(), u));
    }
  }
  while ((int)s.size() > 1) {
    int x = s.rbegin()->second;
    s.erase(*s.rbegin());
    int y = s.rbegin()->second;
    s.erase(*s.rbegin());
    int a = *vert[x].begin();
    vert[x].erase(a);
    int b = *vert[y].begin();
    vert[y].erase(b);
    res.push_back(make_pair(a, b));
    if (vert[x].size()) {
      s.insert(make_pair(vert[x].size(), x));
    }
    if (vert[y].size()) {
      s.insert(make_pair(vert[y].size(), y));
    }
  }
  int x = s.begin()->second;
  assert((int)vert[x].size() == 1);
  res.push_back(make_pair(v, *vert[x].begin()));
  for (pair<int, int> f : res) {
    printf("%d %d\n", f.first + 1, f.second + 1);
  }
}