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;
using ll = long long;
using ld = long double;
using db = double;
using str = string;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;
template <class T>
using V = vector<T>;
template <class T, size_t SZ>
using AR = array<T, SZ>;
const int MOD = 1e9 + 7;
const int MX = 2e5 + 5;
const ll INF = 1e18;
const ld PI = acos((ld)-1);
const int xd[4] = {1, 0, -1, 0}, yd[4] = {0, 1, 0, -1};
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
constexpr int pct(int x) { return __builtin_popcount(x); }
constexpr int bits(int x) { return 31 - __builtin_clz(x); }
ll cdiv(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); }
ll fdiv(ll a, ll b) { return a / b - ((a ^ b) < 0 && a % b); }
ll half(ll x) { return fdiv(x, 2); }
template <class T>
bool ckmin(T& a, const T& b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
bool ckmax(T& a, const T& b) {
  return a < b ? a = b, 1 : 0;
}
template <class T, class U>
T fstTrue(T lo, T hi, U first) {
  hi++;
  assert(lo <= hi);
  while (lo < hi) {
    T mid = half(lo + hi);
    first(mid) ? hi = mid : lo = mid + 1;
  }
  return lo;
}
template <class T, class U>
T lstTrue(T lo, T hi, U first) {
  lo--;
  assert(lo <= hi);
  while (lo < hi) {
    T mid = half(lo + hi + 1);
    first(mid) ? lo = mid : hi = mid - 1;
  }
  return lo;
}
template <class T>
void remDup(vector<T>& v) {
  sort(begin(v), end(v));
  v.erase(unique(begin(v), end(v)), end(v));
}
template <class T, class U>
void erase(T& t, const U& u) {
  auto it = t.find(u);
  assert(it != end(t));
  t.erase(u);
}
template <class T>
void re(complex<T>& c);
template <class T, class U>
void re(pair<T, U>& p);
template <class T>
void re(vector<T>& v);
template <class T, size_t SZ>
void re(AR<T, SZ>& a);
template <class T>
void re(T& x) {
  cin >> x;
}
void re(db& d) {
  str t;
  re(t);
  d = stod(t);
}
void re(ld& d) {
  str t;
  re(t);
  d = stold(t);
}
template <class T, class... U>
void re(T& t, U&... u) {
  re(t);
  re(u...);
}
template <class T>
void re(complex<T>& c) {
  T a, b;
  re(a, b);
  c = {a, b};
}
template <class T, class U>
void re(pair<T, U>& p) {
  re(p.first, p.second);
}
template <class T>
void re(vector<T>& x) {
  for (auto& a : x) re(a);
}
template <class T, size_t SZ>
void re(array<T, SZ>& x) {
  for (auto& a : x) re(a);
}
str to_string(char c) { return str(1, c); }
str to_string(const char* second) { return (str)second; }
str to_string(str second) { return second; }
str to_string(bool b) { return to_string((int)b); }
template <class T>
str to_string(complex<T> c) {
  stringstream ss;
  ss << c;
  return ss.str();
}
str to_string(vector<bool> v) {
  str res = "{";
  for (int i = (0); i < ((int)(v).size()); ++i) res += char('0' + v[i]);
  res += "}";
  return res;
}
template <size_t SZ>
str to_string(bitset<SZ> b) {
  str res = "";
  for (int i = (0); i < (SZ); ++i) res += char('0' + b[i]);
  return res;
}
template <class T, class U>
str to_string(pair<T, U> p);
template <class T>
str to_string(T v) {
  bool fst = 1;
  str res = "";
  for (const auto& x : v) {
    if (!fst) res += " ";
    fst = 0;
    res += to_string(x);
  }
  return res;
}
template <class T, class U>
str to_string(pair<T, U> p) {
  return to_string(p.first) + " " + to_string(p.second);
}
template <class T>
void pr(T x) {
  cout << to_string(x);
}
template <class T, class... U>
void pr(const T& t, const U&... u) {
  pr(t);
  pr(u...);
}
void ps() { pr("\n"); }
template <class T, class... U>
void ps(const T& t, const U&... u) {
  pr(t);
  if (sizeof...(u)) pr(" ");
  ps(u...);
}
void DBG() { cerr << "]" << endl; }
template <class T, class... U>
void DBG(const T& t, const U&... u) {
  cerr << to_string(t);
  if (sizeof...(u)) cerr << ", ";
  DBG(u...);
}
void setIn(str second) { freopen(second.c_str(), "r", stdin); }
void setOut(str second) { freopen(second.c_str(), "w", stdout); }
void unsyncIO() { cin.tie(0)->sync_with_stdio(0); }
void setIO(str second = "") {
  unsyncIO();
  if ((int)(second).size()) {
    setIn(second + ".in"), setOut(second + ".out");
  }
}
int n;
ll k;
int sub[MX];
vi adj[MX];
ll mn, mx;
vpi ed;
vi cur[MX];
int up[MX];
set<int> oops[MX];
void dfs(int a, int b) {
  sub[a] = 1;
  for (auto& t : adj[a])
    if (t != b) {
      dfs(t, a);
      sub[a] += sub[t];
    }
  if (sub[a] & 1) mn++;
  mx += min(sub[a], n - sub[a]);
  cur[min(sub[a], n - sub[a])].push_back(a);
}
vpi ans;
void comb(set<int>& a, set<int>& b) {
  if ((int)(a).size() < (int)(b).size()) swap(a, b);
  for (auto& t : b) a.insert(t);
  b.clear();
}
void go(int a, int b) {
  priority_queue<pi> p;
  int sum = 0;
  for (auto& t : adj[a])
    if (t != b) {
      go(t, a);
      if ((int)(oops[t]).size()) {
        p.push({(int)(oops[t]).size(), t});
        sum += (int)(oops[t]).size();
      }
    }
  assert((sum - up[a]) % 2 != 0);
  while ((int)(p).size() > 1 && sum > up[a]) {
    pi x = p.top();
    p.pop();
    pi y = p.top();
    p.pop();
    int X = *oops[x.second].begin();
    int Y = *oops[y.second].begin();
    ans.push_back({X, Y});
    sum -= 2;
    oops[x.second].erase(oops[x.second].begin());
    if ((int)(oops[x.second]).size())
      p.push({(int)(oops[x.second]).size(), x.second});
    oops[y.second].erase(oops[y.second].begin());
    if ((int)(oops[y.second]).size())
      p.push({(int)(oops[y.second]).size(), y.second});
  }
  while ((int)(p).size()) {
    comb(oops[a], oops[p.top().second]);
    p.pop();
  }
  if (sum > up[a]) {
    assert(sum == up[a] + 1);
    ans.push_back({*oops[a].begin(), a});
    oops[a].erase(begin(oops[a]));
  } else {
    assert(sum == up[a] - 1);
    oops[a].insert(a);
  }
}
int main() {
  setIO();
  re(n, k);
  for (int i = (0); i < (n - 1); ++i) {
    int u, v;
    re(u, v);
    adj[u].push_back(v), adj[v].push_back(u);
  }
  dfs(1, 0);
  if ((k - mn) % 2 != 0 || k < mn || k > mx) {
    ps("NO");
    exit(0);
  }
  ps("YES");
  for (int i = (n + 1) - 1; i >= (2); --i) {
    if (mx - 2 * (int)(cur[i]).size() >= k) {
      mx -= 2 * (int)(cur[i]).size();
      swap(cur[i - 2], cur[i]);
      cur[i - 2].insert(end(cur[i - 2]), begin(cur[i]), end(cur[i]));
      cur[i].clear();
    } else {
      while (mx > k && (int)(cur[i]).size()) {
        mx -= 2;
        cur[i - 2].push_back(cur[i].back());
        cur[i].pop_back();
      }
    }
  }
  int sum = 0;
  for (int i = (0); i < (n + 1); ++i) sum += (int)(cur[i]).size();
  assert(sum == n);
  assert(mx == k);
  for (int i = (1); i < (n + 1); ++i)
    for (auto& t : cur[i]) up[t] = i;
  go(1, 0);
  for (auto& t : ans) ps(t.first, t.second);
}