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