Saytın sürətinin təhlili

Son bir il ərzində 1024 nömrəli məktəbin saytında səhifələrin sayı əhəmiyyətli dərəcədə artmışdır. Saytın strukturunu optimallaşdırmaq məqsədilə səhifələr arasındakı keçidlərin analizi aparılmasına qərar verilib.

Hər səhifənin yüklənmə vaxtı məlumdur. Həmçinin səhifələr arasında mövcud olan keçidlər haqqında məlumat da məlumdur. Əgər i və j səhifələri arasında keçid varsa, bu o deməkdir ki, j və i səhifələri arasında da keçid mövcuddur. A səhifəsindən B səhifəsinə minimum hansı vaxtda keçmək mümkün olduğunu müəyyən edin, A səhifəsinin yüklənmə vaxtını, B səhifəsinin yüklənmə vaxtını və aralıq səhifələrin yüklənmə vaxtını nəzərə alaraq.

Giriş məlumatları

Birinci sətir saytın səhifələrinin sayı olan N (1 ≤ N ≤ 1000) və keçidlərin sayı olan K (1 ≤ K ≤ 1000000) natural ədədlərini ehtiva edir.

İkinci sətirdə müvafiq səhifənin yüklənmə vaxtını göstərən N ədəd yazılıb. Daha sonra K sətir gəlir, hər birində iki ədəd x[i], y[i] (1 ≤ i ≤ K) - x[i], y[i] səhifələri arasında keçidin mövcudluğu.

Sonuncu sətirdə iki ədəd yazılıb - A və B (1 ≤ A, B ≤ N), keçid vaxtını hesablamaq lazım olan səhifələr.

Çıxış məlumatları

A və B səhifələri arasında keçidin minimum vaxtı və ya belə keçid mümkün deyilsə -1.