یک موسسه‌ی حمل و نقل در شهر $A$ قرار دارد و هواپیمایی دارد که با استفاده از آن کالاها را بین ۷ شهر $F،E،D،C،B،A$ و $G$ منتقل می‌کند (شکل زیر).

فاصله‌ی بین شهرها در تمام ورودی‌ها یکسان است. این فاصله‌ها در جدول شکل زیر نشان داده شده‌اند و در فایل DISTANCE.TXT در دسترس شما قرار خواهند گرفت.

هر روز صبح این موسسه باید تصمیم بگیرد که در آن روز به چه ترتیبی کالاها را منتقل کند. این ترتیب باید به صورتی باشدکه مجموع مسافت پیموده شده حداقل شود.

• هواپیما همواره از شهر $A$ شروع به حرکت می‌کند و پس از آن که کارش تمام شد باید به همین شهر بازگردد.
• هواپیما در هر لحظه فقط برای حمل یک کالا جا دارد.

برنامه‌ای بنویسید که با دریافت لیستی از سفارش‌های انتقال کالا، کوتاه‌ترین مسیری را پیدا کند که از $A$ شروع و به $A$ نیز ختم شود و تمام سفارش‌ها را انجام دهد.

لیست این سفارش‌ها در فایل ورودی ذخیره شده است. در سطر اول فایل تعداد سفارش‌ها که عددی طبیعی و کم‌تر یا مساوی با ۲۰ است، نوشته شده است. در سطرهای بعدی، برای هر یک از سفارش‌ها در یک خط یک زوج از حرف‌های $A$ تا $G$ که با یک فاصله از هم جدا شده‌اند، نوشته شده است که شهرهای مبدا و مقصد سفارش انتقال کالا را مشخص می‌کنند.

خروجی برنامه را در فایل خروجی بنویسید. در سطر اول این فایل طول کوتاه‌ترین مسیر، و در سطر بعد، دنباله‌ی شهرهای مسیر را به ترتیب بنویسید.

به مثال زیر توجه کنید. خروجی این مثال در شکل زیر نشان داده شده است.

• سوال بعد
• سوال قبل