Böyük dəyişikliklər

Təpəgözlər ölkəsində n şəhər mövcuddur. Padşah bu şəhərləri n - 1 ikitərəfli hava xətti ilə birləşdirmək istəyir ki:

• Hər bir hava xətti iki fərqli şəhəri birləşdirsin.

• Hər bir şəhərdən digərinə birbaşa və ya köçürmə ilə çatmaq mümkün olsun.

Şəhərin əlçatanlığı, onun birbaşa hava xətləri ilə birləşdirildiyi şəhərlərin sayıdır. Padşah istəyir ki, krallığın bütün şəhərləri arasında əlçatanlığın maksimum dəyəri mümkün qədər böyük olsun.

Şəhərləri bu tələblərə uyğun birləşdirmək üçün neçə fərqli yol var?

Giriş məlumatları

Bir tam ədəd n (2 ≤ n ≤ 10^9) - şəhərlərin sayı.

Çıxış məlumatları

Bir tam ədəd çıxarın - məsələnin cavabı.

İzah

Üç şəhər üçün əlçatanlığın mümkün maksimum dəyəri 2-dir. Bu dəyərə çatmaq üçün üç müxtəlif birləşmə variantı mümkündür: (1,2) və (2,3), (1,3) və (2,3), (1,2) və (1,3).