G - Is it a tree? Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 6 点

問題文

N 頂点 N-1 辺の無向グラフが与えられます。i \, (1 \leq i \leq N-1) 番目の辺は頂点 A_i と頂点 B_i を結んでいます。

与えられるグラフが木かどうか判定してください。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \lt B_i \leq N
  • (A_i, B_i) \neq (A_j, B_j) \, (i \neq j)
  • 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 B_1
\vdots
A_{N-1} B_{N-1}

出力

与えられるグラフが木なら Yes と、木でないなら No と出力せよ。

入力例 1

4
1 3
3 4
2 3

出力例 1

Yes

与えられるグラフは下図の通りです。

sample1

入力例 2

4
1 2
2 3
1 3

出力例 2

No

与えられるグラフは下図の通りです。

sample2

Score : 6 points

Problem Statement

You are given an undirected graph with N vertices and N-1 edges. The i-th (1 \leq i \leq N-1) edge connects Vertex A_i and Vertex B_i.

Determine whether the given graph is a tree.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \lt B_i \leq N
  • (A_i, B_i) \neq (A_j, B_j) \, (i \neq j)
  • All values in input are integers.

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 tree, print Yes; otherwise, print No.

Sample Input 1

4
1 3
3 4
2 3

Sample Output 1

Yes

The figure below illustrates the given graph.

sample1

Sample Input 2

4
1 2
2 3
1 3

Sample Output 2

No

The figure below illustrates the given graph.

sample2