Language Barrier#13013

Language Barrier

It’s not about the money, it’s about sending a message.

In a network of people connected by a tree structure, person wants to send a message to person . There are 10^9 different languages numbered from to 10^9. Person speaks all languages in the interval [l_i, r_i].

Person starts with a piece of paper and can write the initial message in any language they speak. On each turn, the person currently holding the paper can do one of the following.

Find the minimum number of turns for person to receive the paper with a message written in a language they understand.

Input

The first line contains a single integer – the number of people.

The next n-1 lines each contain two integers and , describing an edge between people and in the tree.

The next lines each contain two integers l_i and r_i – the interval describing the languages that person speaks.

2 \le n \le 2 \cdot 10^5

1 \le u, v \le n for all edges,

u \ne v for all edges,

1 \le l_i \le r_i \le 10^9,

it is guaranteed that any person can send a message to any other person (possibly requiring a series of translations).

Output

Print a single integer – the minimum number of turns needed for person to receive the message in a language they understand.

Examples

Example

Loading
Loading

Note

In the sample, the tree is a path.

Person speaks languages , , . Person speaks languages , , . Person speaks languages , , . Person speaks languages , , .

One optimal solution is as follows. First, person writes the message in language . Then the people start to make turns.

  1. Person passes the paper to person .

  2. Person translates the message from language into language .

  3. Person passes the paper to person .

  4. Person passes the paper to person .

Person now has the message in language , which they understand. The minimum number of turns needed is four.