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;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template <typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) { return (ull)rng() % B; }
clock_t startTime;
double getCurrentTime() {
  return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}
const int N = 100100;
int n;
vector<pii> ans;
vector<int> g[N];
int sz[N];
int h[N];
set<pair<int, pii>> match[N];
set<int> comp[N];
ll want;
void dfsSz(int v, int par) {
  sz[v] = 1;
  for (int u : g[v]) {
    if (u == par) continue;
    dfsSz(u, v);
    sz[v] += sz[u];
  }
}
int dfsMatch(int v, int par, int id) {
  comp[id].insert(v);
  int lft = -1;
  for (int u : g[v]) {
    if (u == par) continue;
    h[u] = h[v] + 1;
    int x = dfsMatch(u, v, id);
    if (x != -1) {
      if (lft == -1) {
        lft = x;
      } else {
        match[id].insert(make_pair(h[v], make_pair(lft, x)));
        lft = -1;
      }
    }
  }
  if (lft == -1) {
    return v;
  } else {
    match[id].insert(make_pair(h[v], make_pair(lft, v)));
    return -1;
  }
}
int findWithH(int v, int H) {
  assert(h[v] > H);
  int u = v;
  while (h[u] > H) {
    for (int w : g[u]) {
      if (h[w] < h[u]) {
        u = w;
        break;
      }
    }
  }
  return u;
}
int main() {
  startTime = clock();
  scanf("%d%lld", &n, &want);
  for (int i = 1; i < n; i++) {
    int v, u;
    scanf("%d%d", &v, &u);
    v--;
    u--;
    g[v].push_back(u);
    g[u].push_back(v);
  }
  dfsSz(0, -1);
  int v = 0;
  while (true) {
    int w = v;
    for (int u : g[v]) {
      if (sz[u] > sz[v] || 2 * sz[u] < n) continue;
      w = u;
    }
    if (w == v) break;
    v = w;
  }
  dfsSz(v, -1);
  ll minVal = 0, maxVal = 0;
  for (int i = 0; i < n; i++) {
    minVal += sz[i] & 1;
    maxVal += sz[i];
  }
  maxVal -= n;
  if (want < minVal || want > maxVal || (want - minVal) % 2 == 1) {
    printf("NO\n");
    return 0;
  }
  printf("YES\n");
  want = (maxVal - want) / 2;
  for (int u : g[v]) {
    h[u] = 1;
    dfsMatch(u, v, u);
  }
  set<pii> setik;
  for (int u : g[v]) setik.insert(make_pair(sz[u], u));
  while (want > 0) {
    pii cur = *setik.rbegin();
    assert(cur.first >= 2);
    setik.erase(cur);
    int u = cur.second;
    assert(!match[u].empty());
    auto p = *match[u].rbegin();
    if (p.first <= want) {
      want -= p.first;
      match[u].erase(p);
      ans.push_back(p.second);
      comp[u].erase(p.second.first);
      comp[u].erase(p.second.second);
      if (cur.first - 2 > 0) setik.insert(make_pair(cur.first - 2, u));
      continue;
    }
    int w = p.second.first;
    int z = findWithH(w, want);
    ans.push_back(make_pair(w, z));
    comp[u].erase(w);
    comp[u].erase(z);
    if (cur.first - 2 > 0) setik.insert(make_pair(cur.first - 2, u));
    break;
  }
  setik.insert(make_pair(1, v));
  comp[v].insert(v);
  while (!setik.empty()) {
    assert((int)setik.size() >= 2);
    pii c1 = *setik.rbegin();
    setik.erase(c1);
    pii c2 = *setik.rbegin();
    setik.erase(c2);
    int u = c1.second, w = c2.second;
    ans.push_back(make_pair(*comp[u].begin(), *comp[w].begin()));
    comp[u].erase(comp[u].begin());
    comp[w].erase(comp[w].begin());
    if (c1.first - 1 > 0) setik.insert(make_pair(c1.first - 1, u));
    if (c2.first - 1 > 0) setik.insert(make_pair(c2.first - 1, w));
  }
  for (auto t : ans) printf("%d %d\n", t.first + 1, t.second + 1);
  return 0;
}