İki krallığı birləşdirin

Nlogonia və Kvadradonia krallıqları uzun və mənasız bir müharibə apardılar ki, tarixçilər bu müharibəni demək olar ki, tamamilə mənasız (ACM) adlandırdılar, çünki indi heç kim onun niyə başladığını xatırlamır. ACM müharibəsi nəhayət bitdikdə, iki krallıq daha çox qan tökülməsinin qarşısını almaq üçün əlaqələrini gücləndirməyə qərar verdilər və bu səbəbdən Münaqişələrin Qarşısının Alınması üzrə Beynəlxalq Konsorsiuma (ICPC) müraciət etdilər. ICPC, Nlogonia şəhərlərindən birini Kvadradonia şəhərlərindən biri ilə birləşdirən bir yol tikməyi tövsiyə etdi, beləliklə iki krallıq arasında ticarət və mədəni mübadilə mümkün oldu.

Nlogonia və Kvadradonia müvafiq olaraq N və Q şəhərlərinə malikdir. Hər bir krallığın yol sistemi eyni krallıqda olan müxtəlif şəhər cütlərini birləşdirən ikitərəfli yollardan ibarətdir ki, bir krallıqda hər hansı bir şəhərdən digər şəhərə getmək üçün unikal bir yol (yəni ardıcıl yolların sırası) mövcuddur. Belə bir yol sisteminin "ölçüsü" bir krallıqda hər hansı bir şəhər cütü arasında səyahət etmək üçün götürülməsi lazım olan maksimum yol sayıdır.

ICPC iki krallığı birləşdirən yeni yolun hansı iki şəhəri birləşdirməli olduğunu dəqiq göstərmədiyi üçün, vətəndaşlar indi birləşmiş yol sisteminin ölçüsünün çox böyük ola biləcəyindən narahatdırlar. İkinci ACM müharibəsinin qarşısını almaq üçün onları bunun belə olmadığına inandırmaq istəyirsiniz və bu məqsədlə, iki krallıq arasında mümkün olan bütün yolların eyni dərəcədə tikilmə ehtimalını nəzərə alaraq, yaranan yol sisteminin gözlənilən ölçüsünü hesablamalısınız.

Giriş

Birinci sətir hər iki krallıqda olan şəhərlərin sayını göstərən N və Q tam ədədlərini ehtiva edir (1 ≤ N, Q ≤ 4×10^4). Nlogonia şəhərləri 1-dən N-ə qədər müxtəlif tam ədədlərlə, Kvadradonia şəhərləri isə 1-dən Q-ə qədər müxtəlif tam ədədlərlə müəyyən edilir. Növbəti N-1 sətirin hər biri Nlogonia-da bir yolu təsvir edir və iki fərqli tam ədəd A və B göstərir ki, bu yol şəhər A ilə şəhər B-ni birləşdirir (1 ≤ A, B ≤ N). Növbəti Q-1 sətirin hər biri Kvadradonia-da bir yolu təsvir edir və iki fərqli tam ədəd C və D göstərir ki, bu yol şəhər C ilə şəhər D-ni birləşdirir (1 ≤ C, D ≤ Q). Hər bir krallığın yol sistemi elədir ki, krallıqda hər bir şəhər cütü arasında dəqiq bir yol mövcuddur.

Çıxış

Bir sətirdə iki krallıq birləşdirildikdən sonra yol sisteminin gözlənilən ölçüsünü göstərən rasional bir ədəd çıxarın, nəzərə alaraq ki, onları birləşdirən bütün mümkün yolların tikilməsi eyni dərəcədə ehtimal olunur. Nəticə dəqiq üç ondalık rəqəmlə, lazım gələrsə yuvarlaqlaşdırılaraq çıxarılmalıdır.