Понк Уоршалл
Слушание рок-музыки меняет вашу ядерную ДНК. Этот поразительный и невероятный факт был недавно опубликован в Rock Nature Weekly, одном из ведущих научных журналов на планете. Частью исследования было взятие образцов ДНК у добровольцев как до, так и после сезона рок-концертов. Образцы были обработаны, и из них были выделены различные гены. Для каждого человека каждый ген был выделен дважды: вариант до рок-сезона и вариант после сезона. Эти два варианта были парными, и во многих случаях было обнаружено, что один вариант представляет собой некоторую перестановку другого варианта в паре.
Следующим шагом в исследовании является определение того, как происходят перестановки. Преобладающая гипотеза предполагает, что перестановка состоит из последовательности транспозиций, так называемых обменов. Обмен — это событие (его химия еще полностью не изучена), при котором ровно два азотистых основания в гене меняются местами. Никакие другие азотистые основания гена обменом не затрагиваются. Положения двух замененных нуклеотидных оснований могут быть совершенно произвольными.
Чтобы предсказать и наблюдать движение молекул в процессе перестановки, исследователям необходимо знать теоретическое минимальное количество перестановок, которые могут привести к конкретной перестановке азотистых оснований в гене. Напоминаем, что ген ядерной ДНК представляет собой последовательность азотистых оснований цитозина, гуанина, аденина и тимина, которые кодируются как C, G, A и T соответственно.
Входные данные
Содержит две строки. Каждая строка содержит заглавных букв "A", "C", "G" или "T". Две строки представляют собой одну пару некоторых версий гена. Первая строка задает ген до рок-сезона, вторая строка задает тот же ген от того же человека после рок-сезона. Число вхождений каждого азотистого основания одинаково в обеих строках.
Выходные данные
Выведите минимальное количество обменов, преобразующих первую версию гена во вторую.