Понк Уоршалл#9767

Понк Уоршалл

1 секунда
128 мегабайтів
Дуже легка

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

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

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

Вхідні дані

Містить два рядки. Кожен рядок містить n~(1 \le n \le 10^6) великих літер "A", "C", "G" або "T". Два рядки представляють собою одну пару деяких версій гена. Перший рядок задає ген до рок-сезону, другий рядок задає той самий ген від тієї ж людини після рок-сезону. Кількість входжень кожної азотистої основи однакова в обох рядках.

Вихідні дані

Виведіть мінімальну кількість обмінів, що перетворюють першу версію гена у другу.

Приклади

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading