← 返回题目列表

Codeforces · 573/C

C. 熊和绘图

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

Limak 是一只学习画画的小熊。人们通常从房子、栅栏和鲜花开始,但为什么熊会这么做呢?利马克住在森林里,他决定画一棵树。

回想一下,树是一个由 n 个顶点和 n - 1 个边组成的连通图。

Limak 选择了一棵有 n 个顶点的树。他有一张无限长的纸条,上面有两排平行的点。小熊想要将一棵树的顶点分配给纸上的一些 n 个不同的点,以便边缘仅在端点处相交 - 绘制的树必须是平面的。下面您可以看到第一个样本测试的正确图纸之一。

Limak 可以画出选定的树吗?

输入

第一行包含单个整数 n (1 ≤ n ≤ 105)。

接下来的 n - 1 行包含树的描述。其中第 i 个包含两个空格分隔的整数 ai 和 bi (1 ≤ ai, bi ≤ n, ai ≠ bi),表示顶点 ai 和 bi 之间的边。保证给定的描述形成一棵树。

输出

如果 Limak 可以绘制所选树,则打印“是”(不带引号)。否则,打印“No”(不带引号)。

示例

输入 #1

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

输出 #1

Yes

输入 #2

13
1 2
1 3
1 4
2 5
2 6
2 7
3 8
3 9
3 10
4 11
4 12
4 13

输出 #2

No