Qrafın əlaqəliliyi

Verilmiş qraf n zirvə və m kənardan (1 ≤ n ≤ 1000, 1 ≤ m ≤ 7000) ibarətdir.

Qrafın əlaqəli olması üçün əlavə edilməli olan ən az kənar sayını və bu kənarları tapmaq tələb olunur.

Giriş məlumatları

Əvvəlcə n və m ədədləri verilir. Daha sonra qrafın kənarlarının təsviri gəlir - hər biri kənarın başlanğıcı və sonunu göstərən m cüt ədəd.

Çıxış məlumatları

Birinci sətirdə əlavə edilməli olan ən az kənar sayını k çıxarın. Sonrakı k sətirdə isə hər yeni kənarın başlanğıcı və sonunu göstərən 2 ədəd çıxarın.

Nümunələr