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 N = 100010;
int n, prnt[N];
long long k;
long long sum = 0;
vector<int> g[N];
int sz[N];
void DFS(int node, int prnt) {
  sz[node] = 1;
  for (int i = 0; i < (int)g[node].size(); i++) {
    if (g[node][i] == prnt) continue;
    DFS(g[node][i], node);
    sz[node] += sz[g[node][i]];
  }
}
int get_centroid(int node, int prnt) {
  for (int i = 0; i < (int)g[node].size(); i++) {
    if (g[node][i] == prnt) continue;
    if (sz[g[node][i]] > n / 2) return get_centroid(g[node][i], node);
  }
  return node;
}
int Idx, cur[N], in[N], depth[N], val[N], root;
bool taken[N];
void init(int node) {
  cur[node] = Idx;
  val[Idx]++;
  sum += depth[node];
  for (int i = 0; i < (int)g[node].size(); i++) {
    if (g[node][i] == prnt[node]) continue;
    depth[g[node][i]] = depth[node] + 1;
    prnt[g[node][i]] = node;
    init(g[node][i]);
    in[node]++;
  }
}
vector<int> has[N];
priority_queue<pair<int, int> > q[N];
set<pair<int, int> > st[N];
set<pair<int, int> >::iterator it, it2;
vector<pair<int, int> > ans;
priority_queue<pair<int, int> > pq, q2;
void finish(int node) {
  it2 = st[cur[node]].find(make_pair(depth[node], node));
  if (it2 != st[cur[node]].end()) st[cur[node]].erase(it2);
  int idx = -1;
  for (int i = 0; i < (int)g[node].size(); i++) {
    if (g[node][i] == prnt[node]) continue;
    if (idx == -1 ||
        (int)has[g[node][i]].size() > (int)has[g[node][idx]].size()) {
      idx = i;
    }
  }
  if (idx != -1) swap(has[node], has[g[node][idx]]);
  for (int i = 0; i < (int)g[node].size(); i++) {
    if (i == idx || g[node][i] == prnt[node]) continue;
    while ((int)has[g[node][i]].size() > 0) {
      has[node].push_back(has[g[node][i]].back());
      has[g[node][i]].pop_back();
    }
  }
  if (!taken[node]) has[node].push_back(node);
  if (prnt[node] == root) return;
  in[prnt[node]]--;
  if ((int)has[node].size() > 0)
    q[prnt[node]].push(make_pair((int)has[node].size(), node));
  if (in[prnt[node]] == 0) {
    st[cur[node]].insert(make_pair(depth[prnt[node]], prnt[node]));
  }
}
vector<int> lll;
int main() {
  scanf("%d%lld", &n, &k);
  for (int u, v, i = 0; i < n - 1; i++) {
    scanf("%d%d", &u, &v);
    g[u].push_back(v);
    g[v].push_back(u);
  }
  DFS(1, -1);
  root = get_centroid(1, -1);
  prnt[root] = -1;
  for (int i = 0; i < (int)g[root].size(); i++) {
    Idx = i;
    prnt[g[root][i]] = root;
    depth[g[root][i]] = 1;
    init(g[root][i]);
    in[root]++;
    pq.push(make_pair(val[Idx], Idx));
  }
  if (k > sum || (sum % 2) != (k % 2)) {
    puts("NO");
    return 0;
  }
  for (int i = 1; i <= n; i++) {
    if (in[i] == 0) {
      lll.push_back(i);
    }
  }
  for (int i = 0; i < (int)lll.size(); i++) {
    finish(lll[i]);
  }
  int tmp1, tmp2, tmp3, tmp4;
  long long needed;
  while (sum > k && (int)pq.size() > 0) {
    tmp1 = pq.top().second;
    pq.pop();
    if (val[tmp1] < 2) break;
    needed = (sum - k) / 2;
    assert((int)st[tmp1].size() > 0);
    while (true) {
      it = st[tmp1].end();
      it--;
      tmp2 = it->second;
      if ((long long)it->first > needed) {
        finish(tmp2);
        continue;
      }
      if ((int)q[tmp2].size() > 1) {
        tmp3 = q[tmp2].top().second;
        q[tmp2].pop();
        tmp4 = q[tmp2].top().second;
        q[tmp2].pop();
        ans.push_back(make_pair(has[tmp3].back(), has[tmp4].back()));
        taken[has[tmp3].back()] = taken[has[tmp4].back()] = true;
        has[tmp3].pop_back();
        has[tmp4].pop_back();
        if ((int)has[tmp3].size() > 0)
          q[tmp2].push(make_pair((int)has[tmp3].size(), tmp3));
        if ((int)has[tmp4].size() > 0)
          q[tmp2].push(make_pair((int)has[tmp4].size(), tmp4));
        sum -= (long long)2 * depth[tmp2];
        break;
      }
      if (taken[tmp2] || (int)q[tmp2].size() == 0) {
        finish(tmp2);
        continue;
      }
      tmp3 = q[tmp2].top().second;
      q[tmp2].pop();
      ans.push_back(make_pair(tmp2, has[tmp3].back()));
      taken[tmp2] = true;
      taken[has[tmp3].back()] = true;
      has[tmp3].pop_back();
      finish(tmp2);
      sum -= (long long)2 * depth[tmp2];
      break;
    }
    val[tmp1] -= 2;
    if (val[tmp1] > 0) pq.push(make_pair(val[tmp1], tmp1));
  }
  for (int i = 1; i <= n; i++) has[i].clear();
  for (int i = 1; i <= n; i++) {
    if (i != root && !taken[i]) has[cur[i]].push_back(i);
  }
  for (int i = 0; i < (int)g[root].size(); i++) {
    if ((int)has[i].size() > 0) q2.push(make_pair((int)has[i].size(), i));
  }
  while ((int)q2.size() > 1) {
    tmp1 = q2.top().second;
    q2.pop();
    tmp2 = q2.top().second;
    q2.pop();
    ans.push_back(make_pair(has[tmp1].back(), has[tmp2].back()));
    has[tmp1].pop_back();
    has[tmp2].pop_back();
    if ((int)has[tmp1].size() > 0)
      q2.push(make_pair((int)has[tmp1].size(), tmp1));
    if ((int)has[tmp2].size() > 0)
      q2.push(make_pair((int)has[tmp2].size(), tmp2));
  }
  assert((int)q2.size() > 0);
  tmp1 = q2.top().second;
  tmp1 = has[tmp1].back();
  ans.push_back(make_pair(root, tmp1));
  if (sum == k) {
    puts("YES");
    assert((int)ans.size() == n / 2);
    for (int i = 0; i < (int)ans.size(); i++) {
      printf("%d %d\n", ans[i].first, ans[i].second);
    }
  } else
    puts("NO");
  return 0;
}