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 long long MOD = 1e9 + 7;
const long long INF = 1e9;
const long long INFLL = 1e18;
using namespace std;
int cx[4] = {0, 0, 1, -1};
int cy[4] = {-1, 1, 0, 0};
string Yes[2] = {"No\n", "Yes\n"};
string YES[2] = {"NO\n", "YES\n"};
string Possible[2] = {"Impossible\n", "Possible\n"};
string POSSIBLE[2] = {"IMPOSSIBLE\n", "POSSIBLE\n"};
void dfs(int v, int p, int &n, int &c, vector<vector<int> > &g,
         vector<int> &sz) {
  sz[v] = 1;
  for (auto u : g[v])
    if (u != p) dfs(u, v, n, c, g, sz), sz[v] += sz[u];
  if (c == -1 && sz[v] * 2 >= n) c = v;
}
const int N = 5e5;
vector<int> child[N];
void dfs2(int v, int p, int pnt,
          vector<set<pair<int, int>, greater<pair<int, int> > > > &Vertices,
          vector<vector<int> > &g, vector<int> &dist) {
  child[p].push_back(v);
  dist[v] = dist[p] + 1;
  Vertices[pnt].insert({dist[v], v});
  for (auto u : g[v])
    if (u != p) dfs2(u, v, pnt, Vertices, g, dist);
}
void dfs3(int v, int p, vector<int> &used, vector<int> &order,
          vector<vector<int> > &g) {
  if (!used[v]) order.push_back(v);
  for (auto u : g[v])
    if (u != p) dfs3(u, v, used, order, g);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n;
  long long k;
  cin >> n >> k;
  vector<vector<int> > g(n);
  vector<int> sz(n);
  for (int(i) = 0; (i) != (n - 1); (i)++) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    g[a].push_back(b), g[b].push_back(a);
  }
  int c = -1, d = -1;
  dfs(0, 0, n, c, g, sz);
  dfs(c, c, n, d, g, sz);
  long long cap = accumulate((sz).begin(), (sz).end(), -1ll * n);
  long long mn = 0;
  for (int(i) = 0; (i) != (n); (i)++) mn += sz[i] % 2;
  mn -= sz[c] % 2;
  if (k % 2 == cap % 2 && mn <= k && k <= cap) {
    cout << "YES\n";
    int m = g[c].size();
    set<pair<int, int>, greater<pair<int, int> > > S;
    int pnt = 0;
    for (auto u : g[c]) S.insert({sz[u], pnt}), pnt++;
    vector<set<pair<int, int>, greater<pair<int, int> > > > Vertices(m);
    vector<int> dist(n);
    pnt = 0;
    for (auto u : g[c]) dfs2(u, c, pnt, Vertices, g, dist), pnt++;
    vector<int> used(n);
    while (cap > k) {
      long long rem = cap - k;
      auto it = *(S.begin());
      S.erase(S.begin());
      it.first -= 2;
      S.insert(it);
      int tree = it.second;
      auto &Set = Vertices[tree];
      while (Set.size()) {
        auto it = *Set.begin();
        if (2 * it.first > rem) {
          Set.erase(Set.begin());
          continue;
        }
        int v = it.second;
        int alpha = -1, beta = -1;
        while (child[v].size()) {
          int u = child[v].back();
          if (!used[u]) {
            used[u] = 1;
            if (alpha == -1)
              alpha = u;
            else
              beta = u;
            child[v].pop_back();
          } else {
            child[v].pop_back();
          }
          if (beta != -1) break;
        }
        if (alpha != -1 && beta != -1) {
          cap -= 2 * it.first;
          cout << alpha + 1 << " " << beta + 1 << "\n";
          break;
        } else if (alpha != -1) {
          cap -= 2 * it.first;
          cout << alpha + 1 << " " << v + 1 << "\n";
          used[v] = 1;
          break;
        } else {
          Set.erase(Set.begin());
        }
      }
    }
    vector<int> order;
    dfs3(c, c, used, order, g);
    int D = order.size() / 2;
    for (int i = 0; i < D; i++)
      cout << order[i] + 1 << " " << order[i + D] + 1 << "\n";
  } else {
    cout << "NO";
  }
}