Time Limit: 2 sec / Memory Limit: 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