Çismani qrafik

Vasif və Pətək bir ədədi qraf tapdılar — hər zirvəsində bir ədəd yazılmış əlaqəli istiqamətli qraf.

Oğlanlar bu qraf üzərində oyun oynamağa qərar verdilər. Onlar fiquru 1 nömrəli zirvəyə yerləşdirdilər. Bir gedişdə ya oyunu bitirib fiqurun olduğu zirvədən ədəd götürə, ya da fiquru istiqamətli kənar üzrə qonşu zirvəyə keçirə bilərlər. Əgər $10^{100}$ gedişdən sonra oyun bitməzsə, fiqurun olduğu zirvədən ədəd götürülür.

Vasif oyuna başlayır və məqsədi ədədi maksimumlaşdırmaqdır, Pətək isə onu minimumlaşdırmağa çalışır. Hər iki oyunçu optimal oynayarsa, oyunun sonunda alınacaq ədədi tapın.

Giriş verilənləri

Birinci sətir qrafın zirvə və kənarlarının sayını göstərən iki tam ədəd $n$ və $m$ ($1\le n\le 250000,1\le m\le 500000$) ehtiva edir.

İkinci sətir qrafın zirvələrində yazılmış $n$ tam ədəd $a_i$ ($1\le a_i\le 10^9$) ehtiva edir.

Sonrakı $m$ sətirin hər biri iki tam ədəd $x$ və $y$ ($1\le x,y\le n$) ehtiva edir ki, bu da $x$-dən $y$-yə istiqamətli kənarın mövcud olduğunu göstərir.

Çıxış verilənləri

Yeganə sətirdə hər iki oyunçu optimal oynayarsa, oyunun sonunda alınacaq tam ədədi çıxarın.

Nümunələr

Qeyd

Birinci nümunədə, şəkil 1-də birinci nümunədən olan qraf təsvir edilmişdir. Zirvələrdə zirvənin nömrəsi və oyundakı ədəd mötərizədə yazılmışdır.

1. İlk gedişi Vasif edir, o, dərhal oyunu dayandıra bilər və ya 2-ci zirvəyə gedə bilər. Ən yaxşısı kənar üzrə getməkdir.

2. Sonra Pətək gedir, o, 3-cü zirvəyə getməkdə maraqlıdır.

3. Sonda, əgər Vasif 1-ci zirvəyə gedərsə, Pətək oyunu 1 ədədi ilə bitirəcək, buna görə də dərhal oyunu 4 ədədi ilə bitirmək daha yaxşıdır.

İkinci nümunədə, şəkil 2-də ikinci nümunədən olan qraf təsvir edilmişdir.

Burada oğlanlar növbə ilə bütün $10^{100}$ addımı edəcəklər, nəticədə fiqur 1-ci zirvədə dayanacaq.

Qiymətləndirmə

1. ($6$ bal) verilmiş qraf — bütün kənarları bir istiqamətə yönəlmiş düz xəttdir;

2. ($8$ bal) verilmiş qraf — 1 zirvəsində kökü olan və bütün kənarları kökdən aşağıya yönəlmiş ağacdır;

3. ($14$ bal) verilmiş qraf — dövrədir;

4. ($26$ bal) $1\le a_i\le 2$;

5. ($46$ bal) əlavə məhdudiyyətlər olmadan.