题目描述
农民约翰最近建造了一个巨大的谷仓,由N×N个房间组成(2≤N≤100),编号从(1,1)到(N,N)。由于有点怕黑,奶牛贝西想在旧能多的 房间里开灯。
贝西从房间(1,1)开始,这是唯一一个最初亮起的房间。在一些房间里,她会找到可以用来切换其他房间灯光的开关;例如,房间(1,1)中可能有一个开关,用于切换房间(1,2)中的灯光。贝西只能穿过有灯光的房间,她只能从一个房间(x,y)移动到四个相邻的房间(x−1,y)、(x+1,y)、(x,y−1) 和(x,y+1)(如果该房间位于网格边界上,则可能更少的邻居)。
请确定贝西可以照亮的最大房间数。
输入格式
第一行输入包含整数N和M(1≤M≤20,000)。
接下来的M行分别描述了一个具有四个整数x,y,a,b的单灯开关,房间(x,y)中的开关可用于切换房间(a,b)中的灯。任何房间中都可能存在多个开关,多个开关可以切换任何房间的灯光。
输出格式
一条线给出了 Bessie可以照亮的最大房间数。
样例
输入样例
输出样例
提示
在这里,贝西可以使用(1,1)中的开关打开(1,2)和(1,3)中的灯。然后她可以走到(1,3)并打开(2,1)中的灯,从中她可以打开(2,2)中的灯。(2,3)中的开关在一个没有照明的房间里,她无法接近。因此,她最多可以照亮5个房间。