GPS Я люблю тебе#2680

GPS Я люблю тебе

1 секунда

64 мегабайти

Складна

Томас Т. Ґармін отримав GPS-навігатор на свій день народження минулого року, і він був у захваті! На жаль, іноді Том хотів поїхати мальовничим маршрутом, а не найкоротшим, який пропонував GPS. Почитавши інструкцію, він дізнався, що алгоритм GPS можна обійти, вказавши дороги, якими система зобов'язана провести маршрут. Після кількох експериментів Том з'ясував, що часто достатньо примусити вибрати одну дорогу для отримання потрібного маршруту. Але для складніших маршрутів доводилося змушувати GPS використовувати більше доріг. Згодом Том почав перейматися, що витрачає забагато часу на підбір доріг перед кожною поїздкою. Тепер, замість того щоб тішитися GPS, він проводить поїздки, задумуючись над таким питанням: чи міг би він примусити GPS вибрати мальовничий маршрут, використавши менше примусових доріг?

Чи врятуєте ви цю любов, чи Том і його GPS приречені розлучитися?

Вхідні дані

Вхід для кожного тесту складається з кількох рядків. Перший рядок містить одне ціле число $n < 100$ n < 100 — кількість кінцевих точок доріг, пронумерованих від $0$ до $n - 1$ n-1. Далі йдуть $n$ рядків, кожен з яких містить $n$ невід'ємних цілих чисел. Якщо $j$ -те число в $i$ -му рядку додатне, це означає, що існує дорога довжини, вказаної цим числом, з точки $i$ до точки $j$ ; якщо значення $0$ , між цими двома точками дороги немає. Після цих рядків буде рядок виду $m p_{1} p_{2} p_{3} \dots p_{m}$ m\ p_1\ p_2\ p_{3}\ \ldots\ p_m, який задає бажаний мальовничий маршрут Тома: маршрут містить $m - 1$ m-1 доріг і проходить від точки $p_{1}$ p_1 до $p_{m}$ p_m, відвідуючи точки $p_{2}$ p_2, $p_{3}$ p_3 тощо у такому порядку. Останній тестовий випадок завершується рядком, що містить $0$ .

Зверніть увагу, що коли Том вказує примусові дороги GPS, він визначає як їхній напрямок, так і порядок проходження. Усі маршрути — прості шляхи, і всі довжини доріг не перевищують $100$ .

Вихідні дані

Для кожного тесту виведіть один рядок у такому форматі:

Case n: k

де $k$ — це мінімальна кількість доріг, які Том має примусово вказати, щоб GPS обрав заданий маршрут. Вважайте, що якщо існує кілька найкоротших шляхів, GPS завжди вибирає наймальовничіший з них. Тому, якщо маршрут Тома належить до найкоротших для заданої множини примусових доріг, він і буде вибраний GPS.

Приклади

Приклад 1