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