宁波市第 25 届中小学生计算机程序设计竞赛复赛试题（初中组）第 6 页 共 7 页
m列的n*m个互相之间交换了一下次序）。A教官能力尚浅，不能用大招把方阵瞬间复原。他每次操作只可以交换任意两个同学的位置。
A教官是第一次执教，他不想在上级领导面前出丑。他想让你帮他算出他至少需要多少次操作才能把方阵复原。
【输入】
输入文件lineup.in的第一行只有二个整数n和m(互相之间以一个空格分隔)。 接下来n行，每行有m对整数(a,b)。第i行的第j对整数(a,b)表示第i行的第j个同学应该排在第a行第b列。
如样例输入所示，每对整数以一对括号括起来，相邻二对整数之间有一个空格分隔，同一对的二个整数之间有一个逗号分隔。
【输出】
输出文件lineup.out中仅有一行，该行只有一个整数，代表A教官想要复原方阵最少需要的操作次数。
【样例输入】
3 3
(1,1) (2,2) (1,3) (1,2) (2,1) (2,3) (3,3) (3,2) (3,1)
【样例输出】
3
【样例说明】
被打乱的方阵为：
(1,1) (1,2) (3,3) (2,2) (2,1) (3,2) (1,3) (2,3) (3,1) 第一次操作交换第1行第2列和第2行第2列后得：
(1,1) (1,2) (2,1) (2,2) (1,3) (2,3)
? 宁波市计算机学会，2010
宁波市第 25 届中小学生计算机程序设计竞赛复赛试题（初中组）第 7 页 共 7 页 (3,3) (3,2) (3,1) 第二次操作交换第1行第2列和第2行第1列后得：
(1,1) (2,1) (3,3) (1,2) (2,2) (3,2) (1,3) (2,3) (3,1) 第三次操作交换第3行第1列和第3行第3列后得：
(1,1) (2,1) (3,1) 方阵被复原。一共进行了三次操作。
(1,2) (2,2) (3,2) (1,3) (2,3) (3,3) 【数据规模】
30%的数据中，1≤n*m≤9；
65%的数据中，1≤n*m≤20000； 1≤n≤210，1≤m≤210； 90%的数据中，1≤n≤1000，1≤m≤1000； 100%的数据中，1≤n*m≤1000000。
? 宁波市计算机学会，2010