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 inf = (int)1.01e9;
const long long infll = (long long)1.01e18;
const long double eps = 1e-9;
const long double pi = acos((long double)-1);
mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x) { return mrand() % x; }
void precalc() {}
const int maxn = (int)1e5 + 5;
int n;
long long k;
vector<int> g[maxn];
bool read() {
  if (scanf("%d%lld", &n, &k) < 2) {
    return false;
  }
  for (int i = 0; i < n; ++i) {
    g[i].clear();
  }
  for (int i = 0; i < n - 1; ++i) {
    int v, u;
    scanf("%d%d", &v, &u);
    --v;
    --u;
    g[v].push_back(u);
    g[u].push_back(v);
  }
  return true;
}
int ts[maxn];
void getTs(int v, int p) {
  ts[v] = 1;
  for (int i = 0; i < ((int)(g[v]).size()); ++i) {
    int u = g[v][i];
    if (u == p) {
      continue;
    }
    getTs(u, v);
    ts[v] += ts[u];
  }
}
int cnt[maxn];
int a[maxn];
vector<int> *vs[maxn];
priority_queue<pair<int, int>> pq;
vector<pair<int, int>> ans;
void dfs(int v, int p) {
  for (int i = 0; i < ((int)(g[v]).size()); ++i) {
    int u = g[v][i];
    if (u == p) {
      continue;
    }
    dfs(u, v);
  }
  while (!pq.empty()) {
    pq.pop();
  }
  {
    vs[v] = new vector<int>(1, v);
    pq.push(make_pair(1, v));
  }
  int sum = 1;
  for (int i = 0; i < ((int)(g[v]).size()); ++i) {
    int u = g[v][i];
    if (u == p) {
      continue;
    }
    if (!vs[u]->empty()) {
      pq.push(make_pair(((int)(*vs[u]).size()), u));
      sum += ((int)(*vs[u]).size());
    }
  }
  while (sum > a[v]) {
    assert(!pq.empty());
    int x = pq.top().second;
    pq.pop();
    assert(!pq.empty());
    int y = pq.top().second;
    pq.pop();
    ans.push_back(make_pair(vs[x]->back(), vs[y]->back()));
    vs[x]->pop_back();
    vs[y]->pop_back();
    sum -= 2;
    if (!vs[x]->empty()) {
      pq.push(make_pair(((int)(*vs[x]).size()), x));
    }
    if (!vs[y]->empty()) {
      pq.push(make_pair(((int)(*vs[y]).size()), y));
    }
  }
  if (!pq.empty()) {
    int u = pq.top().second;
    pq.pop();
    while (!pq.empty()) {
      int w = pq.top().second;
      pq.pop();
      for (int i = 0; i < ((int)(*vs[w]).size()); ++i) {
        vs[u]->push_back((*vs[w])[i]);
      }
      delete vs[w];
    }
    vs[v] = vs[u];
  }
}
void solve() {
  getTs(0, -1);
  long long cur = 0, mx = 0;
  for (int i = 0; i <= n; ++i) {
    cnt[i] = 0;
  }
  for (int i = 0; i < n; ++i) {
    cur += (ts[i] & 1);
    int x = min(ts[i], n - ts[i]);
    mx += x;
    ++cnt[x];
  }
  if (k < cur || k > mx || (k & 1) != (cur & 1)) {
    printf("NO\n");
    return;
  }
  int c[2] = {n - (int)cur, (int)cur};
  c[0] -= cnt[0];
  c[1] -= cnt[1];
  for (int i = 2; i <= n; ++i) {
    if (cur + c[i & 1] * 2 >= k) {
      a[0] = 0;
      for (int v = 0; v < n; ++v) {
        int val = ((ts[v] & 1) == (i & 1) ? i - 2 : i - 1);
        val = min(val, min(ts[v], n - ts[v]));
        a[v] = val;
      }
      int need = k - cur;
      for (int v = 0; v < n && need; ++v) {
        if ((ts[v] & 1) == (i & 1) && a[v] + 2 <= min(ts[v], n - ts[v])) {
          a[v] += 2;
          need -= 2;
        }
      }
      break;
    }
    cur += c[i & 1] * 2;
    c[i & 1] -= cnt[i];
  }
  ans.clear();
  dfs(0, -1);
  printf("YES\n");
  for (int i = 0; i < ((int)(ans).size()); ++i) {
    printf("%d %d\n", ans[i].first + 1, ans[i].second + 1);
  }
}
int main() {
  precalc();
  while (read()) {
    solve();
  }
  return 0;
}