멀티버스 Ⅰ

면접 대비

시간 제한1초메모리 제한512 MB

요약

두 우주는 크기 배열이 만드는 순서와 동률 구조가 같을 때 같다고 한다. 각 배열을 순위 패턴으로 바꾸고 같은 쌍의 수를 센다.

난이도: 보통10점 중 5점
유형: 정렬, 해시맵, 배열, 구현
정답자: 아직 제출이 없습니다

문제

$M$ 개의 우주가 있고, 각 우주에는 1부터 $N$ 까지 번호가 매겨진 행성이 $N$ 개 있다. 행성의 크기를 알고 있을 때, 균등한 우주의 쌍이 몇 개인지 구하려고 한다. 구성이 같은데 순서만 다른 우주의 쌍은 한 번만 센다.

두 우주 $A$ 와 $B$ 가 있고, 우주 $A$ 에 있는 행성의 크기는 $A_1, A_2, \dots, A_N$ , 우주 $B$ 에 있는 행성의 크기는 $B_1, B_2, \dots, B_N$ 이라고 하자. 두 우주의 행성 크기가 모든 $1 \le i, j \le N$ 에 대해서 아래 조건을 만족하면 두 우주를 균등하다고 한다.

$A_i < A_j \rightarrow B_i < B_j$
$A_i = A_j \rightarrow B_i = B_j$
$A_i > A_j \rightarrow B_i > B_j$

입력

첫째 줄에 우주의 개수 $M$ 과 각 우주에 있는 행성의 개수 $N$ 이 주어진다. 둘째 줄부터 $M$ 개의 줄에 공백으로 구분된 행성의 크기가 한 줄에 하나씩 1번 우주부터 차례대로 주어진다.

출력

첫째 줄에 균등한 우주의 쌍의 개수를 출력한다.

제한

$2 \le M \le 10$
$3 \le N \le 100$
$1 \le$ 행성의 크기 $\le 10{,}000$

예제3

예제 1
입력
```
2 3
1 3 2
12 50 31
```
예상 출력
```
1
```
예제 2
입력
```
2 3
1 3 2
12 50 10
```
예상 출력
```
0
```

예제 3

입력

예상 출력