به تازگی هپید با اکثریت آرا رییس‌جمهور کشور شلوغ پلوغ شده است. او در اولین روزهای ریاست‌جمهوری خود تصمیم گرفت به جای یک پایتخت، کشور چندین پایتخت داشته باشد. دلیل وی هم این بود که هرچه افراد بیش‌تری در پایتخت زندگی کنند کشور پیشرفته‌تر می‌شود. کشور شلوغ پلوغ از تعدادی شهر تشکیل شده است که بین هر دو شهری دقیقا یک مسیر وجود دارد. اما از آنجا که هپید اهل مشورت است با هیات دولت خویش مشورت کرد و به این نتیجه رسیدند از آنجا که هر شهری که پایتخت می‌شود صنعتی و آلوده می‌شود راهی برای تفریح مردم بگذارند. بنابراین تصمیم گرفتند هر شهری که پایتخت می‌شود مثلا A حداقل یک شهر مجاور مثلا B داشته باشد که شهر B و تمام شهر‌هایی که از شهر B بدون عبور از A می‌توان به آن‌ها رسید هیچ‌کدام پایتخت نشده باشند.
حال شما به آن‌ها کمک کنید تا با شرط بالا طوری پایتخت‌ها را انتخاب کنند که بیشترین تعداد افراد در پایتخت‌ها زندگی کنند.
در تنها خط خروجی بیشترین تعداد افرادی که می‌توانند تحت پوشش پایتخت! قرار گیرند را چاپ کنید.
| ورودی نمونه | خروجی نمونه |
|---|---|
| 4 1 2 2 3 2 4 1 4 10 5 | 10 |
| 9 1 2 2 3 3 9 2 4 4 5 4 6 4 7 4 8 2 4 2 1 2 2 2 2 1 | 7 |