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.
<center></center>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.
## Input
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.
## Output
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.
[samples]
## Note
In the first sample one of the possible positions of tree is: 
Dasha 在解决完问题后决定休息一下。她本准备开始自己最喜欢的手工活动——折纸，但突然想起了那个尚未解决的谜题。
树是一种无向连通无环图。特别地，具有 #cf_span[n] 个顶点的树中总是包含 #cf_span[n - 1] 条边。
这个谜题要求将每个顶点放置在笛卡尔平面上的整数坐标点上，使得连接有边的顶点之间的线段与坐标轴平行，并且线段的交点仅允许出现在端点处。不同顶点必须放置在不同的点上。
请帮助 Dasha 找到一种将树的顶点放置在平面上的可行方案。
题目保证，如果存在满足上述条件的放置方式，则可以使用绝对值不超过 #cf_span[1018] 的整数坐标点实现。
第一行包含一个整数 #cf_span[n] #cf_span[(1 ≤ n ≤ 30)] —— 树的顶点数。
接下来的 #cf_span[n - 1] 行每行包含两个整数 #cf_span[ui], #cf_span[vi] (#cf_span[1 ≤ ui, vi ≤ n])，表示树的第 #cf_span[i] 条边连接顶点 #cf_span[ui] 和 #cf_span[vi]。
题目保证所给图是一棵树。
如果谜题无解，则仅输出一行 "_NO_"。
否则，第一行输出 "_YES_"，接下来的 #cf_span[n] 行每行输出一对整数 #cf_span[xi], #cf_span[yi] #cf_span[(|xi|, |yi| ≤ 1018)]，表示第 #cf_span[i] 个顶点对应的坐标点。
如果有多种解，输出任意一种即可。
在第一个样例中，树的一种可能位置如下：
## Input
第一行包含一个整数 #cf_span[n] #cf_span[(1 ≤ n ≤ 30)] —— 树的顶点数。接下来的 #cf_span[n - 1] 行每行包含两个整数 #cf_span[ui], #cf_span[vi] (#cf_span[1 ≤ ui, vi ≤ n])，表示树的第 #cf_span[i] 条边连接顶点 #cf_span[ui] 和 #cf_span[vi]。题目保证所给图是一棵树。
## Output
如果谜题无解，则仅输出一行 "_NO_"。否则，第一行输出 "_YES_"，接下来的 #cf_span[n] 行每行输出一对整数 #cf_span[xi], #cf_span[yi] #cf_span[(|xi|, |yi| ≤ 1018)]，表示第 #cf_span[i] 个顶点对应的坐标点。如果有多种解，输出任意一种即可。
[samples]
## Note
在第一个样例中，树的一种可能位置如下：
**Definitions**
Let $ n \in \mathbb{Z} $ be the number of vertices ($1 \leq n \leq 30$).
Let $ T = (V, E) $ be a tree with $ V = \{1, 2, \dots, n\} $ and $ E \subseteq \binom{V}{2} $, $ |E| = n - 1 $.
**Constraints**
1. The graph $ T $ is a tree (connected, undirected, acyclic).
2. Each vertex $ i \in V $ must be assigned a point $ (x_i, y_i) \in \mathbb{Z}^2 $ such that:
- All points are distinct: $ (x_i, y_i) \neq (x_j, y_j) $ for $ i \neq j $.
- For every edge $ (u, v) \in E $, the segment between $ (x_u, y_u) $ and $ (x_v, y_v) $ is axis-aligned (i.e., $ x_u = x_v $ or $ y_u = y_v $).
- No two segments intersect except possibly at shared endpoints.
3. $ |x_i|, |y_i| \leq 10^{18} $ for all $ i \in V $.
**Objective**
Find an embedding $ f: V \to \mathbb{Z}^2 $, $ f(i) = (x_i, y_i) $, satisfying the above constraints, or determine that no such embedding exists.
If such an embedding exists, output:
- "YES"
- $ n $ lines: $ x_i, y_i $ for $ i = 1, \dots, n $
Otherwise, output:
- "NO"