У вас є квадратна бінарна матриця розміром n \times n. Спочатку всі її елементи дорівнюють нулю.
Вам дано оновлень. Кожне оновлення має наступний формат:
x y — встановити a_{x,y} := 1. Якщо ця клітинка вже була , вона залишиться .
Координати та індексуються з .
Після початкової матриці, що складається лише з нулів (перед обробкою будь-яких оновлень), і після кожного з оновлень, вам потрібно знайти довжину сторони найбільшої квадратної підматриці, що складається лише з .
Перший рядок містить два цілі числа та (1 \le n \le 500, 1 \le q \le 250 000) — розмір матриці та кількість оновлень.
Кожен з наступних рядків містить два цілі числа та (1 \le x, y \le n) і описує оновлення x y — встановити a_{x,y} := 1.
Виведіть q+1 рядків.
У першому рядку виведіть довжину сторони найбільшої квадратної підматриці з усіх одиниць у початковій матриці (яка складається лише з нулів).
Потім, після кожного оновлення, виведіть довжину сторони найбільшої квадратної підматриці з усіх одиниць у поточній матриці.
Приклад 1
У прикладі матриця після кожного запиту виглядає так:
Після 1 1:
1 | 0 | 0 |
0 | 0 | 0 |
0 | 0 | 0 |
Після 1 2:
1 | 1 | 0 |
0 | 0 | 0 |
0 | 0 | 0 |
Найбільший квадрат з усіх одиниць має довжину сторони .
Після 2 2:
1 | 1 | 0 |
0 | 1 | 0 |
0 | 0 | 0 |
Після 2 1:
1 | 1 | 0 |
1 | 1 | 0 |
0 | 0 | 0 |
Тепер найбільший квадрат з усіх одиниць має довжину сторони (верхній лівий кут у ).
У кожному блоці тести оцінюються незалежно.
( балів): n \le 10;
( балів): n \le 100;
( балів): без додаткових обмежень.