Деревом называется связный неориентированный граф без циклов. Обратите внимание, что в этой задаче речь идёт о некорневых деревьях.
Заданы четыре положительных целых числа \(n, d_{12}, d_{23}\) и \(d_{31}\). Постройте такое дерево, что:
- оно содержит \(n\) вершин, пронумерованных от \(1\) до \(n\),
- расстояние (длина кратчайшего пути) от вершины \(1\) до вершины \(2\) равно \(d_{12}\),
- расстояние от вершины \(2\) до вершины \(3\) равно \(d_{23}\),
- расстояние от вершины \(3\) до вершины \(1\) равно \(d_{31}\).
Выведите любое дерево, которое удовлетворяет всем требованиям выше, или определите, что такого дерева не существует.
Выходные данные
Для каждого набора входных данных выведите YES, если искомое дерево существует, и NO в противном случае. В случае положительного ответа выведите ещё \(n-1\) строку, каждая содержит описание ребра дерева — пару положительных целых чисел \(x_i, y_i\), которая обозначает, что \(i\)-е ребро соединяет вершины \(x_i\) и \(y_i\). Ребра и вершины ребер можно выводить в произвольном порядке. Если искомых деревьев несколько, выведите любое из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
9
5 1 2 1
5 2 2 2
5 2 2 3
5 2 2 4
5 3 2 3
4 2 1 1
4 3 1 1
4 1 2 3
7 1 4 1
|
YES
1 2
4 1
3 1
2 5
YES
4 3
2 5
1 5
5 3
NO
YES
2 4
4 1
2 5
5 3
YES
5 4
4 1
2 5
3 5
YES
2 3
3 4
1 3
NO
YES
4 3
1 2
2 4
NO
|