#ABC303B. 不开心的摄影

不开心的摄影

题目描述

\hspace{15pt}有 nn 个人,编号为 1∼n1\sim n,一共拍摄了 mm 张合影。每张合影中,所有人站成一排,每个人恰好出现一次。第 ii 张照片从左到右的人员编号为 {ai,1,ai,2,…,ai,n}\{a_{i,1},a_{i,2},\dots,a_{i,n}\}。

\hspace{15pt}若两个人在所有照片中都没有相邻站立过,则称他们为一对不开心的人。照片中只有位置相差 11 才算相邻,队首与队尾不相邻。交换两个人的顺序视为同一对,每对由两名不同的人组成。请计算不开心的人的对数。

输入格式

\hspace{15pt}第一行输入两个整数 n,m(2≦n≦50; 1≦m≦50)n,m\left(2\leqq n\leqq50;\ 1\leqq m\leqq50\right),分别代表人数与照片数量。

\hspace{15pt}此后 mm 行,第 ii 行输入 nn 个整数 $a_{i,1},a_{i,2},\dots,a_{i,n}\left(1\leqq a_{i,j}\leqq n\right)$。保证每一行都是 1∼n1\sim n 的一个排列,即每个编号恰好出现一次。

输出格式

\hspace{15pt}输出一个整数,代表不开心的人的对数。

测试样例

4 2
1 2 3 4
4 3 1 2
2

样例 1 解释

\hspace{15pt}两张照片中曾相邻的无序对为 {1,2},{2,3},{3,4},{1,3}\{1,2\},\{2,3\},\{3,4\},\{1,3\}。总共有 66 对不同的人,因此还剩 {1,4}\{1,4\} 与 {2,4}\{2,4\} 两对,答案为 22。

3 3
1 2 3
3 1 2
1 2 3
0
10 10
4 10 7 2 8 3 9 1 6 5
3 6 2 9 1 8 10 7 4 5
9 3 4 5 7 10 1 8 2 6
7 3 1 8 4 9 5 6 2 10
5 2 1 4 10 7 9 8 3 6
5 8 1 6 9 3 2 4 7 10
8 10 3 4 5 7 2 9 6 1
3 10 2 7 8 5 1 4 9 6
10 6 1 5 4 2 3 8 9 7
4 5 9 1 8 2 7 6 3 10
6