Minimal Swap Transformation

At a rock concert, your very core DNA might change! Recent research published in one of Earth's top scientific journals, Rock Nature Weekly, revealed that the two variants of DNA collected before and after the rock season are rearrangements of each other. In this study, each gene is examined in two states: pre-rock season and post-rock season. In many cases, one variant appears to be a permutation of the other.

The next step for researchers is to understand how such permutations occur. A common hypothesis suggests that a series of exchanges are responsible. An exchange is defined as an event in which exactly two nucleobases in the gene swap positions, leaving all other nucleobases unaffected. The positions of the swapped nucleobases can be arbitrary.

Given two DNA sequences consisting only of the characters A, C, G, and T – where the second sequence is a permutation of the first – your task is to determine the theoretical minimum number of exchanges required to transform the first sequence into the second. It can be shown that if we represent the transformation as a permutation with cycles, the minimum number of swaps needed is given by:

[ \text{Minimum Swaps} = \sum_{i} (|cycle_i| - 1), , ]

where each cycle_i is one of the disjoint cycles in the permutation mapping from the first sequence to the second.

inputFormat

The input consists of two lines:

1. The first line contains a DNA sequence S (a string with characters chosen from {A, C, G, T}).
2. The second line contains a DNA sequence T of the same length as S, which is a permutation of S.

outputFormat

Output a single integer representing the minimum number of swaps required to transform S into T.

sample

ACGT
TGCA

2