Məsafələrin cəmi
Verilmiş istiqamətsiz çəkisiz qrafda iki zirvə u və v arasındakı məsafə d(u, v) onların arasındakı ən qısa yolda olan kənarların sayına bərabərdir. Bütün nizamsız cütlər (u, v) üçün d(u, v) cəmini tapın.
Giriş məlumatları
Birinci sətirdə iki tam ədəd n və m (2 ≤ n ≤ 10^5, n - 1 ≤ m ≤ n + 42) - qrafda zirvələrin və kənarların sayı müvafiq olaraq verilir. Zirvələr 1-dən n-ə qədər nömrələnmişdir.
Növbəti m sətirin hər biri iki tam ədəd x[i] və y[i] (1 ≤ x[i], y[i] ≤ n, x[i] ≠ y[i]) - i-ci kənarın uclarını göstərir.
Hər bir zirvə cütü arasında ən çox bir kənar mövcuddur.
Çıxış məlumatları
Tək tam ədəd çıxarın - qrafda bütün nizamsız zirvə cütləri arasındakı məsafələrin cəmi.
İzah
Birinci nümunədə, kənarla birləşdirilmiş dörd zirvə cütü arasındakı məsafə 1-ə bərabərdir və d(1, 4) = d(2, 4) = 2.