← 返回题目列表

Codeforces · 761/E

E. 达莎和谜题

中文机器翻译题面 查看原题

解决完问题后,大傻决定休息一下。她已经准备好开始她最喜欢的活动——折纸,但想起了她无法解决的难题。

树是一个无环的无向连通图。特别是,具有 n 个顶点的树中始终有 n - 1 条边。

该谜题是将顶点定位在笛卡尔平面上具有积分坐标的点上,使得顶点之间由边连接的线段与坐标轴平行。此外,线段仅允许在其末端相交。不同的顶点应该放置在不同的点上。

帮助 Dasha 找到在平面上定位树顶点的任何合适方法。

可以保证,如果可以在不违反上面给出的条件的情况下将树顶点定位在平面上,那么您可以使用积分坐标绝对值不超过 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 个顶点的点的坐标。

如果有多个解决方案,请打印其中任何一个。

示例

输入 #1

7
1 2
1 3
2 4
2 5
3 6
3 7

输出 #1

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

输出 #2

NO

输入 #3

4
1 2
2 3
3 4

输出 #3

YES
3 3
4 3
5 3
6 3

注意

在第一个示例中,树的可能位置之一是: