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 + 50;
int n, rt, all;
long long k;
int dep[N], sz[N];
bool ban[N];
vector<int> G[N];
void pre_dfs(int u, int fa) {
  int mx = 0;
  sz[u] = 1;
  for (int v : G[u])
    if (v != fa) pre_dfs(v, u), sz[u] += sz[v], mx = max(mx, sz[v]);
  mx = max(mx, n - sz[u]);
  if (mx < all) rt = u, all = mx;
}
void dfs(int u, int fa) {
  vector<int> T;
  sz[u] = 1;
  for (int v : G[u])
    if (v != fa) dep[v] = dep[u] + 1, dfs(v, u), sz[u] += sz[v], T.push_back(v);
  G[u] = T;
}
multiset<pair<int, int> > S[N], M;
void sub_dfs(int u, int rt) {
  if (G[u].size()) S[rt].insert(pair<int, int>(dep[u], u));
  for (int v : G[u]) sub_dfs(v, rt);
}
void cope(int r) {
  auto z = S[r].end();
  --z;
  int u = z->second, d = z->first << 1;
  S[r].erase(z);
  if (k >= d) {
    int a = -1, b = -1;
    for (int v : G[u])
      if (!ban[v]) a == -1 ? a = v : b = v;
    if (a == -1) return cope(r), void();
    if (b == -1)
      b = u;
    else
      S[r].insert(pair<int, int>(d >> 1, u));
    cout << a << " " << b << '\n';
    ban[a] = ban[b] = true;
    sz[r] -= 2;
    k -= d;
    return;
  }
  cope(r);
}
vector<int> q;
void fin_dfs(int u) {
  if (!ban[u]) q.push_back(u);
  for (int v : G[u]) fin_dfs(v);
}
int main() {
  scanf("%d%lld", &n, &k);
  for (int i = 1, u, v; i < n; i++)
    scanf("%d%d", &u, &v), G[u].push_back(v), G[v].push_back(u);
  all = n;
  pre_dfs(1, 0), dfs(rt, 0);
  long long L = 0, R = 0;
  for (int i = 1; i <= n; i++)
    if (i != rt) L += sz[i] & 1, R += sz[i];
  if (k < L || k > R) return puts("NO"), 0;
  if ((R - k) & 1) return puts("NO"), 0;
  k = R - k;
  for (int v : G[rt]) {
    sub_dfs(v, v);
    if (sz[v] > 1) M.insert(pair<int, int>(sz[v], v));
  }
  puts("YES");
  while (k > 0) {
    auto z = M.end();
    --z;
    int r = z->second;
    M.erase(z);
    cope(r);
    if (sz[r] > 1) M.insert(pair<int, int>(sz[r], r));
  }
  fin_dfs(rt);
  int r = q.size() >> 1;
  for (int i = 0; i < r; i++) cout << q[i] << " " << q[i + r] << '\n';
  return 0;
}