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;
int n;
long long K;
int head[100010], v[100010 << 1], nxt[100010 << 1], tot = 0;
inline void add_edge(int s, int e) {
  tot++;
  v[tot] = e;
  nxt[tot] = head[s];
  head[s] = tot;
  tot++;
  v[tot] = s;
  nxt[tot] = head[e];
  head[e] = tot;
}
int siz[100010], mx[100010], rt;
int depth[100010];
int *son[100010], at[100010];
bool vis[100010];
int seq[100010], T = 0;
void findroot(int u, int f) {
  siz[u] = 1;
  mx[u] = 0;
  for (int i = head[u]; i; i = nxt[i])
    if (v[i] ^ f) {
      findroot(v[i], u);
      mx[u] = max(mx[u], siz[v[i]]);
      siz[u] += siz[v[i]];
    }
  mx[u] = max(mx[u], n - siz[u]);
  if (!rt || mx[u] < mx[rt]) rt = u;
}
bool leaf[100010];
int deg[100010];
struct B {
  int *head, *v, *nxt, tot = 0, Top;
  void init(int siz) {
    siz++;
    head = new int[siz + 2];
    memset(head, 0, sizeof(int) * (siz + 2));
    v = new int[siz + 2];
    memset(v, 0, sizeof(int) * (siz + 2));
    nxt = new int[siz + 2];
    memset(nxt, 0, sizeof(int) * (siz + 2));
    Top = siz + 1;
  }
  void add_edge(int dep, int u) {
    tot++;
    v[tot] = u;
    nxt[tot] = head[dep];
    head[dep] = tot;
  }
  void Del(int dep) { head[dep] = nxt[head[dep]]; }
  pair<int, int> query() {
    while (!head[Top]) Top--;
    return make_pair(v[head[Top]], Top);
  }
} B[100010];
long long L, R;
int bel[100010];
void pre_dfs(int u, int f) {
  siz[u] = 1;
  for (int i = head[u]; i; i = nxt[i])
    if (v[i] ^ f) {
      pre_dfs(v[i], u);
      siz[u] += siz[v[i]];
    }
}
int fa[100010];
void dfs(int u, int f, int tp) {
  vis[u] = true;
  bel[u] = tp;
  at[u] = 0;
  L += depth[u];
  R += depth[u];
  for (int i = head[u]; i; i = nxt[i])
    if (v[i] ^ f) {
      fa[v[i]] = u;
      depth[v[i]] = depth[u] + 1;
      dfs(v[i], u, tp);
      at[u]++;
    }
  son[u] = new int[at[u] + 1];
  son[u][0] = 0;
  at[u] = 0;
  if (at[u] == 0) leaf[u] = true;
  for (int i = head[u]; i; i = nxt[i])
    if (v[i] ^ f) {
      at[u]++;
      son[u][at[u]] = v[i];
      if (!leaf[v[i]]) deg[u]++;
    }
  if (u != rt && !deg[u]) {
    B[tp].add_edge(depth[u], u);
  }
  if (u != rt) L -= siz[u] / 2 * 2;
}
void search(int u, int f) {
  if (vis[u]) seq[++T] = u;
  for (int i = head[u]; i; i = nxt[i])
    if (v[i] ^ f) search(v[i], u);
}
inline void rd(int &x) {
  x = 0;
  char ch = getchar();
  while (ch < '0' || ch > '9') ch = getchar();
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
}
char num[20];
int numst;
void print(int x) {
  if (x == 0)
    putchar('0');
  else {
    numst = 0;
    while (x) {
      num[++numst] = '0' + x % 10;
      x /= 10;
    }
    while (numst) {
      putchar(num[numst]);
      numst--;
    }
  }
}
void output(int x, int y) {
  vis[x] = vis[y] = false;
  print(x);
  putchar(' ');
  print(y);
  puts("");
}
int main() {
  rd(n);
  scanf("%lld", &K);
  int s, e;
  for (int i = 1; i < n; ++i) {
    rd(s);
    rd(e);
    add_edge(s, e);
  }
  rt = 0;
  findroot(1, 0);
  pre_dfs(rt, 0);
  for (int i = head[rt]; i; i = nxt[i]) B[v[i]].init(siz[v[i]]);
  B[0].init(2 * n);
  depth[rt] = 0;
  vis[rt] = true;
  for (int i = head[rt]; i; i = nxt[i]) {
    fa[v[i]] = rt;
    depth[v[i]] = 1;
    dfs(v[i], rt, v[i]);
    B[0].add_edge(siz[v[i]], v[i]);
  }
  if (K < L || R < K || (K - L) & 1) {
    puts("NO");
    return 0;
  }
  puts("YES");
  long long sum = 0, To = (R - K) / 2;
  while (To) {
    pair<int, int> tmp = B[0].query();
    int node = tmp.first, siz = tmp.second;
    while (true) {
      tmp = B[node].query();
      int u = tmp.first;
      while (at[u] && !vis[son[u][at[u]]]) at[u]--;
      if (at[u] == 0) {
        B[node].Del(tmp.second);
      } else
        break;
    }
    tmp = B[node].query();
    int u = tmp.first;
    if (depth[u] > To) {
      while (depth[u] > To + 1) u = fa[u];
      output(u, fa[u]);
      To = 0;
      break;
    } else {
      To -= depth[u];
      int z = at[u] - 1, b = son[u][at[u]];
      while (z && !vis[son[u][z]]) z--;
      if (!z) {
        output(u, b);
        B[bel[u]].Del(depth[u]);
        if (fa[u] != rt) {
          deg[fa[u]]--;
          if (!deg[fa[u]]) B[bel[u]].add_edge(depth[fa[u]], fa[u]);
        }
      } else {
        output(b, son[u][z]);
        at[u] = z - 1;
        while (at[u] && !vis[son[u][at[u]]]) at[u]--;
        if (!at[u] && fa[u] != rt) {
          deg[fa[u]]--;
          if (!deg[fa[u]]) B[bel[u]].add_edge(depth[fa[u]], fa[u]);
        }
      }
    }
    B[0].Del(siz);
    siz -= 2;
    if (siz > 1) B[0].add_edge(siz, node);
  }
  search(rt, 0);
  for (int i = 1; i <= T / 2; ++i) output(seq[i], seq[i + T / 2]);
  return 0;
}