Kosmik yarış
N planet Omicron Theta ərazisinin E4 sektorunda yerləşir. Ageira Technologies şirkəti burada Ticarət Xətləri şəbəkəsi quraraq kosmik nəqliyyatı tamamilə monopoliyaya alıb.
Hər bir Ticarət Xətti, planetlər cütü arasında iki tərəfli bir portaldır. Ageira Technologies, iqtisadi vəziyyətdən istifadə edərək, hər bir planetdən i digər planetə j bəzi Ticarət Xətləri vasitəsilə keçmək mümkün olacaq minimal sayda Ticarət Xətləri qurub. Bu məqsədlə n-1 Ticarət Xətti tikilib.
Uzaq planetlərin bir çox sakinləri bu vəziyyətdən narazıdırlar, çünki bir planetdən digərinə keçmək üçün çoxlu Ticarət Xətləri istifadə etməlidirlər. Səyahət nə qədər uzun olsa, kosmik quldurlarla qarşılaşma təhlükəsi də bir o qədər artır!
Nomad Industries şirkəti, Ageira şirkətinin rəqibi olaraq, bu vəziyyətdən istifadə etmək və öz Hyper Qapılar şəbəkəsini sektorda qurmaq istəyir ki, kosmik nəqliyyat bazarının bir hissəsini ələ keçirsin. Nomad Industries-in ixtisaslı mütəxəssisləri müəyyən ediblər ki, planetlər arasında i və j arasında Qapı tikməkdən əldə edilən mənfəət yalnız Ageira-nın Ticarət Xətləri ilə aşılmalı olan yolun uzunluğuna bərabər olacaq. Planet i və planet j arasındakı yolun uzunluğu dedikdə, planet i-dən planet j-ə keçmək üçün istifadə olunan minimal Ticarət Xətləri sayını nəzərdə tuturuq.
Nomad Industries, Ageira-nın siyasətinə bənzər bir prinsipə əməl etməyə qərar verib: Ticarət Xətlərindən ümumiyyətlə istifadə etmədən hər bir planetdən i digər planetə j keçmək mümkün olacaq minimal sayda Qapılar qurmaq.
Elə bir Qapı konfiqurasiyası tapacaq proqram yazın ki, tikilmiş bütün qapıların maksimal mənfəəti olsun. (Qeyd edək ki, şirkət dəqiq N-1 Qapı tikməlidir)
Giriş verilənləri
Giriş faylının ilk sətri N tam ədədindən ibarətdir (2 ≤ N ≤ 2000) – sektordakı planetlərin və müvafiq olaraq Ticarət Xətlərinin sayı. İlk sətirdən sonra N-1 sətir gəlir, hər biri boşluqla ayrılmış iki rəqəm ehtiva edir – Ageira Technologies-in Ticarət Xətləri ilə birləşdirilmiş planetlərin identifikatorları. Planetlərin identifikatorları 1 -dən N-ə qədər unikal tam ədədlərdir.
Çıxış verilənləri
Çıxış faylının ilk sətri tək tam ədəd olmalıdır – Nomad Industries şirkətinin maksimal mənfəəti.