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.