농부 존은 그의 정사각형 농장에 정사각형 우리를 가장 크게 두고자 하는데 농장에 있는 나무를 베는 것을 극도로 싫어한다. 그의 농장은 N*N 형태의 셀로 나누어져 있고 나무를 포함하는 셀의 리스트가 주어진다.

우리가 해야 할 일은 나무를 베지 않고 가장 큰 정사각형 농장 부지를 결정하는 것이다. 단, 우리는 가로 세로 축에 평행하여야 한다.

보기

  1 2 3 4 5 6 7 8
1 . . . . . . . .
2 . # . . . # . .
3 . . . . . . . .
4 . . . . . . . .
5 . . . . . . . .
6 . . # . . . . .
7 . . . . . . . .
8 . . . . . . . .

입력

• 첫 번째 라인은 2 개의 수가 N , T 가 입력으로 주어진다. N 은 농장의 크기이고 , T 는 나무의 수이다. 1 <= N <= 1000 , 1 <= T <= 10,000 이다.
• 다음 T 라인은 나무가 있는 셀의 위치로 행,열로 주어진다.

출력

입출력 예

입력

8 3
2 2
2 6
6 3

출력

5

출처:usaco