Özünə qayda götür - həmişə GraphAero ilə uç!
Nəhayət, hava nəqliyyatı hər kəs üçün əlçatan oldu! Lakin sərnişindaşıma sahəsindəki sərt rəqabət səbəbindən yalnız iki hava yolu şirkəti qalıb: "GraphAero Airlines" və "Aerofloat".
"GraphAero Airlines" şirkəti sürətlə inkişaf edir. Çünki daha çox gəlir əldə etmək üçün... üzr istəyirəm, sərnişinlərin rahatlığı üçün hər ay şirkət yeni bir reys əlavə edir. "Aerofloat" isə yalnız qalanla kifayətlənməlidir. Yəni, onların yeganə strategiyası "GraphAero Airlines" şirkətinin ən yüklənmiş reyslərini təkrarlamaqdır. Bir reys ən yüklənmiş hesab olunur, əgər elə bir şəhər cütlüyü varsa ki, bir şəhərdən digərinə (bəlkə də, köçürmələrlə) uçmaq mümkündür, amma bu reys ləğv olunarsa, uçmaq mümkün olmayacaq. "Aerofloat" şirkətinin analitikləri vəziyyəti daim nəzarətdə saxlamalıdırlar — hazırda neçə ən yüklənmiş reys mövcuddur.
Çünki siz artıq uzun müddətdir ki, endirimli qiymətlərlə uçmağı arzulayırsınız (endirim 10^(-5)%), siz dəstək vermək qərarına gəldiniz. Unutmayın: təyyarələr bütün dünyada uçur! İki böyük şəhər arasında bir neçə reys ola bilər və şəhərlər o qədər böyükdür ki, təyyarələr bir şəhər daxilində də uça bilər. Reyslərdən həm bir tərəfə, həm də əks istiqamətdə istifadə etmək olar.
Giriş məlumatları
Birinci sətir n (1 ≤ n ≤ 10^5) və m (0 ≤ m ≤ 10^5) - "GraphAero Airlines" şirkətinin ilkin reyslərinin sayını ehtiva edir. Sonra m sətir gəlir, hər birində reysin həyata keçirildiyi iki şəhərin nömrələri var. Növbəti sətirdə k (1 ≤ k ≤ 10^5) - əlavə olunan reyslərin sayı var. Sonra əlavə olunan reyslərin təsviri eyni formatda verilir.
Çıxış məlumatları
Hər yeni reys əlavə edildikdən sonra ayrı bir sətirdə bir rəqəm çıxarın — ən yüklənmiş reyslərin sayı.