Дано дерево (связный неориентированный граф без циклов) с \(n\) вершинами. Два ребра считаются смежными, если они имеют ровно один общий конец. За один ход вы можете удалить любое ребро, которое смежно четному количеству оставшихся ребер.
Удалите все ребра или установите, что это невозможно. Если существует несколько решений, выведите любое из них.
Выходные данные
Для каждого набора входных данных выведите «NO», если невозможно удалить все ребра.
В противном случае выведите «YES» и в следующих \(n-1\) строке выведите возможный порядок удаления ребер. Для каждого ребра выведите его концы в любом порядке.
Примечание
Пример \(1\): можно удалить данное ребро, поскольку оно не смежно никакому ребру.
Пример \(2\): оба ребра смежны ровно одному ребру, поэтому невозможно удалить ни одно из них. Таким образом, ответ «NO».
Пример \(3\): ребро \(2-3\) смежно двум другим ребрам, поэтому его можно удалить. После этого также становится возможным удалить оставшиеся ребра.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2
1 2
3
1 2
2 3
4
1 2
2 3
3 4
5
1 2
2 3
3 4
3 5
7
1 2
1 3
2 4
2 5
3 6
3 7
|
YES
2 1
NO
YES
2 3
3 4
2 1
YES
3 5
2 3
2 1
4 3
NO
|