eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Понк Уоршалл

Понк Уоршалл

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Слушание рок-музыки меняет вашу ядерную ДНК. Этот поразительный и невероятный факт был недавно опубликован в Rock Nature Weekly, одном из ведущих научных журналов на планете. Частью исследования было взятие образцов ДНК у добровольцев как до, так и после сезона рок-концертов. Образцы были обработаны, и из них были выделены различные гены. Для каждого человека каждый ген был выделен дважды: вариант до рок-сезона и вариант после сезона. Эти два варианта были парными, и во многих случаях было обнаружено, что один вариант представляет собой некоторую перестановку другого варианта в паре.

Следующим шагом в исследовании является определение того, как происходят перестановки. Преобладающая гипотеза предполагает, что перестановка состоит из последовательности транспозиций, так называемых обменов. Обмен — это событие (его химия еще полностью не изучена), при котором ровно два азотистых основания в гене меняются местами. Никакие другие азотистые основания гена обменом не затрагиваются. Положения двух замененных нуклеотидных оснований могут быть совершенно произвольными.

Чтобы предсказать и наблюдать движение молекул в процессе перестановки, исследователям необходимо знать теоретическое минимальное количество перестановок, которые могут привести к конкретной перестановке азотистых оснований в гене. Напоминаем, что ген ядерной ДНК представляет собой последовательность азотистых оснований цитозина, гуанина, аденина и тимина, которые кодируются как C, G, A и T соответственно.

Вхідні дані

Содержит две строки. Каждая строка содержит n~(1 \le n \le 10^6) заглавных букв "A", "C", "G" или "T". Две строки представляют собой одну пару некоторых версий гена. Первая строка задает ген до рок-сезона, вторая строка задает тот же ген от того же человека после рок-сезона. Число вхождений каждого азотистого основания одинаково в обеих строках.

Вихідні дані

Выведите минимальное количество обменов, преобразующих первую версию гена во вторую.

Приклад

Вхідні дані #1
CGATA
ATAGC
Вихідні дані #1
2
Вхідні дані #2
CTAGAGTCTA
TACCGTATAG
Вихідні дані #2
7
Джерело 2019 ACM Central Europe (CERC), Прага, Ноябрь 29 - Декабрь 1, Задача I