Evakuasiya
Bir Gizli təşkilatlardan biri, adını açıqlamağa icazəmiz olmayan, N yeraltı bunkerdən ibarət bir şəbəkədir. Bu bunkerlər bərabər uzunluqda tunellərlə birləşdirilib və istənilən bunkerdən digərinə (mütləq birbaşa deyil) çatmaq mümkündür. Xarici dünya ilə əlaqə bəzi bunkerlərdə yerləşən xüsusi gizli çıxışlar vasitəsilə həyata keçirilir.
Təşkilat fövqəladə vəziyyət zamanı personalın təxliyə planını hazırlamalıdır. Bunun üçün hər bir bunker üçün ən yaxın çıxışa çatmaq üçün nə qədər vaxt lazım olduğunu öyrənmək lazımdır. Sizə, bu cür məsələlər üzrə mütəxəssis olaraq, Gizli təşkilatın təsvirinə əsasən hər bir bunker üçün lazım olan vaxtı hesablamaq tapşırılıb. Sizin rahatlığınız üçün bunkerlər 1 -dən N-ə qədər nömrələnmişdir.
Giriş verilənləri
Əvvəlcə iki natural ədəd N, K (1 ≤ N ≤ 100000, 1 ≤ K ≤ N) - bunkerlərin və çıxışların sayı daxil edilir.
Sonra boşluqla ayrılmış K fərqli ədəd 1 -dən N-ə qədər olan bunkerlərin nömrələrini göstərir, harada ki, çıxışlar yerləşir.
Sonra M (1 ≤ M ≤ 100000) - tunellərin sayı gəlir. Sonra M cüt ədəd daxil edilir - tunellə birləşdirilmiş bunkerlərin nömrələri. Hər bir tunel üzrə hər iki istiqamətdə hərəkət etmək mümkündür. Təşkilatda bir bunkerdən eyni bunkərə aparan tunellər mövcud deyil, lakin bir bunker cütü arasında bir neçə tunel ola bilər.
Çıxış verilənləri
Boşluqla ayrılmış N ədəd çıxarın - hər bir bunker üçün çıxışa çatmaq üçün lazım olan minimal vaxt. Bir tunel üzrə hərəkət vaxtının 1 olduğunu qəbul edin.