페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8014

돗자리 깔기 1s 32MB

문제

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

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

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


입력

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

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

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


출력

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


부분문제

번호 점수 조건
#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


예제 #1

5
1
2 4
3

예제 #2

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


출처

CCC 2022 Junior Division
로그인해야 코드를 작성할 수 있어요.