解决完问题后,大傻决定休息一下。她已经准备好开始她最喜欢的活动——折纸,但想起了她无法解决的难题。
树是一个无环的无向连通图。特别是,具有 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
注意
在第一个示例中,树的可能位置之一是: