Bessie’s Light Switching Challenge

Bessie is exploring an $N \times N$ grid of rooms. She starts from the top-left room at position $ (1,1) $, and she can only move in the four cardinal directions (up, down, left, right). Initially, only room $(1,1)$ is lit, and Bessie may only move through lit rooms.

There are $M$ pieces of information. Each piece contains four integers $a,b,c,d$ and denotes that in room $(a,b)$ there is a switch that can turn on the light in room $(c,d)$ (if it is not already lit).

Your task is to determine the maximum number of rooms that can be lit by Bessie.

Note: Once a room is lit, it remains lit. However, Bessie can only navigate through lit rooms that are reachable from $(1,1)$ by a sequence of adjacent moves.

inputFormat

The first line of input contains two integers $N$ and $M$ indicating the size of the grid and the number of switches, respectively.

The next $M$ lines each contain four integers $a$, $b$, $c$, $d$ indicating that in room $(a,b)$ there is a switch to toggle the light in room $(c,d)$.

outputFormat

Output a single integer representing the maximum number of rooms that can be lit.

sample

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

7