Background

Source: usaco-2015-dec.

Farmer John recently built a large set of barns arranged in an $N \times N$ rectangular grid ($1 < N \leq 100$).

However, Bessie is afraid of the dark and wants to know how many barns’ lights she can turn on.

Problem Description

There are $N \times N$ rooms forming an $N \times N$ grid. Bessie starts at the top-left corner $(1, 1)$ and can move only up, down, left, and right.

Initially, only the room $(1, 1)$ is lit, and Bessie may only move through rooms whose lights are on.

There are $M$ additional pieces of information. Each describes that a switch in room $(a, b)$ controls the light in room $(c, d)$.

Compute the maximum number of rooms whose lights can be turned on.

Input Format

The first line contains two integers $N, M$ ($1 < N \leq 100$, $1 < M < 2 \times 10^5$).

Lines $2$ to $M+1$ each contain four integers $(x_1, y_1), (x_2, y_2)$, meaning the switch in room $(x_1, y_1)$ can turn on the light in room $(x_2, y_2)$.

Output Format

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

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

5

Hint

Bessie can use the switch at $(1, 1)$ to turn on the lights in $(1, 2)$ and $(1, 3)$, then move to $(1, 3)$ and turn on $(2, 1)$, move to $(2, 1)$ and turn on $(2, 2)$. The switch at $(2, 3)$ is unreachable. Therefore, $5$ rooms can be lit.

Translated by ChatGPT 5