Kənarların minimallaşdırılması#11217

Kənarların minimallaşdırılması

1 saniyə

128 meqabayt

Çox çətin

Bessinin $n$ ədəd düyünü ( $1, 2, \dots, n$ 1, 2, \ldots, n ilə nömrələnmiş) və $m$ ədəd kənarı olan əlaqəli, istiqamətsiz qrafı $G$ var. $G$ -də öz-özünə kənarlar ola bilər (bir düyünü özü ilə birləşdirən kənar), ancaq paralel kənarlar yoxdur (eyni düyünlər arasında bir neçə kənar).

$f_{G} (a, b)$ f_G(a, b) funksiyası belə müəyyən olunur: əgər $1$ -ci düyündən $a$ -cı düyünə tam $b$ kənar üzərindən keçən yol varsa ( $1 \leq a \leq n$ 1 \le a \le n, $0 \leq b$ 0 \le b), bu funksiya doğru olur, əks halda səhv olur. Hər hansı bir kənardan birdən çox dəfə keçilərsə, bu kənar hər dəfəsində ayrıca sayılır.

Elsa Bessinin qrafını təkrarlamaq istəyir. Xüsusilə $G^{'}$ G' adlı istiqamətsiz bir qraf qurmaq istəyir ki, $f_{G^{'}} (a, b) = f_{G} (a, b)$ f_{G'}(a, b) = f_G(a, b) hamısı üçün doğrudur.

Elsa ən az iş görmək istəyir, ona görə də mümkün olan ən kiçik (kənar sayına görə) qrafı qurmaq istəyir. Tapşırığınız — $G^{'}$ G' üçün mümkün olan minimal kənar sayını tapmaqdır.

Bütün testlər üzrə $n$ -lərin cəmi $1 0^{5}$ 10^5-dən çox olmayacaq, $m$ -lərin cəmi isə $2 \cdot 1 0^{5}$ 2 \cdot 10^5-dən çox olmayacaq.

Giriş

Birinci sətrdə $t$ ( $1 \leq t \leq 5 \cdot 1 0^{4}$ 1 \le t \le 5 \cdot 10^4) ədəd testin sayı verilib.

Hər testin ilk sətrində $n$ və $m$ ( $2 \leq n \leq 1 0^{5}$ 2 \le n \le 10^5, $n - 1 \leq m \leq \frac{n ^{2} + n}{2}$ n - 1 \le m \le \frac{n^2 + n}{2}) ədədləri – düyün və kənar sayı verilir.

Sonrakı $m$ sətrin hər biri iki tam ədəd $x$ və $y$ ( $1 \leq x \leq y \leq n$ 1 \le x \le y \le n) verir, $G$ qrafında kənar var deməkdir.

Testlər ardıcıl olaraq boş sətrlərlə ayrılır.

Çıxış

Hər test üçün $G^{'}$ G' üçün mümkün minimal kənar sayını ayrıca sətirdə çap edin.

Nümunələr

Birinci testdə Elsa $G^{'}$ G' qrafını $G$ -dən başlayıb $(2, 5)$ kənarını silə, və ya sadəcə aşağıdakı kimi kənarlarla qurmaq olar (Elsa yalnız $G$ -dəki kənarları silməklə məhdudlaşmır):

Elsa heç vaxt $n - 1$ n - 1-dən daha az kənarla əlaqəli $G^{'}$ G' qrafı qura bilməz.

Nümunə 1