GPS Я люблю тебя
Томас Т. Гармин получил 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.