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;
int n;
int qtdMinPair, curTime;
int anc[MAXN];
int match[MAXN];
int minMatch[MAXN][2], LCA[MAXN];
int sub[MAXN], depth[MAXN], tin[MAXN];
long long int k;
vector<int> adj[MAXN];
vector<int> minPairSub[MAXN];
bool cmpTin(int i, int j) { return tin[i] < tin[j]; }
bool cmpDepth(int i, int j) { return depth[LCA[i]] < depth[LCA[j]]; }
void DFSInit(int cur, int p, int d) {
  anc[cur] = p;
  sub[cur] = 1;
  depth[cur] = d;
  tin[cur] = ++curTime;
  for (int i = 0; i < (int)adj[cur].size(); i++) {
    int viz = adj[cur][i];
    if (viz == p) continue;
    DFSInit(viz, cur, d + 1);
    sub[cur] += sub[viz];
  }
}
void DFSPairingMin(int cur, int p, int indSubtree) {
  vector<int> nodes;
  for (int i = 0; i < (int)adj[cur].size(); i++) {
    int viz = adj[cur][i];
    if (viz == p) continue;
    if (sub[viz] % 2 == 1) nodes.push_back(viz);
    int newInd = indSubtree;
    if (newInd == -1) newInd = i;
    DFSPairingMin(viz, cur, newInd);
  }
  if (sub[cur] % 2 == 0) nodes.push_back(cur);
  for (int i = 0; i < (int)nodes.size(); i += 2) {
    qtdMinPair++;
    LCA[qtdMinPair] = cur;
    minMatch[qtdMinPair][0] = nodes[i];
    minMatch[qtdMinPair][1] = nodes[i + 1];
    if (indSubtree != -1) minPairSub[indSubtree].push_back(qtdMinPair);
  }
}
void makeGreedyPairing() {
  vector<int> remain;
  for (int i = 1; i <= n; i++)
    if (match[i] == 0) remain.push_back(i);
  sort(remain.begin(), remain.end(), cmpTin);
  int qtdRemain = (int)remain.size();
  for (int i = 0; i < qtdRemain / 2; i++) {
    int A = remain[i];
    int B = remain[i + qtdRemain / 2];
    match[A] = B;
    match[B] = A;
  }
}
int findCentroid(int cur, int p) {
  for (int i = 0; i < (int)adj[cur].size(); i++) {
    int viz = adj[cur][i];
    if (viz == p) continue;
    if (sub[viz] > n / 2) return findCentroid(viz, cur);
  }
  return cur;
}
void printMatching() {
  printf("YES\n");
  for (int i = 1; i <= n; i++)
    if (i < match[i]) printf("%d %d\n", i, match[i]);
  exit(0);
}
int main() {
  scanf("%d %lld", &n, &k);
  for (int i = 1; i < n; i++) {
    int U, V;
    scanf("%d %d", &U, &V);
    adj[U].push_back(V);
    adj[V].push_back(U);
  }
  DFSInit(1, 1, 0);
  int root = findCentroid(1, 1);
  DFSInit(root, root, 0);
  long long int minK, maxK;
  minK = maxK = 0;
  for (int i = 1; i <= n; i++) minK += sub[i] % 2, maxK += depth[i];
  if (k < minK || maxK < k || k % 2 != minK % 2) {
    printf("NO\n");
    return 0;
  }
  DFSPairingMin(root, root, -1);
  set<pair<int, int> > subtrees;
  for (int i = 0; i < (int)adj[root].size(); i++)
    subtrees.insert({-sub[adj[root][i]], i});
  for (int i = 0; i < n; i++)
    sort(minPairSub[i].begin(), minPairSub[i].end(), cmpDepth);
  while (maxK > k) {
    int ind = subtrees.begin()->second;
    subtrees.erase(subtrees.begin());
    sub[adj[root][ind]] -= 2;
    subtrees.insert({-sub[adj[root][ind]], ind});
    if (minPairSub[ind].empty()) break;
    int curPair = minPairSub[ind].back();
    minPairSub[ind].pop_back();
    if (maxK - 2 * depth[LCA[curPair]] > k) {
      maxK -= 2 * depth[LCA[curPair]];
      int A = minMatch[curPair][0];
      int B = minMatch[curPair][1];
      match[A] = B;
      match[B] = A;
      continue;
    }
    int curLCA = LCA[curPair];
    int newLCADepth = (maxK - k) / 2;
    while (depth[curLCA] > newLCADepth) curLCA = anc[curLCA];
    int A = minMatch[curPair][0], B = curLCA;
    match[A] = B;
    match[B] = A;
    break;
  }
  makeGreedyPairing();
  printMatching();
}