E. Паросочетание с расстояниями
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано целое число $$$k$$$ и дерево $$$T$$$ с $$$n$$$ вершинами ($$$n$$$ четно).

Обозначим за $$$dist(u, v)$$$ количество ребер на кратчайшем пути между вершинами $$$u$$$ и $$$v$$$ в $$$T$$$.

Определим неориентированный взвешенный полный граф $$$G = (V, E)$$$ следующим образом:

  • $$$V = \{x \mid 1 \le x \le n \}$$$ т.е. множество целых чисел от $$$1$$$ до $$$n$$$
  • $$$E = \{(u, v, w) \mid 1 \le u, v \le n, u \neq v, w = dist(u, v) \}$$$ т.е. существует ребро между каждой парой разных вершин, вес ребра равен расстоянию между соотвествующими вершинами в $$$T$$$

Ваша задача — найти совершенное паросочетание в $$$G$$$ с суммой весов ребер $$$k$$$ $$$(1 \le k \le n^2)$$$.

Входные данные

В первой строке записано два целых числа $$$n$$$, $$$k$$$ ($$$2 \le n \le 100\,000$$$, $$$n$$$ четное, $$$1 \le k \le n^2$$$): количество вершин и необходимый вес паросочетания.

В $$$i$$$-й из следующих $$$n - 1$$$ строк записаны два целых числа $$$v_i$$$, $$$u_i$$$ ($$$1 \le v_i, u_i \le n$$$), описывающих ребро между вершинами $$$v_i$$$ и $$$u_i$$$ в $$$T$$$. Гарантируется, что данный граф является деревом.

Выходные данные

Если не существует необходимого паросочетания, выведите «NO» (без кавычек) в единственной строке.

Иначе, выведите «YES» (без кавычек) в первой строке вывода.

Затем, выведите $$$\frac{n}{2}$$$ строк, в $$$i$$$-й из них выведите $$$p_i, q_i$$$ ($$$1 \le p_i, q_i \le n$$$): $$$i$$$-ю пару в паросочетании.

Примеры
Входные данные
4 2
1 2
2 3
3 4
Выходные данные
YES
2 1
3 4
Входные данные
4 4
1 2
2 3
3 4
Выходные данные
YES
3 1
2 4
Примечание

Дерево это связный неориентированный граф без циклов.

Паросочетание это множество попарно несмежных ребер, без петель; таким образом, никакие два ребра не имеют общих концов.

Совершенное паросочетание это паросочетание, которое покрывает все вершины графа; таким образом, каждая вершина инцидентна ровно одному ребру паросочетания.