시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB201887747.239%

문제

영선이는 N행 M열로 이루어진 표를 가지고 있다. 행은 위에서부터 아래로 0번부터 N-1번까지, 열은 왼쪽에서 오른쪽으로 0번부터 M-1번까지 번호가 매겨져 있다.

표의 각 칸에는 양의 정수가 하나 쓰여 있으며, 표에 포함되어 있는 수는 1부터 N*M까지로 이루어진 순열을 이룬다. 즉, 각각의 수는 표에 한 번씩 등장한다.

표가 주어졌을 때, 행 우선 순서를 이용해 만든 수열을 값 수열이라고 한다.

영선이는 두 가지 방법을 표를 수정할 수 있는데, 임의의 두 행을 서로 위치를 바꾸거나, 두 열의 위치를 바꾸는 것이다.

표가 주어졌을 때, 값 수열을 오름차순으로 만들 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N, M ≤ 50)

둘째 줄부터 N개의 줄에 표의 내용이 주어진다.

출력

입력으로 주어진 표의 값 수열을 오름차순으로 만들 수 있으면 1을, 없으면 0을 출력한다.

예제 입력 1

2 2
1 2
3 4

예제 출력 1

1

예제 입력 2

2 2
3 4
1 2

예제 출력 2

1

예제 입력 3

2 2
4 3
1 2

예제 출력 3

0

예제 입력 4

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

예제 출력 4

1

예제 입력 5

3 5
10 6 8 9 7
5 1 3 4 2
15 11 13 14 12

예제 출력 5

1

출처

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: jh05013