Ayrılma dərəcəsi

Getdikcə bir-birinə bağlı olan dünyamızda, Yer üzündəki hər kəsin altı dərəcədən çox olmayan ayrılıq ilə digər hər kəslə əlaqəli olduğu güman edilirdi. Bu problemdə siz insanların müəyyən bir şəbəkəsi üçün maksimum ayrılma dərəcəsini tapmalısınız. İstənilən iki insan üçün ayrılıq dərəcəsi iki insanı bir araya gətirmək üçün aradan qaldırılmalı olan minimum əlaqə miqdarıdır. Şəbəkə üçün maksimum ayrılma dərəcəsi şəbəkədəki hər iki şəxs arasında ən böyük ayrılma dərəcəsidir. Şəbəkədə əlaqələr zənciri ilə bağlı olmayan bir neçə insan varsa, şəbəkə offline olur. Aşağıda göstərildiyi kimi, şəbəkə hər biri iki nəfəri birləşdirən simmetrik əlaqələr toplusu ilə təsvir olunur. Hər bir əlaqə iki insan arasındakı əlaqəni təmsil edir.

Giriş verilənləri

İnsanların şəbəkələrini təsvir edən bir neçə testdən ibarətdir. Hər bir məlumat dəsti üçün birinci sətir iki tam ədəddən ibarətdir: $p$ $(2\le p\le 50)$ - şəbəkədəki insanların sayı və $r$ $(r\ge 1)$ - şəbəkədəki əlaqələrin sayı. şəbəkə. Bu birinci sətirdən sonra $r$ münasibətləri var. Hər bir keçid şəbəkədə əlaqəli şəxslərin adlarını əks etdirən iki sətirdən ibarətdir. Adlar unikaldır və boşluq yoxdur. Bir şəxs birdən çox başqa şəxslə əlaqəli ola bildiyinə görə, ad məlumat dəstində bir neçə dəfə görünə bilər. Son testdən sonra iki sıfırdan ibarət sətir gəlir.

Çıxış verilənləri

Hər bir şəbəkə üçün onun nömrəsini çap edin, ardınca maksimum ayrılma dərəcəsi. Şəbəkə bağlantısı kəsilibsə, DISCONNECTED yazın. Cavabdan sonra hər şəbəkə üçün boş bir sətir çap edin. Nümunə çıxışında göstərilən formatdan istifadə edin.

Nümunələr

Qeyd

Birinci sınaqda şəbəkənin maksimum ayrılması dərəcəsi $2$ təşkil edir. İkinci sınaqda şəbəkə söndürülür.