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 + 10, mod = 1e9 + 7, inf = 1e9 + 10;
int SZ[maxn];
bool done[maxn];
int h[maxn], pr[maxn];
vector<int> eraseList[maxn];
vector<int> v[maxn];
void dfsSZ(int u, int par = -1) {
  SZ[u] = !done[u];
  for (int y : v[u])
    if (y != par) dfsSZ(y, u), SZ[u] += SZ[y];
}
int center(int u, int N, int par = -1) {
  for (int y : v[u])
    if (y != par && SZ[y] > N) return center(y, N, u);
  return u;
}
void fill(int u, int root, int par) {
  eraseList[root].push_back(u);
  h[u] = h[par] + 1;
  pr[u] = par;
  for (int y : v[u])
    if (y != par) fill(y, root, u);
}
vector<pair<int, int> > ans;
int solveMin(int u, int par = -1) {
  int lst = -1;
  if (!done[u]) lst = u;
  for (int y : v[u]) {
    if (y != par) {
      int x = solveMin(y, u);
      if (x == -1) continue;
      if (lst == -1)
        lst = x;
      else
        ans.push_back({lst, x}), lst = -1;
    }
  }
  return lst;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie();
  int n;
  cin >> n;
  long long k;
  cin >> k;
  for (int i = 0; i < n - 1; i++) {
    int a, b;
    cin >> a >> b;
    v[a].push_back(b);
    v[b].push_back(a);
  }
  dfsSZ(1);
  int root = center(1, n / 2);
  dfsSZ(root);
  vector<int> vec;
  for (int y : v[root]) {
    fill(y, y, root);
    for (int i = 0; i < SZ[y]; i++) vec.push_back(y);
  }
  eraseList[root].push_back(root);
  vec.push_back(root);
  assert(int((vec).size()) == n);
  int pt = 0;
  while (pt < (n / 2) && k >= 2 * n) {
    int A = eraseList[vec[pt]].back(), B = eraseList[vec[pt + (n / 2)]].back();
    eraseList[vec[pt]].pop_back(), eraseList[vec[pt + (n / 2)]].pop_back();
    done[A] = done[B] = 1;
    ans.push_back({A, B});
    k -= h[A] + h[B];
    pt++;
  }
  if (pt == (n / 2) && k > 0) return cout << "NO\n", 0;
  dfsSZ(root);
  for (int i = 1; i <= n; i++) k -= SZ[i] & 1;
  if ((k & 1) || k < 0) return cout << "NO\n", 0;
  while (k > 0 && pt < (n / 2)) {
    int A = eraseList[vec[pt]].back(), B = eraseList[vec[pt + (n / 2)]].back();
    eraseList[vec[pt]].pop_back(), eraseList[vec[pt + (n / 2)]].pop_back();
    int delta = 0;
    int tmp = A;
    while (tmp != root) delta += 2 * (!(SZ[tmp] & 1)), tmp = pr[tmp];
    tmp = B;
    while (tmp != root) delta += 2 * (!(SZ[tmp] & 1)), tmp = pr[tmp];
    if (k - delta > 0) {
      done[A] = done[B] = 1;
      ans.push_back({A, B});
      while (A != root) k -= 2 * (!(SZ[A] & 1)), --SZ[A], A = pr[A];
      while (B != root) k -= 2 * (!(SZ[B] & 1)), --SZ[B], B = pr[B];
      SZ[root] -= 2;
    } else {
      while (A != root && delta > k) delta -= 2 * (!(SZ[A] & 1)), A = pr[A];
      while (B != root && delta > k) delta -= 2 * (!(SZ[B] & 1)), B = pr[B];
      assert(delta == k);
      k = 0;
      done[A] = done[B] = 1;
      ans.push_back({A, B});
      break;
    }
    pt++;
  }
  if (k > 0) return cout << "NO\n", 0;
  assert(k == 0);
  cout << "YES\n";
  int chert = solveMin(root);
  assert(chert == -1);
  for (pair<int, int> p : ans) {
    cout << p.first << " " << p.second << "\n";
  }
  return 0;
}