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 max_n = 100111, inf = 1000111222;
struct state {
  int v, pos, cnt;
  state(int v, int pos, int cnt) : v(v), pos(pos), cnt(cnt) {}
};
int n, sz[max_n];
long long k;
vector<int> g[max_n], a[max_n];
vector<state> all;
void dfs(int v, int p) {
  sz[v] = 1;
  for (int i = 0; i < g[v].size(); ++i) {
    if (g[v][i] == p) {
      swap(g[v][i], g[v].back());
      g[v].pop_back();
      --i;
      continue;
    }
    dfs(g[v][i], v);
    sz[v] += sz[g[v][i]];
  }
  for (int i = 0; i < g[v].size(); ++i) {
    all.push_back({v, i, min(sz[g[v][i]], n - sz[g[v][i]])});
  }
}
long long get_sum(int x) {
  long long res = 0;
  for (const state &s : all) {
    int y = s.cnt;
    if (y > x) {
      if (y % 2 == x % 2) {
        y = x;
      } else {
        y = x - 1;
      }
    }
    res += y;
  }
  return res;
}
void proc(int x) {
  int mx = 0;
  for (state &s : all) {
    if (s.cnt > x) {
      if (s.cnt % 2 == x % 2) {
        s.cnt = x;
      } else {
        s.cnt = x - 1;
      }
    }
    k -= s.cnt;
    mx = max(mx, s.cnt);
  }
  for (state &s : all) {
    if (s.cnt == mx && k < 0) {
      s.cnt -= 2;
      k += 2;
    }
  }
}
vector<int> ids[max_n];
int get(int id) {
  int res = ids[id].back();
  ids[id].pop_back();
  return res;
}
void solve(int v, int need) {
  int tot = 0;
  priority_queue<pair<int, int>> q;
  for (int i = 0; i < g[v].size(); ++i) {
    solve(g[v][i], a[v][i]);
    assert(ids[g[v][i]].size() == a[v][i]);
    tot += a[v][i];
    q.push({a[v][i], g[v][i]});
  }
  ids[v].push_back(v);
  q.push({1, v});
  while (tot > need) {
    tot -= 2;
    pair<int, int> p1 = q.top();
    q.pop();
    pair<int, int> p2 = q.top();
    q.pop();
    printf("%d %d\n", get(p1.second) + 1, get(p2.second) + 1);
    --p1.first;
    --p2.first;
    if (p1.first) {
      q.push(p1);
    }
    if (p2.first) {
      q.push(p2);
    }
  }
  for (int to : g[v]) {
    if (ids[to].size() > ids[v].size()) {
      ids[v].swap(ids[to]);
    }
    for (int id : ids[to]) {
      ids[v].push_back(id);
    }
  }
}
int main() {
  scanf("%d%I64d", &n, &k);
  for (int i = 1; i < n; ++i) {
    int u, v;
    scanf("%d%d", &u, &v);
    --u;
    --v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  dfs(0, -1);
  long long tot_mx = 0, tot_mn = 0;
  for (const auto &s : all) {
    tot_mx += s.cnt;
    tot_mn += s.cnt % 2;
  }
  if (k < tot_mn || k > tot_mx || k % 2 != tot_mn % 2) {
    puts("NO");
    return 0;
  }
  puts("YES");
  int l = 0, r = n;
  while (r - l > 1) {
    int mid = (l + r) / 2;
    if (get_sum(mid) < k) {
      l = mid;
    } else {
      r = mid;
    }
  }
  proc(r);
  for (int i = 0; i < n; ++i) {
    a[i].resize(g[i].size());
  }
  for (const state &s : all) {
    a[s.v][s.pos] = s.cnt;
  }
  solve(0, 0);
  return 0;
}