Матриця#484

Матриця

3 секунди
256 мегабайтів
Складна

У вас є квадратна бінарна матриця розміром n \times n. Спочатку всі її елементи дорівнюють нулю.

Вам дано оновлень. Кожне оновлення має наступний формат:

Координати та індексуються з .

Після початкової матриці, що складається лише з нулів (перед обробкою будь-яких оновлень), і після кожного з оновлень, вам потрібно знайти довжину сторони найбільшої квадратної підматриці, що складається лише з .

Вхідні дані

Перший рядок містить два цілі числа та (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

Loading
Loading

Примітка

У прикладі матриця після кожного запиту виглядає так:

  • Після 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

    Тепер найбільший квадрат з усіх одиниць має довжину сторони (верхній лівий кут у ).

Оцінювання

У кожному блоці тести оцінюються незалежно.

  1. ( балів): n \le 10;

  2. ( балів): n \le 100;

  3. ( балів): без додаткових обмежень.