GPS Я люблю тебе
"'markdown Томас Т. Гармін отримав GPS на свій день народження минулого року, і йому це дуже сподобалося! На жаль, іноді Том хотів обрати мальовничий маршрут, а не найкоротший, як пропонував GPS. Він трохи почитав інструкцію і дізнався, що може змінити алгоритм пошуку шляху за замовчуванням, вказавши дороги, які система GPS буде змушена використовувати при визначенні маршруту. Після деяких експериментів Том виявив, що часто достатньо примусити одну дорогу, щоб отримати бажаний маршрут. Однак для деяких звивистих маршрутів Тому доводилося примушувати більше доріг. Зрештою, Том почав турбуватися, що витрачає занадто багато часу на вибір доріг для примусу перед кожною поїздкою. Тепер, замість того, щоб насолоджуватися чудесами свого GPS, він проводить свої поїздки, мучаючись над наступним питанням: чи міг би він змусити свій GPS обрати мальовничий маршрут, використовуючи менше примусових доріг?
Чи можете ви врятувати цей любовний зв'язок, чи Том і його GPS приречені йти різними шляхами?
Вхідні дані
Вхідні дані для кожного тестового випадку складатимуться з кількох рядків. Перший рядок міститиме одне ціле число n < 100, що вказує на кількість кінцевих точок для доріг, пронумерованих від 0 до n-1. Далі йтимуть n рядків, кожен з яких містить n невід'ємних цілих чисел. Якщо j-те значення в рядку i є додатним, це вказує на довжину дороги від кінцевої точки i до кінцевої точки j; якщо значення дорівнює 0, це вказує на те, що між цими двома кінцевими точками немає дороги. Після цих рядків буде рядок виду m p_1 p_2 p_{3 }... p_m, що вказує на мальовничий маршрут, який хоче Том - маршрут містить m-1 доріг і проходить між кінцевими точками p_1 та p_m, відвідуючи кінцеві точки p_2, p_3 тощо, у такому порядку. Останній тестовий випадок буде завершено рядком, що містить '0'.
Зверніть увагу, що коли Том вказує свої примусові дороги своєму GPS, він вказує як їх напрямок, так і порядок. Усі маршрути є простими шляхами, а довжини всіх доріг ≤ 100.
Вихідні дані
Для кожного тестового випадку один рядок виходу наступного вигляду:
Case n: k
де k - це найменша кількість доріг, які Том повинен примусити, щоб GPS обрав вказаний маршрут. Ви повинні припустити, що якщо є кілька найкоротших шляхів, GPS завжди обирає наймальовничіший з них. Тому, якщо маршрут Тома є серед найкоротших, які використовують заданий набір примусових доріг, він буде обраний GPS. "'