Take any initial segment of the alphabet (like abcdefgh), rearrange the letters any way you want (say, hedagcbf), and you have a permutation of the original sequence. A permutation is just a rearrangement of the original sequence (though not all letters need be rearranged). A permutation can also be used to encode a message by replacing each letter in the original sequence by the corresponding letter in the rearranged sequence.
Original letter: abcdefgh Replacement: hedagcbf
This means to replace a by h, b by e, and so on. For example,
Original message: He begged a deaf cad. Encoded message: fh egbbga h aghc dha.
Another way to represent a permutation is as a collection of cycles. For example, hedagcbf can be represented as (a,h,f,c,d)(b,e,g) because it maps a to h, h to f, f to c, c to d, and d back to a, and it maps b to e, e to g, and g back to b. Your job is to write a program that can represent a permutation in this form.
The input consists of one or more lines, each of which contains a permutation of some initial segment of the English alphabet. For each permutation, output its cycles exactly as shown in the examples. Note that the first letters of the cycles are in alphabetical order. Omit cycles that consist of only a single letter.
Input must be read from the file "prob39.in", and output must be
written to the file "prob39.out". All output to the screen will be
ignored.
<BOF> cafdegb ab hcdbjeigaf dabc <EOF>
(a,c,f,g,b) (a,h,g,i)(b,c,d)(e,j,f) (a,d,c,b)