Galileo Galilei made a number of astronomic discoveries, but as corresponding observations may require many days to confirm, he often was not sure enough, to immediately publish them. For example, he once sent the message to a number of other scientists, containing the anagram:
smaismrmilmepoetaleumibunenugttauiras
The idea was, that when the necessary additional observations are made, he can explain to which exactly phrase this anagram is decoded, thus establishing his priority. You can google this story easily - and particularly how Kepler spent significant time to guess the meaning (and succeeded, though incorrectly).
This introduction just served to show that anagrams are not just an abstract puzzle, and may have practical value. However we are to solve much easier problem now, than one faced by Kepler.
So anagram is a shuffle of the letters in the word or phrase.
Regard the word CLOVER which is shuffled into anagram LRCOVE. Suppose we want to restore it by several
swaps of letters (not necessary adjacent). It seems we can't do better than in 5 swaps, e.g.:
From: LRCOVE
0 <=> 2 : CRLOVE
1 <=> 2 : CLROVE
2 <=> 3 : CLORVE
3 <=> 4 : CLOVRE
4 <=> 5 : CLOVER
It is easy to see that on each step we simply locate the next letter of the original word and swap it to its
proper place. This could take up to N-1 steps for N letters (the last will appear at its place for it simply
has no other place).
However, in some situation we may need less steps. For example DANDELION could be restored from NALDIEOND
in several ways. Straightforward approach may take 7 steps (luckily A is already at its place - just don't
disturb it):
From: NALDIEOND
0 <=> 3 : DALNIEOND
2 <=> 3 : DANLIEOND
3 <=> 8 : DANDIEONL
4 <=> 5 : DANDEIONL
5 <=> 8 : DANDELONI
6 <=> 8 : DANDELINO
7 <=> 8 : DANDELION
But it is possible to do better. See if you can do it in 5 swaps.
The problem is just about the same - given an anagram and the target word, please, suggest a sequence of swaps. Checker will accept it unless it could find better sequence itself.
Input: will give T - amount of anagrams to restore - in the first line. Next lines contain
anagrams and target words - a pair in every line.
Answer: should provide a series of swaps for each case. Each series should contain several pairs of indices
(0-based) describing swaps. Numbers in each pair should be separated with colon while pairs themselves
are linked into series with commas. Series are separated with spaces.
Example
input:
3
LRCOVE CLOVER
NRAAAMG ANAGRAM
AITC.SUEETIRLSIRORIPUSSTN SURREALISTIC.SUPERSTITION
answer:
0:2,1:2,2:3,3:4,4:5 4:1,0:1,3:6,6:5
0:5,1:6,2:15,3:11,4:7,6:12,7:12,8:21,14:20,15:19,16:21,18:22,21:23
here the long line is wrapped for readability