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 maxn = 100010, mod = 998244353;
inline long long read() {
  char ch = getchar();
  long long x = 0, f = 0;
  while (ch < '0' || ch > '9') f |= ch == '-', ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  return f ? -x : x;
}
int n, el, head[maxn], to[maxn * 2], nxt[maxn * 2], sz[maxn], son[maxn], rt,
    dep[maxn], tmp[maxn], tl, ans[maxn][2], al, fa[maxn];
long long k, lwr, upr;
vector<int> v[maxn], sss[maxn];
bool del[maxn];
struct cmp1 {
  bool operator()(int x, int y) { return sz[x] < sz[y]; }
};
priority_queue<int, vector<int>, cmp1> pq;
inline void add(int u, int v) {
  to[++el] = v;
  nxt[el] = head[u];
  head[u] = el;
}
inline bool cmp(int x, int y) { return dep[x] < dep[y]; }
void dfs(int u, int f) {
  sz[u] = 1;
  for (int i = head[u]; i; i = nxt[i]) {
    int v = to[i];
    if (v == f) continue;
    dfs(v, u);
    sz[u] += sz[v];
    son[u] = max(son[u], sz[v]);
  }
  son[u] = max(son[u], n - sz[u]);
  if (son[u] <= n / 2) rt = u;
}
void dfs1(int u, int f, int hhh) {
  if (hhh && !del[u]) v[hhh].push_back(u);
  if (!del[u])
    sz[u] = 1;
  else
    sz[u] = 0;
  dep[u] = f ? dep[f] + 1 : 0;
  sss[u].clear();
  fa[u] = f;
  for (int i = head[u]; i; i = nxt[i]) {
    int v = to[i];
    if (v == f) continue;
    if (!f) ::v[v].clear();
    dfs1(v, u, f ? hhh : v);
    sz[u] += sz[v];
    sss[u].push_back(v);
    if (!f) {
      if (sz[v]) pq.push(v);
      sort(::v[v].begin(), ::v[v].end(), cmp);
    }
  }
}
int main() {
  n = read();
  k = read();
  for (int i = (1); i <= (n - 1); i++) {
    int u = read(), v = read();
    add(u, v);
    add(v, u);
  }
  dfs(1, 0);
  dfs1(rt, 0, 0);
  for (int i = (1); i <= (n); i++) lwr += sz[i] % 2, upr += dep[i];
  if (k < lwr || k > upr || k % 2 != upr % 2) return puts("NO"), 0;
  puts("YES");
  k = (upr - k) / 2;
  while (k) {
    int u = pq.top();
    pq.pop();
    if (sz[u] < 2) puts("shit0");
    sz[u] -= 2;
    pq.push(u);
    while (sss[v[u].back()].empty() || dep[v[u].back()] > k) v[u].pop_back();
    int x = v[u].back();
    if (sss[x].empty())
      puts("shit0.1");
    else if (del[sss[x].back()])
      puts("shit0.25");
    del[ans[++al][0] = sss[x].back()] = true;
    while (!sss[x].empty() && del[sss[x].back()]) sss[x].pop_back();
    if (sss[x].empty()) {
      if (del[x]) puts("shit0.5");
      del[ans[al][1] = x] = true;
      while (!sss[fa[x]].empty() && del[sss[fa[x]].back()])
        sss[fa[x]].pop_back();
    } else {
      if (del[sss[x].back()]) puts("shit0.75");
      del[ans[al][1] = sss[x].back()] = true, sss[x].pop_back();
      while (!sss[x].empty() && del[sss[x].back()]) sss[x].pop_back();
    }
    k -= dep[x];
  }
  while (!pq.empty()) pq.pop();
  dfs1(rt, 0, 0);
  sz[rt] = 1;
  v[rt].push_back(rt);
  pq.push(rt);
  while (!pq.empty()) {
    int u = pq.top();
    pq.pop();
    if (pq.empty()) puts("shit1");
    int v = pq.top();
    pq.pop();
    if (::v[v].empty()) puts("shit2");
    ans[++al][0] = ::v[u].back();
    ::v[u].pop_back();
    sz[u]--;
    if (!::v[u].empty()) pq.push(u);
    ans[al][1] = ::v[v].back();
    ::v[v].pop_back();
    sz[v]--;
    if (!::v[v].empty()) pq.push(v);
  }
  if (al != n / 2) puts("shit3");
  for (int i = (1); i <= (al); i++) printf("%d %d\n", ans[i][0], ans[i][1]);
}