Задача №113131. B
На сайте Берляндских Железных Дорог (БЖД) любой может купить билет. Для этого ему лишь нужно заполнить несложную форму, а затем пройти еще несколько простых шагов. Руководство БЖД недавно задумалось о том, насколько легко людям использовать эту форму, и поручило вам провести измерения, чтобы оптимизировать количество действий, нужных для заполнения формы.
Форма состоит из двух полей: станция отправления и станция назначения. Когда человек заходит на сайт, в этих полях уже введены станции — те, которые сайт считает наиболее вероятными. Также под каждым полем есть список названий некоторых, самых популярных, станций — клик по элементу списка подставляет название станции в соответствующее поле. Наконец, есть кнопка «Поменять местами станцию отправления и станцию назначения». Кроме того, конечно, пользователь также волен ввести названия нужных ему станций вручную. К сожалению, из-за ошибки в коде сайта, редактировать введенное или выбранное название нельзя, можно только ввести его заново.
Для целей эксперимента клик по кнопке смены станций отправления и назначения или по станции в списке популярных станций оценивается в одно очко действия. Ввод названия станции вручную стоит столько очков действия, сколько символов (включая пробелы и дефисы) содержит это название.
Вам нужно написать программу, которая по желаемым станциям отправления и назначения и начальному виду страницы (введенные станции, список популярных станций) определит минимальное количество очков действия, необходимое для того, чтобы ввести желаемые станции в соответствующие поля ввода.
В первой строке входного файла записано количество тестов в этом файле — единственное целое число K (1 ≤ K ≤ 10) . В последующих строках записаны K тестов.
Каждый отдельный тест состоит из нескольких строк. В первой строке теста записано название желаемой станции отправления. Во второй строке — название желаемой станции назначения. Гарантируется, что желаемая станция отправления не совпадает с желаемой станцией назначения.
В третьей строке — текущее введенное название станции отправления. В четвертой строке — текущее введенное название станции назначения.
В пятой строке — одно целое число N (0 ≤ N ≤ 100) — количество популярных вариантов станции отправления. В следующих N строках записаны эти варианты, по одному на строке. Все варианты различны.
После этого записано количество популярных вариантов станции назначения — одно целое число M (0 ≤ M ≤ 100) . В следующих M строках записаны эти варианты, по одному на строке. Все варианты различны.
Названия станций могут состоять из больших и маленьких латинских букв, пробелов и дефисов. Длина каждого названия не превышает 100 символов. Названия станций всегда начинаются и заканчиваются буквой. Любой пробел или дефис обязательно окружен буквами.
Для каждого теста выведите единственное целое число — количество очков действия, необходимое, чтобы ввести желаемые станции отправления и назначения в соответствующие поля. Выводите по одному ответу на строку. Порядок ответов должен соответствовать порядку тестов во входном файле.
Первый пример состоит из двух тестов. В первом тесте пользователю достаточно кликнуть по Nizhny Novgorod в списке популярных станций отправления, чтобы заменить Samara на желаемую станцию отправления, а затем кликнуть по Moskva в списке популярных станций назначения, чтобы заменить Petrozavodsk на желаемую станцию. Два клика требуют двух очков действия.
Во втором тесте у пользователя нет выбора, кроме как ввести названия станций вручную. Ввод Moskva потребует 6 очков действий, а ввод Nizhny Novgorod — 15 очков. В сумме требуется 21 очко.
Второй пример стоит из единственного теста. В этом тесте пользователю достаточно сначала кликнуть по Nizhny Novgorod в списке популярных станций отправления, а затем нажать на кнопку «Поменять местами станцию отправления и станцию назначения». На это потребуется два очка.
Иллюстрация ко второму примеру:
2 Nizhny Novgorod Moskva Samara Petrozavodsk 2 Arkhangelsk Nizhny Novgorod 2 Moskva Samara Moskva Nizhny Novgorod Moskv Novgorod 2 Arkhangelsk Ulyanovsk 2 Volgograd Samara
2 21
1 Moskva Nizhny Novgorod Arkhangelsk Moskva 3 Nizhny Novgorod Ulyanovsk Kazan 3 Volgograd Kazan Samara
2