## USACO 2015 December Contest, Silver

## Problem 1. Switching on the Lights

Contest has ended.

**Log in to allow submissions in analysis mode**

Bessie starts in room $(1,1)$, the only room that is initially lit. In some rooms, she will find light switches that she can use to toggle the lights in other rooms; for example there might be a switch in room $(1,1)$ that toggles the lights in room $(1,2)$. Bessie can only travel through lit rooms, and she can only move from a room $(x,y)$ to its four adjacent neighbors $(x-1,y)$, $(x+1,y)$, $(x,y-1)$ and $(x,y+1)$ (or possibly fewer neighbors if this room is on the boundary of the grid).

Please determine the maximum number of rooms Bessie can illuminate.

#### INPUT FORMAT (file lightson.in):

The first line of input contains integers $N$ and $M$ ($1 \leq M \leq 20,000$).The next $M$ lines each describe a single light switch with four integers $x$, $y$, $a$, $b$, that a switch in room $(x,y)$ can be used to toggle the lights in room $(a,b)$. Multiple switches may exist in any room, and multiple switches may toggle the lights of any room.

#### OUTPUT FORMAT (file lightson.out):

A single line giving the maximum number of rooms Bessie can illuminate.#### SAMPLE INPUT:

3 6 1 1 1 2 2 1 2 2 1 1 1 3 2 3 3 1 1 3 1 2 1 3 2 1

#### SAMPLE OUTPUT:

5

Here, Bessie can use the switch in $(1,1)$ to turn on lights in $(1,2)$ and $(1,3)$. She can then walk to $(1,3)$ and turn on the lights in $(2,1)$, from which she can turn on the lights in $(2,2)$. The switch in $(2,3)$ is inaccessible to her, being in an unlit room. She can therefore illuminate at most 5 rooms.

Problem credits: Austin Bannister and Brian Dean