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 = 100005;
const int inf = 1000 * 1000;
const int mod = 1000 * 1000 * 1000 + 7;
mt19937 myrand(chrono::steady_clock::now().time_since_epoch().count());
int n;
long long k;
vector<pair<int, int> > g[N];
int sz[N];
long long mn, mx;
void dfs(int v, int p) {
  sz[v] = 1;
  for (int i = 0; i < (int)g[v].size(); i++) {
    int to = g[v][i].first;
    if (to == p) continue;
    dfs(to, v);
    sz[v] += sz[to];
    mn += min(sz[to], n - sz[to]) % 2;
    mx += min(sz[to], n - sz[to]);
    g[v][i].second = min(sz[to], n - sz[to]) % 2;
  }
}
void rec(int v, int p, int lim) {
  for (int i = 0; i < (int)g[v].size(); i++) {
    int to = g[v][i].first;
    if (to == p) continue;
    int t = (sz[to] % 2 == lim % 2) ? lim : (lim - 1);
    int val = min(t, min(sz[to], n - sz[to])) - g[v][i].second;
    g[v][i].second += val;
    k -= val;
    rec(to, v, lim);
  }
}
vector<int> mas[N];
vector<pair<int, int> > answ;
void solve(int v, int p, int x) {
  mas[v].push_back(v);
  set<pair<int, int> > Q;
  int all = 1;
  Q.insert(make_pair(1, v));
  for (int i = 0; i < (int)g[v].size(); i++) {
    int to = g[v][i].first;
    int len = g[v][i].second;
    if (to == p) continue;
    solve(to, v, len);
    all += (int)mas[to].size();
    if ((int)mas[to].size() != 0) {
      Q.insert(make_pair((int)mas[to].size(), to));
    }
  }
  while (all != x) {
    set<pair<int, int> >::iterator it = Q.end();
    --it;
    int id1 = it->second;
    --it;
    int id2 = it->second;
    Q.erase(make_pair((int)mas[id1].size(), id1));
    Q.erase(make_pair((int)mas[id2].size(), id2));
    int a = mas[id1].back();
    mas[id1].pop_back();
    int b = mas[id2].back();
    mas[id2].pop_back();
    answ.push_back(make_pair(a, b));
    if ((int)mas[id1].size() != 0) {
      Q.insert(make_pair((int)mas[id1].size(), id1));
    }
    if ((int)mas[id2].size() != 0) {
      Q.insert(make_pair((int)mas[id2].size(), id2));
    }
    all -= 2;
  }
  for (int i = 0; i < (int)g[v].size(); i++) {
    int to = g[v][i].first;
    if (to == p) continue;
    if ((int)mas[to].size() > (int)mas[v].size()) {
      swap(mas[v], mas[to]);
    }
    for (int j = 0; j < (int)mas[to].size(); j++) {
      mas[v].push_back(mas[to][j]);
    }
  }
}
long long sum = 0;
void recForCheck(int v, int p, int lim) {
  for (int i = 0; i < (int)g[v].size(); i++) {
    int to = g[v][i].first;
    if (to == p) continue;
    int len = min(sz[to], n - sz[to]);
    if (len > lim) {
      if (len % 2 == lim % 2) {
        len = lim;
      } else {
        len = lim - 1;
      }
    }
    sum += len;
    recForCheck(to, v, lim);
  }
}
bool check(int lim) {
  sum = 0;
  recForCheck(1, -1, lim);
  return sum >= k;
}
int main() {
  cin >> n >> k;
  for (int i = 1; i < n; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    g[a].push_back(make_pair(b, 0));
    g[b].push_back(make_pair(a, 0));
  }
  dfs(1, -1);
  if (k < mn || k > mx || k % 2 != mn % 2) {
    cout << "NO" << endl;
    return 0;
  }
  int ina = 1, inb = n, pat;
  while (ina <= inb) {
    int mid = (ina + inb) / 2;
    if (check(mid)) {
      pat = mid;
      inb = mid - 1;
    } else {
      ina = mid + 1;
    }
  }
  cout << "YES" << endl;
  k -= mn;
  rec(1, -1, pat);
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < (int)g[i].size(); j++) {
      if (g[i][j].second == pat && k < 0) {
        k += 2;
        g[i][j].second -= 2;
      }
    }
  }
  solve(1, -1, 0);
  for (int i = 0; i < (int)answ.size(); i++) {
    printf("%d %d\n", answ[i].first, answ[i].second);
  }
  return 0;
}