BRICKS  New bricks disorder
You have n bricks arranged in a line on the table. There is exactly one letter on each of them. Your task is to rearrange those bricks so that letters on them create some specified inscription. While rearanging you can only swap adjacent bricks with specified letters (you are given m pairs (a1,b1),...,(am,bm) and you are only allowed to swap bricks with ai on one of them and bi on the second, for some i=1,..,m). You should check if it is possible to accomplish this  and if it is  calculate minimal needed number of swaps.
Input
There is a single integer c on the first line of input. Then c test cases follow: each of them consists of two lines of small letters (a..z) with lengths not exceeding 100000 (descriptions of starting and ending configurations), one integer m in the next line and then m lines with two letters ai,bi in each of them.
Output
For each test case you should print 1 if it is not possible to rearrange bricks or the minimal number of swaps if it is possible (if so, output this value modulo 2^{32}).
Example
Input: 4 ab ba 0 abc cba 3 ab cb ca cabbbc cbabbc 1 ab abba baab 1 ab Output: 1 3 1 2Warning: large Input/Output data, be careful with certain languages
hide comments
the_imp:
20151004 08:24:48
Anywhere where we can find the editorial for this question???

Added by:  gawry 
Date:  20040617 
Time limit:  9s 
Source limit:  10000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS PERL6 VB.NET 