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 N = 1e5 + 1;
vector<int> adj[N];
int val[N];
int sub[N];
void dfs_sub(int u, int p) {
  sub[u] = 1;
  for (auto c : adj[u]) {
    if (c != p) {
      dfs_sub(c, u);
      sub[u] += sub[c];
    }
  }
}
list<int> dfs_print(int u, int p) {
  list<int> all = {u};
  for (auto c : adj[u]) {
    if (c != p) {
      all.splice(all.end(), dfs_print(c, u));
    }
  }
  int cnt = (int(all.size()) - val[u]) / 2;
  assert(cnt >= 0);
  vector<array<int, 2>> pairs(cnt);
  for (int i = 0; i < cnt; ++i) {
    pairs[i][0] = all.front();
    pairs[cnt - 1 - i][1] = all.back();
    all.pop_front();
    all.pop_back();
  }
  for (auto [a, b] : pairs) {
    cout << a << " " << b << "\n";
  }
  assert(int(all.size()) == val[u]);
  return all;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  int64_t k;
  cin >> n >> k;
  for (int i = 0; i < n - 1; ++i) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  dfs_sub(1, 0);
  int64_t mn = 0;
  int64_t mx = 0;
  for (int i = 2; i <= n; ++i) {
    val[i] = min(sub[i], n - sub[i]);
    mn += val[i] % 2;
    mx += val[i];
  }
  if (k < mn || k > mx || k % 2 != mn % 2) {
    cout << "NO\n";
    exit(0);
  }
  cout << "YES\n";
  int lo = 0;
  int hi = n / 2;
  int64_t cost = -1;
  while (lo <= hi) {
    int mid = (lo + hi) / 2;
    int64_t res = 0;
    for (int i = 2; i <= n; ++i) {
      if (val[i] <= mid) {
        res += val[i];
      } else {
        res += mid - (val[i] % 2 != mid % 2);
      }
    }
    if (res >= k) {
      hi = mid - 1;
      cost = res;
    } else {
      lo = mid + 1;
    }
  }
  assert(cost >= k);
  for (int i = 2; i <= n; ++i) {
    if (val[i] > lo) {
      val[i] = lo - (val[i] % 2 != lo % 2);
    }
    if (val[i] == lo && cost > k) {
      val[i] -= 2;
      cost -= 2;
    }
  }
  assert(cost == k);
  dfs_print(1, 0);
}