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 GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
using namespace std;
using ll = long long;
using ld = long double;
const ll MOD = 1000000007;
const ll root = 62;
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
ll binpow(ll a, ll b) {
  ll res = 1;
  while (b) {
    if (b & 1) res = (res * a) % MOD;
    a = (a * a) % MOD;
    b >>= 1;
  }
  return res;
}
ll modInv(ll a) { return binpow(a, MOD - 2); }
const double PI = acos(-1);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const ll NINFLL = 0xc0c0c0c0c0c0c0c0;
const int mxN = 100001;
int n;
ll k;
vector<int> adj[mxN];
int val[mxN];
int par[mxN];
int sz[mxN];
void weary(int u, int p = -1) {
  sz[u] = 1;
  for (int v : adj[u]) {
    if (v ^ p) {
      weary(v, u);
      sz[u] += sz[v];
    }
  }
  val[u] = min(n - sz[u], sz[u]);
}
void merge(set<pair<int, int> > &a, set<pair<int, int> > b) {
  int cnt = a.size();
  for (auto k : b) {
    a.insert({cnt++, k.second});
  }
}
vector<pair<int, int> > ans;
list<int> geniosity(int u, int p = -1) {
  list<int> curr = {u};
  for (int v : adj[u]) {
    if (v ^ p) {
      curr.splice(curr.end(), geniosity(v, u));
    }
  }
  int req = ((int)curr.size() - val[u]) / 2;
  vector<int> k1(req);
  vector<int> k2(req);
  for (int i = (0); i < (req); ++i) {
    k1[i] = curr.front();
    k2[req - i - 1] = curr.back();
    curr.pop_front();
    curr.pop_back();
  }
  for (int i = (0); i < (req); ++i) {
    ans.push_back({k1[i], k2[i]});
  }
  return curr;
}
int main() {
  mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> k;
  int a, b;
  for (int i = (0); i < (n - 1); ++i) {
    cin >> a >> b;
    a--;
    b--;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  weary(0);
  ll mn = 0;
  ll mx = 0;
  for (int i = (1); i < (n); ++i) {
    mn += (val[i] & 1);
    mx += val[i];
  }
  if (k > mx || k < mn || (k & 1) ^ (mx & 1)) {
    cout << "NO\n";
    exit(0);
  }
  cout << "YES\n";
  int l = 0;
  int r = n / 2;
  ll w = 0;
  while (l < r) {
    int mid = (l + r) >> 1;
    ll num = 0;
    for (int i = (1); i < (n); ++i) {
      if (val[i] <= mid)
        num += val[i];
      else {
        if ((val[i] & 1) ^ (mid & 1))
          num += mid - 1;
        else
          num += mid;
      }
    }
    if (num >= k) {
      r = mid;
      w = num;
    } else {
      l = mid + 1;
    }
  }
  for (int i = (1); i < (n); ++i) {
    if (val[i] > l) {
      if ((val[i] & 1) ^ (l & 1)) {
        val[i] = l - 1;
      } else {
        val[i] = l;
      }
    }
    if (w > k && val[i] == l) {
      val[i] -= 2;
      w -= 2;
    }
  }
  geniosity(0);
  for (auto p : ans) {
    cout << (p.first + 1) << " " << (p.second + 1) << "\n";
  }
  return 0;
}