P9614 [CERC2019] Ponk Warshall

**This problem is translated from [CERC 2019](https://contest.felk.cvut.cz/19cerc/solved.html) “[Ponk Warshall](https://contest.felk.cvut.cz/19cerc/solved/ponk.pdf)”.**

Listening to rock music changes your core DNA. This shocking and unbelievable fact was recently published in one of the top scientific journals on Earth, *Rock Nature Weekly*. Part of the research involved collecting DNA samples from volunteers before and after the rock concert season. The samples were processed, and various genes were isolated from them. For each person, each gene was isolated twice: the variant from before the rock season and the variant from after the rock season. These two variants are paired, and in many cases it was found that one variant is some permutation of the other. The next step of the research is to determine how the permutation happens. The common hypothesis is that the permutation is caused by a series of transpositions, i.e. so-called swaps. A swap is an event where exactly two nucleobases in the gene exchange their positions (the chemical details are not fully understood yet). No other nucleobases in the gene are affected by the swap. The positions of the two swapped nucleobases may be completely arbitrary. To predict and observe the movement of molecules during the permutation process, the researchers need to know the theoretical minimum number of swaps that can produce a specific nucleobase permutation in a gene. Recall that a nuclear DNA gene is a sequence of bases cytosine, guanine, adenine, and thymine, encoded as C, G, A, and T respectively. ### Brief statement Given two strings (the alphabet contains only `A`, `C`, `G`, or `T`), find the minimum number of swaps (swapping two letters) needed to transform the first string into the second string.

The input contains two lines. Each line contains a string of $N\ (1\le N\le 10^6)$ uppercase letters “A”, “C”, “G”, or “T”. These two strings represent a pair of specific gene versions. The first line is the gene before the rock season, and the second line is the same gene from the same person after the rock season. In both strings, the number of occurrences of each nucleobase is the same.

Output one integer, the minimum number of swaps needed to transform the first gene version into the second gene version.

Translated by ChatGPT 5