Вам дано целое число \(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)\).
Выходные данные
Если не существует необходимого паросочетания, выведите «NO» (без кавычек) в единственной строке.
Иначе, выведите «YES» (без кавычек) в первой строке вывода.
Затем, выведите \(\frac{n}{2}\) строк, в \(i\)-й из них выведите \(p_i, q_i\) (\(1 \le p_i, q_i \le n\)): \(i\)-ю пару в паросочетании.
Примечание
Дерево это связный неориентированный граф без циклов.
Паросочетание это множество попарно несмежных ребер, без петель; таким образом, никакие два ребра не имеют общих концов.
Совершенное паросочетание это паросочетание, которое покрывает все вершины графа; таким образом, каждая вершина инцидентна ровно одному ребру паросочетания.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 2
1 2
2 3
3 4
|
YES
2 1
3 4
|
|
2
|
4 4
1 2
2 3
3 4
|
YES
3 1
2 4
|