Об'єднати два королівства#6590
Королівства Нлогонія та Квадрадонія вели тривалу та жахливу війну, яку історики назвали Майже Повністю Безглуздою (MPB), оскільки ніхто вже не пам'ятає, чому вона почалася. Коли війна MPB нарешті завершилася, обидва королівства вирішили зміцнити свої відносини, щоб уникнути подальшого кровопролиття, і звернулися до Міжнародного Консорціуму з Попередження Конфліктів (МКПК). МКПК запропонував побудувати дорогу, яка з'єднає місто в Нлогонії з містом у Квадрадонії, що сприятиме комерційному та культурному обміну між ними.
Нлогонія та Квадрадонія мають відповідно та міст. Дорожня система кожного королівства складається з набору двонаправлених доріг, які з'єднують пари різних міст у межах одного королівства, так що існує унікальний шлях (тобто послідовність послідовних доріг), яким можна дістатися з будь-якого міста в королівстві до будь-якого іншого міста в тому ж королівстві. "Розмір" такої дорожньої системи визначається як максимальна кількість доріг, які потрібно пройти, щоб подорожувати між будь-якою парою міст.
Оскільки МКПК не вказав, які саме два міста повинні бути з'єднані новою дорогою, що з'єднує два королівства, громадяни тепер стурбовані тим, що розмір об'єднаної дорожньої системи може бути занадто великим. Щоб запобігти другій війні MPB, ви хотіли б переконати їх, що це не так, і для цього вам потрібно обчислити очікуваний розмір отриманої дорожньої системи, припускаючи, що всі можливі дороги між двома королівствами однаково ймовірно будуть побудовані.
Перший рядок містить два цілі числа та , що представляють кількість міст у кожному з двох королівств (1 \leq N, Q \leq 4 \times 10^4). Міста в Нлогонії ідентифікуються різними цілими числами від до , а міста в Квадрадонії ідентифікуються різними цілими числами від до . Кожен з наступних N-1 рядків описує дорогу в Нлогонії з двома різними цілими числами та , що вказують, що дорога з'єднує місто з містом (1 \leq A, B \leq N). Кожен з наступних Q-1 рядків описує дорогу в Квадрадонії з двома різними цілими числами та , що вказують, що дорога з'єднує місто з містом (1 \leq C, D \leq Q). Дорожня система кожного королівства така, що існує рівно один шлях між кожною парою міст у королівстві.
Виведіть рядок з раціональним числом, що представляє очікуваний розмір дорожньої системи після об'єднання двох королівств, враховуючи, що всі можливі дороги, що з'єднують їх, однаково ймовірно будуть побудовані. Результат має бути виведений як раціональне число з точно трьома знаками після коми, округлене за необхідності.
Приклад 1