Мәселе ақшада емес, мәселе хабарлама жеткізуде.
Ағаш құрылымымен байланысқан $n$ адамнан тұратын желіде $1$-ші адам $n$-ші адамға хабарлама жібергісі келеді. $1$-ден $10^9$-ға дейін нөмірленген $10^9$ әртүрлі тіл бар. $i$-ші адам $[l_i, r_i]$ кесіндісіндегі барлық тілдерде сөйлейді.
$1$-ші адам бір парақ қағаздан бастайды және бастапқы хабарламаны өзі сөйлейтін кез келген тілде жаза алады. Әр жүрісте қағазды ұстап тұрған адам келесі әрекеттердің бірін орындай алады:
- Қағазды ағаштағы көршілес адамға беру.
- Егер ол қағазда қазір жазылған тілді түсінсе, оны өзі сөйлейтін кез келген басқа тілге аудару (түпнұсқаның үстінен жазу).
$n$-ші адам өзі түсінетін тілде жазылған хабарламасы бар қағазды алуы үшін қажетті ең аз жүрістер санын табыңыз.
Кіріс деректер
Бірінші жолда бір бүтін сан $n$ — адамдар саны берілген.
Келесі $n - 1$ жолдың әрқайсысында ағаштағы $u$ мен $v$ адамдарының арасындағы қырды сипаттайтын екі бүтін сан $u$ және $v$ берілген.
Келесі $n$ жолдың әрқайсысында $i$-ші адам сөйлейтін тілдерді сипаттайтын кесіндінің шеттері — екі бүтін сан $l_i$ және $r_i$ берілген.
Шығыс деректер
Бір бүтін санды — $n$-ші адам хабарламаны өзі түсінетін тілде алуы үшін қажетті ең аз жүрістер санын шығарыңыз.
Шектеулер
- $2 \le n \le 2 \cdot 10^5$,
- барлық қырлар үшін $1 \le u, v \le n$,
- барлық қырлар үшін $u \neq v$,
- $1 \le l_i \le r_i \le 10^9$,
- кез келген адам кез келген басқа адамға (мүмкін, бірнеше аудармалар тізбегі арқылы) хабарлама жібере алатынына кепілдік беріледі.
Мысал 1
4
1 2
2 3
3 4
1 3
2 4
3 5
4 6
4
Ескертпелер
Мысалда ағаш жол болып табылады.
$1$-ші адам $1, 2, 3$ тілдерінде сөйлейді. $2$-ші адам $2, 3, 4$ тілдерінде сөйлейді. $3$-ші адам $3, 4, 5$ тілдерінде сөйлейді. $4$-ші адам $4, 5, 6$ тілдерінде сөйлейді.
Оңтайлы шешімдердің бірі келесідей. Алдымен $1$-ші адам хабарламаны $3$ тілінде жазады. Содан кейін адамдар жүрістер жасай бастайды:
- $1$-ші адам қағазды $2$-ші адамға береді.
- $2$-ші адам хабарламаны $3$ тілінен $4$ тіліне аударады.
- $2$-ші адам қағазды $3$-ші адамға береді.
- $3$-ші адам қағазды $4$-ші адамға береді.
Енді $4$-ші адамда өзі түсінетін $4$ тіліндегі хабарлама бар. Қажетті ең аз жүрістер саны — төрт.