Fuel stations

Time limit2sMemory limit1024 MB

Summary

Given a DAG where each city except Samara has two outgoing roads, decide whether fuel stations can be placed so every route from Moscow to Samara has the same number of stations.

Level: Medium6 of 10
Topics: Graph, Dynamic programming
Solved: No attempts yet

Problem

The organizers of the Moscow-Samara car rally planned the fuel stops on the route carefully. They drew a map of every possible route. From each city except Samara, a participant can drive on one of two other roads to a city with a larger number.

All participants want to win, so they only move toward the goal. They cannot drive back along the road they came from, because they know that if they keep going forward, they will reach the goal anyway. Also, every city except Samara can be reached from Moscow by exactly one route.

The organizers want to place fuel stations in cities so that:

Moscow and Samara each have a fuel station.
If city $a$ has no fuel station and a car can drive from $a$ to city $b$ , then city $b$ must have a fuel station. (Cars do not need to drive two segments between cities on one station.)
Every path from Moscow to Samara passes the same number of fuel stations, so that all participants are in equal positions.

Help the organizers find out whether they can choose the cities with fuel stations so that all three conditions hold.

Input

The first line contains the number of cities $n$ ( $2 \le n \le 200000$ ). Moscow is city $1$ , and Samara is city $n$ . The next $n-1$ lines each contain a pair of integers $a_i$ , $b_i$ ( $i < a_i, b_i \le n$ ), the numbers of the cities that can be reached from city $i$ .

Output

Print YES if the organizers can choose the cities with fuel stations so that all the conditions are met. Otherwise, print NO.

Examples2

Example 1
Input
```
4
2 3
4 4
4 4
```
Expected output
```
YES
```
Example 2
Input
```
5
2 5
3 4
5 5
5 5
```
Expected output
```
NO
```