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;
template <typename T>
ostream &operator<<(ostream &s, const vector<T> &c) {
  s << "[ ";
  for (auto it : c) s << it << " ";
  s << "\b]\n";
  return s;
}
template <typename T>
ostream &operator<<(ostream &s, const pair<int, T> &c) {
  s << "[ ";
  cout << c.first << " , " << c.second << " ] ";
  return s;
}
const int maxn = 123456;
int n;
long long k;
vector<int> E[maxn];
int sz[maxn];
int a[maxn];
int b[maxn];
int dep[maxn];
int f[maxn];
int ptr[maxn];
long long ans;
vector<pair<int, int> > que[maxn];
void input() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> k;
  for (int i = 1; i <= n - 1; ++i) {
    int x, y;
    cin >> x >> y;
    E[x].push_back(y);
    E[y].push_back(x);
  }
}
pair<int, int> cen;
int c;
vector<int> s;
void dfs(int cur, int fa) {
  int now = 0;
  sz[cur] = 1;
  for (auto x : E[cur])
    if (x != fa) {
      dfs(x, cur);
      sz[cur] += sz[x];
      now = max(now, sz[x]);
    }
  now = max(now, n - sz[cur]);
  cen = min(cen, make_pair(now, cur));
}
void dfs1(int cur, int fa) {
  f[cur] = fa;
  dep[cur] = dep[fa] + 1;
  sz[cur] = 1;
  for (auto x : E[cur])
    if (x != fa) {
      dfs1(x, cur);
      sz[cur] += sz[x];
      b[cur] += a[x];
      if (cur == c) s.push_back(x);
    }
  a[cur] = sz[cur] & 1;
  b[cur] += 1 - a[cur];
  ans += a[cur];
}
void dfs2(int cur, int fa, int son) {
  for (int i = 1; i <= b[cur] / 2; ++i)
    que[son].push_back(make_pair(dep[cur], cur));
  for (auto x : E[cur])
    if (x != fa) dfs2(x, cur, son);
}
void dfs3(int cur, int fa) {
  a[cur] = 1 - b[cur];
  for (auto x : E[cur])
    if (x != fa) {
      dfs3(x, cur);
      a[cur] += a[x];
    }
}
struct lst {
  int val;
  lst *nxt, *las;
};
priority_queue<pair<int, int> > pq;
lst *ls[maxn];
void dfs4(int cur, int fa) {
  ls[cur] = new lst();
  ls[cur]->val = cur;
  ls[cur]->nxt = NULL;
  ls[cur]->las = ls[cur];
  int lca = 1;
  for (auto x : E[cur])
    if (x != fa) {
      dfs4(x, cur);
      lca += a[x];
    }
  for (auto x : E[cur])
    if (x != fa)
      if (a[x]) pq.push(make_pair(a[x], x));
  pq.push(make_pair(1, cur));
  lca -= a[cur];
  for (int i = 1; i <= lca / 2; ++i) {
    auto x = pq.top();
    pq.pop();
    auto y = pq.top();
    pq.pop();
    cout << ls[x.second]->val << ' ' << ls[y.second]->val << '\n';
    if (ls[x.second]->nxt) ls[x.second]->nxt->las = ls[x.second]->las;
    ls[x.second] = ls[x.second]->nxt;
    if (ls[y.second]->nxt) ls[y.second]->nxt->las = ls[y.second]->las;
    ls[y.second] = ls[y.second]->nxt;
    if (x.first > 1) pq.push(make_pair(x.first - 1, x.second));
    if (y.first > 1) pq.push(make_pair(y.first - 1, y.second));
  }
  lst *dum = new lst();
  dum->nxt = ls[cur];
  lst *end = dum;
  while (end->nxt) end = end->nxt;
  for (auto x : E[cur])
    if (x != fa)
      if (ls[x]) {
        end->nxt = ls[x];
        end = ls[x]->las;
      }
  ls[cur] = dum->nxt;
  if (ls[cur]) ls[cur]->las = end;
  while (!pq.empty()) pq.pop();
}
priority_queue<pair<int, int>, vector<pair<int, int> >,
               greater<pair<int, int> > >
    PQ;
void solve() {
  cen = make_pair(maxn, 0);
  dfs(1, 0);
  c = cen.second;
  dfs1(c, 0);
  if (ans > k || ((ans ^ k) & 1)) {
    cout << "NO\n";
    return;
  }
  for (auto x : s) {
    dfs2(x, c, x);
    sort(begin(que[x]), end(que[x]));
    PQ.push(make_pair(a[x], x));
  }
  while (!PQ.empty()) {
    auto x = PQ.top();
    PQ.pop();
    if (a[x.second] != x.first) continue;
    if (ptr[x.second] == que[x.second].size()) continue;
    auto y = que[x.second][ptr[x.second]++];
    if (ans + (y.first - 1) * 2 >= k) {
      int cur = y.second;
      b[y.second] -= 2;
      while (ans < k) {
        ans += 2;
        cur = f[cur];
      }
      b[cur] += 2;
      break;
    }
    b[y.second] -= 2;
    ans += (y.first - 1) * 2;
    b[c] += 2;
    a[x.second] += 2;
    if (a[x.second] != sz[x.second]) PQ.push(make_pair(a[x.second], x.second));
  }
  dfs3(c, 0);
  if (ans != k) {
    cout << "NO\n";
    return;
  }
  cout << "YES\n";
  dfs4(c, 0);
}
int main() {
  input();
  solve();
}