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 long long M = 1e5 + 5;
long long min(long long x, long long y) { return x < y ? x : y; }
long long max(long long x, long long y) { return x > y ? x : y; }
long long n, K, Min = 0, Max = 0, Ans;
long long read() {
  long long x = 0, y = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') y = (ch == '-') ? -1 : 1, ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  return x * y;
}
long long tot = 0, first[M];
struct Edge {
  long long nxt, to;
} e[M << 1];
void add(long long x, long long y) {
  e[++tot] = (Edge){first[x], y};
  first[x] = tot;
}
long long sz[M];
void dfs(long long u, long long f) {
  sz[u] = 1;
  for (long long i = first[u]; i; i = e[i].nxt) {
    long long v = e[i].to;
    if (v == f) continue;
    dfs(v, u);
    sz[u] += sz[v];
  }
}
pair<long long, long long> cun[M];
list<long long> dfs2(long long u, long long f) {
  list<long long> cur;
  cur.push_back(u);
  for (long long i = first[u]; i; i = e[i].nxt) {
    long long v = e[i].to;
    if (v == f) continue;
    cur.splice(cur.end(), dfs2(v, u));
  }
  long long siz = (cur.size() - sz[u]) >> 1;
  for (long long i = 0; i < siz; i++) {
    cun[i].first = cur.front();
    cun[siz - i - 1].second = cur.back();
    cur.pop_front(), cur.pop_back();
  }
  for (long long i = 0; i < siz; i++)
    printf("%lld %lld\n", cun[i].first, cun[i].second);
  return cur;
}
long long check(long long x) {
  long long res = 0;
  for (long long i = 2; i <= n; i++)
    if (sz[i] <= x)
      res += sz[i];
    else
      res += x - ((sz[i] - x) & 1);
  return res;
}
void solve() {
  n = read(), K = read();
  for (long long i = 2; i <= n; i++) {
    long long x = read(), y = read();
    add(x, y), add(y, x);
  }
  dfs(1, 0);
  for (long long i = 1; i <= n; i++)
    Max += sz[i] = min(sz[i], n - sz[i]), Min += (sz[i] & 1);
  if (K < Min || K > Max || (Max - K) & 1) return (void)(printf("NO\n"));
  long long l = 0, r = n >> 1;
  while (l <= r) {
    long long mid = (l + r) >> 1, p = check(mid);
    if (p >= K)
      r = mid - 1, Ans = p;
    else
      l = mid + 1;
  }
  for (long long i = 2; i <= n; i++) {
    if (sz[i] > l) sz[i] = l - ((sz[i] - l) & 1);
    if (sz[i] == l && Ans > K) sz[i] -= 2, Ans -= 2;
  }
  printf("YES\n");
  dfs2(1, 0);
}
signed main() { solve(); }