Page not loading? Try clicking here.
Placeholder

#8014

돗자리 깔기 1s 32MB

Problems

N * N 크기의 격자 바닥에 돗자리를 깔기 위해 나무가 없는 평평한 곳을 찾아야 한다.

나무는 총 T그루가 있으며, 나무는 한 격자 칸을 차지한다.

돗자리를 정사각형으로 가장 넓게 깔 때, 한 변의 길이를 구하라.


Input

첫 줄에 정수 N이 주어진다. (2\le N)

다음 줄에 양의 정수 T (T \le N^2)가 주어진다.

다음 T줄에 걸쳐 나무의 위치 행과 열이 공백을 구분으로 주어진다.


Output

가장 넓은 정사각형 돗자리의 한 변의 길이를 출력한다.


Subtask

# Score Condition
#110

N\le50, T=1

#230

N \le 50, T \le 10

#320

N \le 500 \, 000, T \le 10

#440

N \le 500 \, 000, T \le 100


Example #1

5
1
2 4
3

Example #2

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


Source

CCC 2022 Junior Division
You must sign in to write code.