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>
const int MAXN = 1e5 + 10;
using namespace std;
int tree[MAXN * 4];
int bestIndex[MAXN * 4];
void build(int pos, int l, int r) {
  tree[pos] = r - l + 1;
  if (l == r) return (void)(bestIndex[pos] = l);
  int mid = (l + r) >> 1;
  build(pos << 1, l, mid);
  build(pos << 1 | 1, mid + 1, r);
  bestIndex[pos] = bestIndex[pos << 1];
}
int findOn(int pos, int l, int r, int beg, int en) {
  if (l > en || r < beg || tree[pos] == 0) return -1;
  if (l >= beg && r <= en) return bestIndex[pos];
  int mid = (l + r) >> 1;
  int al = findOn(pos << 1, l, mid, beg, en);
  int ar = findOn(pos << 1 | 1, mid + 1, r, beg, en);
  return (al > ar) ? al : ar;
}
void erasing(int pos, int l, int r, int idx) {
  tree[pos]--;
  if (l == r) return (void)(bestIndex[pos] = -1);
  int mid = (l + r) >> 1;
  if (idx <= mid)
    erasing(pos << 1, l, mid, idx);
  else
    erasing(pos << 1 | 1, mid + 1, r, idx);
  bestIndex[pos] = bestIndex[pos << 1];
  if (bestIndex[pos << 1 | 1] > bestIndex[pos])
    bestIndex[pos] = bestIndex[pos << 1 | 1];
}
int n, cn;
int deg[MAXN], parent[MAXN];
int tin[MAXN], tout[MAXN], sub[MAXN], queuePointer[MAXN];
int bit[MAXN], dist[MAXN], tinBackwards[MAXN];
vector<int> adj[MAXN];
long long k, kmin, kmax;
vector<pair<int, int> > ans;
vector<vector<int> > queues;
set<pair<int, int> > s;
set<pair<int, pair<int, int> > > myAlternatives[MAXN];
void dfs1(int x, int father = -1) {
  sub[x] = 1;
  for (auto e : adj[x]) {
    if (e == father) continue;
    dfs1(e, x);
    sub[x] += sub[e];
  }
}
int dfs2(int x, int father) {
  for (auto e : adj[x])
    if (e != father && sub[e] > n / 2) return dfs2(e, x);
  return x;
}
int currTime;
void dfs3(int x) {
  tin[x] = tout[x] = ++currTime;
  tinBackwards[currTime] = x;
  sub[x] = 1;
  for (auto e : adj[x]) {
    if (e == parent[x]) continue;
    deg[x]++;
    if (x == cn) queues.push_back(vector<int>());
    parent[e] = x;
    dist[e] = dist[x] + 1;
    dfs3(e);
    if (x == cn) s.insert(make_pair(-sub[e], (int)(queues.size()) - 1));
    kmax += (long long)(sub[e]);
    kmin += (sub[e] & 1);
    sub[x] += sub[e];
    tout[x] = tout[e];
  }
  if (deg[x] == 0) queues.back().push_back(x);
}
void createEdge(int x) {
  set<pair<int, pair<int, int> > > &ptr = myAlternatives[x];
  auto a = *ptr.begin();
  ptr.erase(ptr.begin());
  auto b = *ptr.begin();
  ptr.erase(ptr.begin());
  int toEraseA = findOn(1, 1, n, a.second.first, a.second.second);
  int toEraseB = findOn(1, 1, n, b.second.first, b.second.second);
  ans.push_back(make_pair(tinBackwards[toEraseA], tinBackwards[toEraseB]));
  erasing(1, 1, n, toEraseA);
  erasing(1, 1, n, toEraseB);
  a.first += 1;
  b.first += 1;
  if (a.first < 0) ptr.insert(a);
  if (b.first < 0) ptr.insert(b);
}
int main() {
  scanf("%d %lld", &n, &k);
  for (int i = 0, a, b; i < n - 1; i++) {
    scanf("%d %d", &a, &b);
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  dfs1(1, -1);
  cn = dfs2(1, -1);
  dfs3(cn);
  if ((k & 1) != (kmax & 1) || k < kmin || k > kmax) {
    printf("NO\n");
    return 0;
  }
  kmax -= k;
  kmax >>= 1;
  build(1, 1, n);
  for (int i = 1; i <= n; i++)
    myAlternatives[i].insert(make_pair(-1, make_pair(tin[i], tin[i])));
  while ((int)(s.size())) {
    pair<int, int> topo = *s.begin();
    s.erase(s.begin());
    int subtreeSize = -topo.first;
    int queueIndex = topo.second;
    int &ptr = queuePointer[queueIndex];
    while (ptr < (int)(queues[queueIndex].size())) {
      int x = queues[queueIndex][ptr];
      if (dist[x] > kmax || (int)(myAlternatives[x].size()) <= 1) {
        int quantityPeople = 0;
        for (auto e : myAlternatives[x]) quantityPeople += e.first;
        myAlternatives[x].clear();
        if (quantityPeople != 0)
          myAlternatives[parent[x]].insert(
              make_pair(quantityPeople, make_pair(tin[x], tout[x])));
        if ((--deg[parent[x]]) == 0 && cn != parent[x])
          queues[queueIndex].push_back(parent[x]);
        ptr++;
        continue;
      }
      createEdge(x);
      subtreeSize -= 2;
      kmax -= dist[x];
      break;
    }
    if (ptr < (int)(queues[queueIndex].size()))
      s.insert(make_pair(-subtreeSize, queueIndex));
  }
  while ((int)(myAlternatives[cn].size())) createEdge(cn);
  printf("YES\n");
  for (auto e : ans) printf("%d %d\n", e.first, e.second);
}