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 + 7;
int n, ind;
long long k;
int sz[N], dl[N], dr[N], tr[N], dep[N];
vector<int> ve[N], vec[N];
set<int> s;
int main() {
  scanf("%d%lld", &n, &k);
  for (int i = 1, a, b; i < n; ++i)
    scanf("%d%d", &a, &b), ve[a].push_back(b), ve[b].push_back(a);
  int rt, mnp = n;
  function<void(int, int)> dfs1 = [&](int x, int fa) {
    sz[x] = 1;
    int mxp = 0;
    for (auto to : ve[x])
      if (to != fa) dfs1(to, x), mxp = max(mxp, sz[to]), sz[x] += sz[to];
    mxp = max(mxp, n - sz[x]);
    if (mxp < mnp) mnp = mxp, rt = x;
  };
  function<void(int, int)> dfs2 = [&](int x, int fa) {
    sz[x] = 1;
    dl[x] = ++ind;
    tr[ind] = x;
    s.insert(ind);
    for (auto to : ve[x])
      if (to != fa) dep[to] = dep[x] + 1, dfs2(to, x), sz[x] += sz[to];
    dr[x] = ind;
  };
  dfs1(1, 0);
  dfs2(rt, 0);
  long long mn = 0, mx = 0;
  for (int i = 1; i <= n; ++i)
    if (i != rt) mn += sz[i] & 1, mx += sz[i];
  if (k < mn || k > mx || (mx - k & 1)) return puts("NO"), 0;
  puts("YES");
  function<void(int, int, int)> dfs3 = [&](int x, int fa, int r) {
    vec[r].push_back(x);
    for (auto to : ve[x])
      if (to != fa) dfs3(to, x, r);
  };
  priority_queue<pair<int, int>> p;
  vector<pair<int, int>> ans;
  for (auto to : ve[rt])
    dfs3(to, rt, to),
        sort(vec[to].begin(), vec[to].end(),
             [](int a, int b) { return dep[a] < dep[b]; }),
        p.push(make_pair(sz[to], to));
  while (k != mx) {
    long long det = mx - k >> 1;
    int id = p.top().second;
    sz[id] -= 2;
    p.pop();
    p.push(make_pair(sz[id], id));
    function<bool(int)> check = [&](int x) {
      auto it = s.lower_bound(dl[x]);
      if (it++ == s.end()) return 0;
      if (it == s.end() || *it > dr[x]) return 0;
      return 1;
    };
    while (!check(vec[id].back()) || dep[vec[id].back()] > det)
      vec[id].pop_back();
    mx -= dep[vec[id].back()] << 1;
    auto it = s.lower_bound(dl[vec[id].back()]);
    int x = *it;
    s.erase(it);
    it = s.lower_bound(dl[vec[id].back()]);
    int y = *it;
    s.erase(it);
    ans.push_back(make_pair(tr[x], tr[y]));
  }
  ind = 0;
  function<void(int, int)> dfs4 = [&](int x, int fa) {
    if (s.find(dl[x]) != s.end()) dl[x] = ++ind, tr[ind] = x;
    for (auto to : ve[x])
      if (to != fa) dfs4(to, x);
  };
  dfs4(rt, 0);
  for (int i = 1; i <= ind >> 1; ++i)
    ans.push_back(make_pair(tr[i], tr[i + (ind >> 1)]));
  for (auto p : ans) printf("%d %d\n", p.first, p.second);
  return 0;
}