102251: [AtCoder]ABC225 B - Star or Not

Problem Statement

You are given a tree with $N$ vertices and $N-1$ edges.
The vertices are numbered $1,2,\ldots,N$. The $i$-th edge connects Vertex $a_i$ and Vertex $b_i$.

Determine whether this tree is a star.

Here, a star is a tree where there is a vertex directly connected to all other vertices.

Notes

For the definition of a tree, see Tree (graph theory) - Wikipedia.

Constraints

• $3 \leq N \leq 10^5$
• $1 \leq a_i \lt b_i \leq N$
• The given graph is a tree.

Input

Input is given from Standard Input in the following format:

$N$
$a_1$ $b_1$
$\vdots$
$a_{N-1}$ $b_{N-1}$

Output

If the given graph is a star, print Yes; otherwise, print No.

Sample Input 1

5
1 4
2 4
3 4
4 5

Sample Output 1

Yes

The given graph is a star.

Sample Input 2

4
2 4
1 4
2 3

Sample Output 2

No

The given graph is not a star.

Sample Input 3

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

Sample Output 3

Yes

问题描述

给你一棵有N个顶点和N-1条边的树。顶点编号为1,2,\ldots,N。第i条边连接顶点a_i和顶点b_i。

判断这棵树是否为星形。

这里的星形是指有一个顶点直接与其他所有顶点相连的树。

注释

关于树的定义，请参见树（图论）- 维基百科。

约束

• 3 \leq N \leq 10^5
• 1 \leq a_i \lt b_i \leq N
• 给定的图是一棵树。

输入

输入格式如下：

$N$
$a_1$ $b_1$
$\vdots$
$a_{N-1}$ $b_{N-1}$

输出

如果给定的图是星形，打印Yes；否则，打印No。

样例输入1

5
1 4
2 4
3 4
4 5

样例输出1

Yes

给定的图是星形。

样例输入2

4
2 4
1 4
2 3

样例输出2

No

给定的图不是星形。

样例输入3

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

样例输出3

Yes