TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P3873
  • Problem
  • P3873平方根
    Limits : Time Limit : - MS   Memory Limit : 165536 KB
    Judgment Tips : 1s
    Description

    小 J 说自己的记忆力无人匹敌,小 Y 不爽,他们找你当裁判。初始时小 J 面前有
    一排 n 个箱子,从左到右第 i 个箱子里有一个编号为 i 的球。小 Y 说出了一串诸如 SWAP 
    x y 的指令,每说一条就把第 x 个箱子与第 y 个箱子交换位置。之后,箱子不归位,小
    J 按顺序把小 Y 执行过的步骤重复了一遍。结束后,打开箱子,你看到的是每个箱子
    里球的编号。由于命令太多了,你并不记得具体的指令是什么,但有时无论指令是什
    么,执行完全相同的两遍后都不可能是小 J 操作后的结果。你需要判断小 J 重复的步
    骤是否可能与小 Y 完全相同。 

    Input Format

    第一行一个整数 T,表示接下来有 T 组测试数据 
    每组测试数据第一行一个整数 n 
    接下来一行 n 个整数,为 1~n 的一个排列,表示最后从左到右箱子里球的编号 

    Output Format

    每组测试数据一行 
    若小 J 一定出现过问题,输出 Impossible,否则输出 Maybe 

    Sample Input

    2
    4
    3 4 1 2
    4
    2 3 4 1

    Sample Output

    Maybe
    Impossible 

    Hint

    第一组数据:一个可能的步骤是:SWAP 1 2; SWAP 2 3; SWAP 3 4 
    第二组数据:任何一组步骤执行两遍后都不可能使球的编号为 2 3 4 1 

    40%的数据保证 n ≤ 10 
    100%的数据保证 n ≤ 1000;T ≤ 10 


    Source  不告诉你