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;
std::mt19937 rnd(
    (int)std::chrono::steady_clock::now().time_since_epoch().count());
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
const int MAXN = 100000;
int n;
long long want;
vector<int> adj[MAXN];
int match[MAXN];
int sz[MAXN];
void dfssz(int at, int par) {
  sz[at] = 1;
  for (int i = (0); i < (((int)(adj[at]).size())); ++i) {
    int to = adj[at][i];
    if (to == par) continue;
    dfssz(to, at);
    sz[at] += sz[to];
  }
}
int dfscentroid(int at, int par, int rootsz) {
  for (int i = (0); i < (((int)(adj[at]).size())); ++i) {
    int to = adj[at][i];
    if (to == par) continue;
    if (2 * sz[to] >= rootsz) return dfscentroid(to, at, rootsz);
  }
  return at;
}
int centroid(int at) {
  dfssz(at, -1);
  return dfscentroid(at, -1, sz[at]);
}
struct SubTree {
  int sz;
  vector<vector<int>> nodesbydep;
  SubTree() : sz(0) {}
};
int par[MAXN], dep[MAXN];
vector<SubTree> subtrees;
void dfsinit(int at, int id) {
  ++subtrees[id].sz;
  while (dep[at] >= ((int)(subtrees[id].nodesbydep).size()))
    subtrees[id].nodesbydep.push_back(vector<int>());
  subtrees[id].nodesbydep[dep[at]].push_back(at);
  for (int i = (0); i < (((int)(adj[at]).size())); ++i) {
    int to = adj[at][i];
    if (to == par[at]) continue;
    par[to] = at;
    dep[to] = dep[at] + 1;
    dfsinit(to, id);
  }
}
bool solve() {
  int cent = centroid(0);
  subtrees.clear();
  par[cent] = -1;
  for (int i = (0); i < (((int)(adj[cent]).size())); ++i) {
    int to = adj[cent][i];
    subtrees.push_back(SubTree());
    par[to] = cent;
    dep[to] = 0;
    dfsinit(to, i);
  }
  long long have = 0;
  for (int i = (0); i < (((int)(subtrees).size())); ++i)
    for (int j = (0); j < (((int)(subtrees[i].nodesbydep).size())); ++j)
      have += (long long)(j + 1) * ((int)(subtrees[i].nodesbydep[j]).size());
  if (want > have) return false;
  if (want % 2 != have % 2) return false;
  long long steps = (have - want) / 2;
  priority_queue<pair<int, int>> pq;
  for (int i = (0); i < (((int)(subtrees).size())); ++i)
    pq.push(make_pair(subtrees[i].sz, i));
  for (int i = (0); i < (n); ++i) match[i] = -1;
  while (steps > 0) {
    int id = pq.top().second;
    pq.pop();
    if (subtrees[id].sz == 1) return false;
    int d = ((int)(subtrees[id].nodesbydep).size()) - 1;
    assert(d >= 1);
    if (d <= steps) {
      int a = subtrees[id].nodesbydep[d].back();
      subtrees[id].nodesbydep[d].pop_back();
      while (!subtrees[id].nodesbydep[d].empty() &&
             match[subtrees[id].nodesbydep[d].back()] != -1)
        subtrees[id].nodesbydep[d].pop_back();
      assert(match[a] == -1);
      int b;
      if (!subtrees[id].nodesbydep[d].empty() &&
          par[a] == par[subtrees[id].nodesbydep[d].back()]) {
        b = subtrees[id].nodesbydep[d].back();
        subtrees[id].nodesbydep[d].pop_back();
      } else {
        b = par[a];
      }
      steps -= d, match[a] = b, match[b] = a, subtrees[id].sz -= 2;
      if (subtrees[id].sz >= 1) pq.push(make_pair(subtrees[id].sz, id));
      while (d > 0) {
        if (subtrees[id].nodesbydep[d].empty())
          subtrees[id].nodesbydep.pop_back(), --d;
        else if (match[subtrees[id].nodesbydep[d].back()] != -1)
          subtrees[id].nodesbydep[d].pop_back();
        else
          break;
      }
    } else {
      while (d > steps) --d;
      while (!subtrees[id].nodesbydep[d].empty() &&
             match[subtrees[id].nodesbydep[d].back()] != -1)
        subtrees[id].nodesbydep[d].pop_back();
      assert(!subtrees[id].nodesbydep[d].empty());
      int a = subtrees[id].nodesbydep[d].back();
      assert(dep[a] >= 1 && match[a] == -1);
      int b = par[a];
      assert(match[b] == -1);
      for (int i = ((int)(subtrees[id].nodesbydep[dep[a]]).size()) - 1; i >= 0;
           --i)
        if (subtrees[id].nodesbydep[dep[a]][i] == a)
          subtrees[id].nodesbydep[dep[a]].erase(
              subtrees[id].nodesbydep[dep[a]].begin() + i);
      for (int i = ((int)(subtrees[id].nodesbydep[dep[b]]).size()) - 1; i >= 0;
           --i)
        if (subtrees[id].nodesbydep[dep[b]][i] == b)
          subtrees[id].nodesbydep[dep[b]].erase(
              subtrees[id].nodesbydep[dep[b]].begin() + i);
      steps -= d, match[a] = b, match[b] = a;
    }
  }
  vector<int> lst;
  lst.push_back(cent);
  for (int i = (0); i < (((int)(subtrees).size())); ++i)
    for (int j = (0); j < (((int)(subtrees[i].nodesbydep).size())); ++j)
      for (int k = (0); k < (((int)(subtrees[i].nodesbydep[j]).size())); ++k) {
        int at = subtrees[i].nodesbydep[j][k];
        if (match[at] == -1) lst.push_back(at);
      }
  assert(((int)(lst).size()) % 2 == 0);
  for (int i = (0); i < (((int)(lst).size()) / 2); ++i) {
    int a = lst[i], b = lst[i + ((int)(lst).size()) / 2];
    match[a] = b, match[b] = a;
  }
  return true;
}
void run() {
  scanf("%d%lld", &n, &want);
  for (int i = (0); i < (n - 1); ++i) {
    int a, b;
    scanf("%d%d", &a, &b);
    --a, --b;
    adj[a].push_back(b), adj[b].push_back(a);
  }
  if (!solve()) {
    printf("NO\n");
    return;
  }
  printf("YES\n");
  for (int i = (0); i < (n); ++i)
    if (i < match[i]) printf("%d %d\n", i + 1, match[i] + 1);
}
void stress() {
  for (int rep = (0); rep < (100000); ++rep) {
    do {
      n = rnd() % 100 + 1;
    } while (n % 2 != 0);
    want = rnd() % n * n + 1;
    for (int i = (0); i < (n); ++i) adj[i].clear();
    vector<pair<int, int>> e;
    for (int i = (1); i < (n); ++i) {
      int a = rnd() % i, b = i;
      adj[a].push_back(b), adj[b].push_back(a);
      e.push_back(make_pair(a, b));
    }
    solve();
  }
}
int main() {
  run();
  return 0;
}