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;
using LL = long long;
int main() {
  int N;
  LL K;
  cin >> N >> K;
  vector<vector<int> > adj(N);
  for (int i = 0; i < N - 1; ++i) {
    int u, v;
    cin >> u >> v;
    --u, --v;
    adj[u].emplace_back(v);
    adj[v].emplace_back(u);
  }
  vector<int> sz(N);
  function<void(int, int)> dfs1 = [&](int u, int p) {
    sz[u] = 1;
    for (int v : adj[u])
      if (v != p) {
        dfs1(v, u);
        sz[u] += sz[v];
      }
  };
  dfs1(0, -1);
  int root = 0;
  for (int i = 1; i < N; ++i)
    if (sz[i] >= N / 2 && sz[i] < sz[root]) root = i;
  vector<int> dist(N);
  vector<int> top(N, -1);
  vector<int> par(N, -1);
  LL low = 0, high = 0;
  function<void(int, int, int)> dfs2 = [&](int u, int p, int r) {
    dist[u] = dist[p] + 1;
    top[u] = r;
    par[u] = p;
    {
      auto it = find(adj[u].begin(), adj[u].end(), p);
      adj[u].erase(it);
    }
    sz[u] = 1;
    for (int v : adj[u]) {
      dfs2(v, u, r);
      sz[u] += sz[v];
    }
    low += (sz[u] & 1);
    high += sz[u];
  };
  for (int v : adj[root]) dfs2(v, root, v);
  if (low > K || high < K || (high - K) & 1) {
    printf("NO\n");
    return 0;
  }
  set<pair<int, int> > sizes;
  for (int v : adj[root]) sizes.emplace(sz[v], v);
  vector<set<pair<int, int> > > lcas(N);
  vector<int> deg(N);
  for (int u = 0; u < N; ++u) deg[u] = (int)adj[u].size();
  for (int u = 0; u < N; ++u)
    if (u != root) {
      if (deg[u] != 0) lcas[top[u]].emplace(dist[u], u);
    }
  vector<bool> matched(N);
  function<void(int)> kill = [&](int u) {
    if (--deg[par[u]] == 0) {
      u = par[u];
      lcas[top[u]].erase(pair<int, int>(dist[u], u));
    }
  };
  printf("YES\n");
  while (high > K) {
    int v = (--sizes.end())->second;
    sizes.erase(pair<int, int>(sz[v], v));
    int mdist = (--lcas[v].end())->first;
    if (high - 2 * mdist <= K) {
      int x = lcas[v].lower_bound(pair<int, int>((high - K) / 2, -1))->second;
      int y = -1;
      for (int z : adj[x])
        if (!matched[z]) {
          y = z;
          break;
        }
      high = K;
      cout << x + 1 << ' ' << y + 1 << "\n";
      matched[x] = matched[y] = true;
      break;
    } else {
      high -= 2 * mdist;
      int u = (--lcas[v].end())->second;
      vector<int> nxts;
      while (nxts.size() < 2 && adj[u].size()) {
        int w = adj[u].back();
        adj[u].pop_back();
        if (!matched[w]) {
          nxts.emplace_back(w);
        }
      }
      if (nxts.size() < 2) nxts.emplace_back(u);
      assert(nxts.size() == 2);
      cout << nxts[0] + 1 << " " << nxts[1] + 1 << "\n";
      matched[nxts[0]] = matched[nxts[1]] = true;
      kill(nxts[0]);
      kill(nxts[1]);
      sz[v] -= 2;
      if (sz[v]) sizes.emplace(sz[v], v);
    }
  }
  vector<int> seq;
  function<void(int)> dfs3 = [&](int u) {
    if (!matched[u]) seq.emplace_back(u);
    for (int v : adj[u]) dfs3(v);
  };
  dfs3(root);
  int h = (int)seq.size() / 2;
  for (int i = 0; i < h; ++i)
    cout << seq[i] + 1 << ' ' << seq[i + h] + 1 << '\n';
  return 0;
}