PERMCYC  Permutation Cycle Decomposition
Note: This is the companion problem to the languagerestricted Peculiar Permutivores. The contraints here are higher and the cluster is faster to allow better speed comparison, but otherwise it is the same problem.
Given some permutations, please print the unique cycle decomposition (up to ordering and rotations), excluding fixed points, and using the symbol "e" to denote the empty product.
Input
The first line contains an integer T (1 ≤ T ≤ 50000). Then follow 2T lines, representing T test cases. The first line of each test case contains an integer N (1 ≤ N ≤ 50), and the second line contains a permutation of [1..N] as a spaceseparated list of N integers.
Output
T lines containing the disjoint cycle decomposition of the corresponding permutation. Any correct answer is acceptable.
Example
Input:
5 3 1 2 3 3 2 1 3 4 2 1 4 3 9 3 8 9 4 1 7 6 2 5 9 3 8 9 4 1 7 6 2 5
Output:
e (1 2) (1 2)(3 4) (1 3 9 5)(2 8)(6 7) (2 8)(9 5 1 3)(7 6)
Additional Info
There are two randomly generated data sets, one with T=50000 and the other with T=5000. The average value of N in each data set is approximately 26.5.
Constraints are set to allow BF to pass without allowing easy 0.00s in C. My BF solution at the time of publication has 476 bytes and runs in 24.50s with 1.9M memory footprint. My C solution runs in 0.02s.
For assessing the correctness of program output, the custom judge works just the same as the standard "Ignores extra whitespaces" judge, except that it allows any valid cycle decomposition. In case you don't understand how the standard judge works, this means that e.g. "( 1 2)" and "(1 2) (3 4)" would be judged as wrong for the second and third example cases respectively, but printing ten spaces instead of the single space in "(1 2)" is perfectly fine.
hide comments
Francky:
20140330 11:21:21
333B in Python3, and I could get 3.33s ;)

Added by:  Mitch Schwartz 
Date:  20140329 
Time limit:  10s30s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  BFPRMCYC 