题目描述

Farm John 最近新建了一批巨大的牛棚。这些牛棚构成了一个 $N \times N$ 的矩形网络 $(1 < N < 100)$。

然而 Bessie 十分怕黑，他想计算可以把多少个牛棚的灯打开。

有 $N \times N$ 个房间，组成了一张 $N \times N$ 的网格图，Bessie 一开始位于左上角 $(1,1)$，并且只能上下左右行走。

一开始，只有 $(1,1)$ 这个房间的灯是亮着的，Bessie 只能在亮着灯的房间里活动。

有另外 $M$ 条信息，每条信息包含四个数 $a,b,c,d$，表示房间 $(a,b)$ 里有房间 $(c,d)$ 的灯的开关。

请计算出最多有多少个房间的灯可以被打开。

输入文件 light.in

第一行输入两个整数 $N,M(1 < N < 100,1 < M < 2 \times 10^5)$。

第 $2 \sim M + 1$ 行，每行输入四个整数 $(x_1,y_1),(x_2,y_2)$，代表房间的坐标 $(x_1,y_1)$ 可以点亮房间的坐标 $(x_2,y_2)$。

输出文件 light.out

一个数，最多可以点亮的房间数。

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

Bessie 可以使用 $(1,1)$ 的开关打开 $(1,2),(1,3)$ 的灯，然后走到 $(1,3)$ 并打开 $(2,1)$ 的灯，走到 $(2,1)$ 并打开 $(2,2)$ 的灯。$(2,3)$ 的开关无法到达。因此可以点亮 $5$ 个房间。