Apagones

Points: 100 (partial)

Time limit: 1.0s

Memory limit: 256M

Author:

Problem type

La tía Polly ha construido recientemente un enorme complejo formado por una cuadrícula $N$ ~N~ x $N$ ~N~ de habitaciones $(2 \leq N \leq 100)$ ~(2 \leq N \leq 100)~, numeradas desde $(1,1)$ ~(1,1)~ hasta $(N,N)$ ~(N,N)~. Tommy, que tiene cierto miedo a la oscuridad, quiere encender las luces del mayor número posible de habitaciones.

Tommy empieza en la habitación $(1,1)$ ~(1,1)~ la única habitación que está iluminada inicialmente. En algunas habitaciones encontrará interruptores que puede utilizar para encender las luces de otras habitaciones; por ejemplo, puede haber un interruptor en la habitación $(1,1)$ ~(1,1)~ que encienda las luces de la habitación $(1,2)$ ~(1,2)~. Tommy sólo puede viajar a través de habitaciones iluminadas, y sólo puede moverse de una habitación $(x,y)$ ~(x,y)~ a sus cuatro vecinas adyacentes $(x-1,y)$ ~(x-1,y)~, $(x+1,y)$ ~(x+1,y)~, $(x,y-1)$ ~(x,y-1)~ y $(x,y+1)$ ~(x,y+1)~ (o posiblemente menos vecinas si esta habitación está en el límite de la cuadrícula).

Determine el número máximo de habitaciones que Tommy puede iluminar.

Entrada

La primera línea de entrada contiene los enteros $N$ ~N~ y $M$ ~M~ $(1 \leq M \leq 20 000)$ ~(1 \leq M \leq 20 000)~.

Las siguientes $M$ ~M~ líneas describen cada una un único interruptor de luz con cuatro enteros $x, y, a, b$ ~x, y, a, b~, un interruptor en la habitación $(x,y)$ ~(x,y)~ puede usarse para encender las luces en la habitación $(a,b)$ ~(a,b)~. Pueden existir múltiples interruptores en cualquier habitación, y múltiples interruptores pueden encender las luces de una misma habitación.

Salida

Una sola línea que indica el número máximo de habitaciones que Tommy puede iluminar.

Ejemplos

Entrada 1

Salida 1

Explicación Aquí, Tommy puede utilizar el interruptor de $(1,1)$ ~(1,1)~ para encender las luces de $(1,2)$ ~(1,2)~ y $(1,3)$ ~(1,3)~. Luego puede caminar a $(1,2)$ ~(1,2)~ y luego hasta $(1,3)$ ~(1,3)~ y encender las luces de $(2,1)$ ~(2,1)~,puede regresar hasta $(1,1)$ ~(1,1)~ e ir hacia $(2,1)$ ~(2,1)~ desde donde puede encender las luces de $(2,2)$ ~(2,2)~. El interruptor de $(2,3)$ ~(2,3)~ es inaccesible para él, ya que se encuentra en una habitación sin luz. Por tanto, puede iluminar como máximo 5 habitaciones: $(1,1), (1,2), (1,3), (2,1), (2,2)$ ~(1,1), (1,2), (1,3), (2,1), (2,2)~

CC BY 4.0

Comments

There are no comments at the moment.