Çismani qrafik#10450
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.
Birinci sətir qrafın zirvə və kənarlarının sayını göstərən iki tam ədəd və (1 \leq n \leq 250\,000, 1 \leq m \leq 500\,000) ehtiva edir.
İkinci sətir qrafın zirvələrində yazılmış tam ədəd a_i (1 \leq a_i \leq 10^9) ehtiva edir.
Sonrakı sətirin hər biri iki tam ədəd və (1 \leq x, y \leq n) ehtiva edir ki, bu da -dən -yə istiqamətli kənarın mövcud olduğunu göstərir.
Yeganə sətirdə hər iki oyunçu optimal oynayarsa, oyunun sonunda alınacaq tam ədədi çıxarın.
Nümunə 1
Nümunə 2
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.
İ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.
Sonra Pətək gedir, o, 3-cü zirvəyə getməkdə maraqlıdır.
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.
( bal) verilmiş qraf — bütün kənarları bir istiqamətə yönəlmiş düz xəttdir;
( 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;
( bal) verilmiş qraf — dövrədir;
( bal) 1 \leq a_i \leq 2;
( bal) əlavə məhdudiyyətlər olmadan.