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 ll = long long;
using pii = std::pair<int, int>;
const int N = 1e5 + 10;
template <typename T = int>
inline T read() {
  T x = 0;
  int f = 0;
  char ch = getchar();
  while (!isdigit(ch)) f = ch == '-', ch = getchar();
  while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
  return f ? -x : x;
}
int tot = 1, fir[N], nex[N << 1], got[N << 1];
inline void AddEdge(int u, int v) {
  nex[++tot] = fir[u], fir[u] = tot, got[tot] = v;
  nex[++tot] = fir[v], fir[v] = tot, got[tot] = u;
}
int siz[N], w[N];
std::vector<int> vec[N];
inline void dfs(int u, int fa) {
  siz[u] = 1;
  for (int i = fir[u]; i; i = nex[i])
    if (got[i] != fa) dfs(got[i], u), siz[u] += siz[got[i]];
}
inline void merge(int u, int v) {
  if (vec[u].size() > vec[v].size()) std::swap(vec[u], vec[v]);
  for (auto dat : vec[u]) vec[v].emplace_back(dat);
}
inline void solve(int u, int fa) {
  vec[u].push_back(u);
  std::set<pii> s;
  int x = 1;
  s.insert(std::make_pair(-1, u));
  for (int i = fir[u]; i; i = nex[i])
    if (got[i] != fa) {
      solve(got[i], u);
      s.insert(std::make_pair(-vec[got[i]].size(), got[i]));
      x += vec[got[i]].size();
    }
  int lim = (x - w[u]) / 2;
  while (lim--) {
    int a = s.begin()->second;
    s.erase(s.begin());
    int b = s.begin()->second;
    s.erase(s.begin());
    printf("%d %d\n", vec[a].back(), vec[b].back());
    vec[a].pop_back(), vec[b].pop_back();
    s.insert(std::make_pair(-vec[a].size(), a));
    s.insert(std::make_pair(-vec[b].size(), b));
  }
  for (int i = fir[u]; i; i = nex[i])
    if (got[i] != fa) merge(got[i], u);
}
int main() {
  int n = read();
  ll k = read<ll>(), l = 0, r = 0;
  for (int i = 1; i <= n - 1; ++i) AddEdge(read(), read());
  dfs(1, 0);
  for (int i = 2; i <= n; ++i) {
    l += siz[i] & 1;
    w[i] = std::min(siz[i], n - siz[i]);
    r += w[i];
  }
  if (k < l || k > r || (k - l) & 1) return puts("NO"), 0;
  puts("YES");
  int L = 0, R = n, x = 0;
  ll s = 0;
  while (L <= R) {
    int mid = (L + R) >> 1;
    ll s = 0;
    for (int i = 2; i <= n; ++i)
      s += w[i] <= mid ? w[i] : mid - (w[i] - mid) % 2;
    if (s >= k)
      x = mid, R = mid - 1;
    else
      L = mid + 1;
  }
  for (int i = 2; i <= n; ++i) w[i] = w[i] <= x ? w[i] : x - (w[i] - x) % 2;
  for (int i = 2; i <= n; ++i) s += w[i];
  for (int i = 2; i <= n; ++i)
    if (w[i] == x && s > k) s -= 2, w[i] -= 2;
  solve(1, 0);
  return 0;
}