B - Star or Not 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 200

問題文

N 頂点 N-1 辺の木が与えられます。
頂点には 1,2,\ldots,N の番号がついており、i 本目の辺は頂点 a_i と頂点 b_i を結んでいます。

この木がスターであるか判定してください。

ただしスターとは、1 つの頂点から、他の全ての頂点に 1 本ずつ辺が出ている木のことです。

注記

「木」については、Wikipedia「木(数学)」 を参照してください。

制約

  • 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

Score : 200 points

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