Un dels llocs més emblemàtics de Sabadell és la Plaça del Pí-Pí. Aquesta plaça amb aquest nom tan suggerent es deu a que hi ha dos pins a la plaça, i tothom li deia així, tot i que realment no tenia nom.

L'ajuntament de Sabadell, seguint la tradició, vol crear la plaça del No-Pí, una plaça sense cap pí.

Donat un mapa, amb posicions que tenen pins, i posicions que no tenen pins, quina es la plaça quadrada més gran que pots fer que no contingui cap pí?

Entrada

La primera línea és un enter $N$ a on $500000 \geq N \geq 2$ , que representa el tamany del terreny a on es vol fer la plaça La segona línea és un enter $T \leq 100$ , que representa el nombre de pins Després vindràn $T$ línies, a on cada una tindrà dos enters representant la fila i la columna de cada pi, a on les files estan distribuides a on la de dalt de tot és $1$ i la de baix de tot és $N$, i les columnes estan distribuides de manera que la de l'esquerra de tot és $1$ i la de la dreta de tot és $N$

Sortida

La mida màxim que pot tenir la plaça del No-Pi, que serà quadrada. No cal que indiquis la ubicació.

Exemple d'Entrada

5 
1 
2 4

Exemple de Sortida

3

Explicació de l'exemple

Exemple d'Entrada

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

Exemple de Sortida

7

Explicació de l'exemple