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 sz = 1e5 + 10;
vector<pair<int, int> > sv[sz], edges[2];
map<int, int> ma;
int n, si[sz], tin[sz], timer = 0;
long long maxx = 0, minn = 0;
void dfs(int v, int pr) {
  si[v] = 1, tin[v] = timer++;
  ma[tin[v]] = v + 1;
  for (int a = 0; a < sv[v].size(); a++) {
    int ne = sv[v][a].first, i = sv[v][a].second;
    if (ne != pr) {
      dfs(ne, v), si[v] += si[ne];
      int w = min(si[ne], n - si[ne]);
      maxx += w, minn += w & 1;
      edges[w & 1].push_back({w, i});
    }
  }
}
int w[sz];
void dfs2(int v, int pr, int prw) {
  set<pair<int, int>, greater<pair<int, int> > > se;
  se.insert({1, tin[v]});
  int su = 1 - prw;
  for (int a = 0; a < sv[v].size(); a++) {
    int ne = sv[v][a].first, i = sv[v][a].second;
    if (ne != pr) {
      dfs2(ne, v, w[i]), su += w[i];
      se.insert({w[i], tin[ne]});
    }
  }
  for (int a = 0; a < su; a += 2) {
    pair<int, int> x = (*se.begin());
    se.erase(se.begin());
    pair<int, int> y = (*se.begin());
    se.erase(se.begin());
    auto it = ma.lower_bound(x.second);
    int u = (*it).second;
    ma.erase(it);
    it = ma.lower_bound(y.second);
    int v = (*it).second;
    ma.erase(it);
    printf("\n%d %d", u, v);
    x.first--, se.insert(x);
    y.first--, se.insert(y);
  }
}
int main() {
  long long k;
  cin >> n >> k;
  for (int a = 0; a < n - 1; a++) {
    int u, v;
    scanf("%d%d", &u, &v);
    u--, v--;
    sv[u].push_back({v, a});
    sv[v].push_back({u, a});
  }
  dfs(0, 0);
  if (k >= minn and k <= maxx and (k & 1) == (minn & 1)) {
    k -= minn;
    for (int i = 0; i < 2; i++) sort(edges[i].begin(), edges[i].end());
    int yk[2] = {0, 0};
    for (int a = 2;; a++) {
      int i = a & 1;
      while (yk[i] < edges[i].size() and edges[i][yk[i]].first < a) yk[i]++;
      if (k <= (edges[i].size() - yk[i]) * 2) {
        for (int b = yk[i]; b < edges[i].size(); b++) {
          if (k)
            edges[i][b].first = a, k -= 2;
          else
            edges[i][b].first = a - 2;
        }
        for (int b = yk[i ^ 1]; b < edges[i ^ 1].size(); b++) {
          edges[i ^ 1][b].first = a - 1;
        }
        for (int i = 0; i < 2; i++) {
          for (int b = 0; b < edges[i].size(); b++) {
            w[edges[i][b].second] = edges[i][b].first;
          }
        }
        break;
      } else
        k -= (edges[i].size() - yk[i]) * 2;
    }
    cout << "YES";
    dfs2(0, 0, 0);
  } else
    cout << "NO";
}