Bear and Drawing

题意翻译

Limak是一只小熊,他想学画画。 对于画画,人们总是从常见的房屋、栅栏、花朵开始尝试—— 但是,作为住在森林里的熊,Limak决定从树开始画。 树是n个节点n-1条边的无向连通图。 Limak有无限长的纸条,纸条上有两排平行的点,点的数量也是无限的,如图显示了纸条的一部分。 Limak想要把这些点中的n个作为树上的点,**注意,所有边只能在顶点处相交,绘制的树必须在同一平面上。** 如图是一个合法的绘画范例。 现在给出树的结构,请你回答:Limak能够画出这棵树吗? 输入包含了n(n<=100000)和n-1条边,保证为合法的树。 输出一行一个字符串,表示Limak是否能够画出这棵树,输出"Yes"或"No"(不包括引号)。

题目描述

Limak is a little bear who learns to draw. People usually start with houses, fences and flowers but why would bears do it? Limak lives in the forest and he decides to draw a tree. Recall that tree is a connected graph consisting of $ n $ vertices and $ n-1 $ edges. Limak chose a tree with $ n $ vertices. He has infinite strip of paper with two parallel rows of dots. Little bear wants to assign vertices of a tree to some $ n $ distinct dots on a paper so that edges would intersect only at their endpoints — drawn tree must be planar. Below you can see one of correct drawings for the first sample test. ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF573C/3e1f6bfb27269bc2d4c98e1421026d340bfdb0da.png)Is it possible for Limak to draw chosen tree?

输入输出格式

输入格式


The first line contains single integer $ n $ ( $ 1<=n<=10^{5} $ ). Next $ n-1 $ lines contain description of a tree. $ i $ -th of them contains two space-separated integers $ a_{i} $ and $ b_{i} $ ( $ 1<=a_{i},b_{i}<=n,a_{i}≠b_{i} $ ) denoting an edge between vertices $ a_{i} $ and $ b_{i} $ . It's guaranteed that given description forms a tree.

输出格式


Print "Yes" (without the quotes) if Limak can draw chosen tree. Otherwise, print "No" (without the quotes).

输入输出样例

输入样例 #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