SPOJ in Armenian

     Մի թագավորությունում կա 2 մարզ։ Մարզերը հարևան են, բայց կապող ճանապարհ չունեն։ Մարզերը բաղկացած են համապատասխանաբար N և M քաղաքներից։ Քաղաքները միմիանց միացված են երկկողմանի ուղիներով։ Թագավորության կառավարիչը՝ սպարապետ Սպարիկը, շատ ժլատ է, և ամեն մարզում ոուղիները քաղաքների միջև այնպես է կառուցել, որ հնարավոր լինի ցանկացած 2 քաղաքի միջև ճամփորդել մեկ և միայն մեկ ճանապարհով։ Սպարապետը այժմ ցանկանում է միացնել այս 2 մարզերը, սակայն նրա ժլատությունը նրան թույլ է տալիս կառուցէլ ընդամենը մի ուղի։ Այդ ուղին պետք է միացնի մեկական քաղաք ամեն մարզից։ Սպարիկին այժմ հետաքրքրում է, եթե նա միացնի մարզերը բոլոր հնարավոր ձևերով, ինչքան կլինի ստացված մեծ մի մարզում իրարից ամենահեռու 2 քաղաքների միջև եղած ճանապարհների երկարության միջին թվաբանականը։

Մուտք

Առաջին տողում տրված է մարզերում քաղաքների քանակը։ Հաջորդ N - 1 տողում տրված են առաջին մարզի ուղիները,  M - 1 ֊ում՝ երկրորդ։

Ելք

Ստացված մարզի հնարավոր տրամագծերի միջին թվաբանականը։

Մուտք

Առաջին տողում տրված է մարզերում քաղաքների N և M քանակները (1 <= N, M <= 10⁶)։ Հաջորդ N - 1 տողում տրված են առաջին մարզի ուղիները,  M - 1 ֊ում՝ երկրորդ։

Ելք

Ստացված մարզի հնարավոր տրամագծերի միջին թվաբանականը։ Պատասխանը արտածել 10^-3 ճշտությամբ։

Օրինակ

Մուտք.

4 5
1 2 
2 3 
4 2 
2 3 
3 4 
4 1
4 5

Ելք.

5.350