Kompüter şəbəkəsi

Kompüter şəbəkəsi $n$ kompüterdən ibarətdir və bu kompüterlər $0$-dan $n-1$-ə qədər nömrələnmişdir. Hər bir kompüter mesaj aldıqdan sonra onu digər kompüterlərə ötürür. Əgər $x$ kompüterindən mesaj $y$ kompüterinə çata bilirsə, bu, $y$ kompüterindən mesajın $x$ kompüterinə çatacağı anlamına gəlmir. Sistem administratorları mesajın şəbəkədəki bütün kompüterlərə çatması üçün minimum neçə kompüterdən göndərilməli olduğunu müəyyən etmək istəyirlər.

Mesajların daha yaxşı ötürülməsi üçün administratorlar şəbəkəni bəzi kompüterlər arasında yeni əlaqələr əlavə edərək genişləndirməyi düşünürlər ki, istənilən kompüterdən göndərilən mesaj bütün digərlərinə yayılsın. Bunun üçün hər bir şəbəkə kompüterinin mesajı yaymaq üçün ilk ola biləcəyi minimum yeni bağlantı sayını müəyyən etmək lazımdır.

Bütün şəbəkəyə mesajın yayılması üçün minimum neçə kompüterdən göndərilməli olduğunu və istənilən kompüterdən göndərilən mesajın şəbəkədəki hər hansı digər kompüterə çatması üçün əlavə edilməli olan minimum yeni bağlantı sayını tapacaq proqram yazın.

Giriş verilənləri

Birinci sətir iki tam ədəd $n(1\le n\le 1600)$ və $m(0\le m\le 120000)$ ehtiva edir, kompüterlərin sayını və aralarındakı əlaqə kanallarının sayını təyin edir. Növbəti $m$ sətirdən hər biri mövcud əlaqə kanalını təsvir edir. Birinci ədəd mesajı göndərən kompüterin nömrəsi, ikinci ədəd isə mesajı alan kompüterin nömrəsidir.

Çıxış verilənləri

Bir sətirdə iki tam ədəd çıxarın — şəbəkənin bütün kompüterlərinə mesajın yayılması üçün başlanğıc olaraq istifadə edilə biləcək minimum kompüter sayı və şəbəkəni elə genişləndirmək üçün lazım olan minimum əlavə bağlantı sayı ki, istənilən kompüterdən göndərilən mesaj bütün digərlərinə çata bilsin.

Nümunələr