CF761E.Dasha and Puzzle

Dasha decided to have a rest after solving the problem. She had been ready to start her favourite activity — origami, but remembered the puzzle that she could not solve.

The tree is a non-oriented connected graph without cycles. In particular, there always are n - 1 edges in a tree with n vertices.

The puzzle is to position the vertices at the points of the Cartesian plane with integral coordinates, so that the segments between the vertices connected by edges are parallel to the coordinate axes. Also, the intersection of segments is allowed only at their ends. Distinct vertices should be placed at different points.

Help Dasha to find any suitable way to position the tree vertices on the plane.

It is guaranteed that if it is possible to position the tree vertices on the plane without violating the condition which is given above, then you can do it by using points with integral coordinates which don't exceed 1018 in absolute value.

达莎在解完这道题后决定休息一下。她本已准备好开始自己最喜爱的活动——折纸，却突然想起了之前没能解开的一道谜题。

树（tree）是一个无向、连通且无环的图。特别地，一个包含 $n$ 个顶点的树中，边的数量恒为 $n - 1$。

该谜题要求将树的各个顶点放置在笛卡尔平面上具有整数坐标的点上，使得每条连接相邻顶点的线段均平行于坐标轴；此外，任意两条线段仅可在其端点处相交；不同顶点必须置于不同的点上。

请帮助达莎找出一种满足上述条件的顶点平面布局方案。

题目保证：若存在一种不违反上述条件的顶点平面布局，则一定存在一种使用整数坐标点的布局方案，且所有坐标的绝对值均不超过 $10^{18}$。

The first line contains single integer n (1 ≤ n ≤ 30) — the number of vertices in the tree.

Each of next n - 1 lines contains two integers u__i, v__i (1 ≤ u__i, v__i ≤ n) that mean that the i-th edge of the tree connects vertices u__i and v__i.

It is guaranteed that the described graph is a tree.

第一行包含一个整数 $n$（$1 \leq n \leq 30$）——树中顶点的数量。

接下来的 $n-1$ 行中，每行包含两个整数 $u_i$、$v_i$（$1 \leq u_i, v_i \leq n$），表示树的第 $i$ 条边连接顶点 $u_i$ 和 $v_i$。

保证所描述的图是一棵树。

If the puzzle doesn't have a solution then in the only line print "NO".

Otherwise, the first line should contain "YES". The next n lines should contain the pair of integers x__i, y__i (|x__i|, |y__i| ≤ 1018) — the coordinates of the point which corresponds to the i-th vertex of the tree.

If there are several solutions, print any of them.

如果谜题无解，则在唯一一行中输出“NO”。

否则，第一行应输出“YES”。接下来的 $n$ 行中，每行应包含一对整数 $x_i$, $y_i$（满足 $|x_i|,\,|y_i| \leq 10^{18}$），表示对应树的第 $i$ 个顶点的坐标。

若存在多个解，输出任意一个即可。

In the first sample one of the possible positions of tree is:

在第一个样例中，树的一种可能位置为：