Фермер Джон недавно построил огромный амбар, состоящий из \(N \times N\)
решётки комнат, (\(2 \leq N \leq 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)\) (или, возможно,
в меньшее количество комнат, если она находится на границе решётки.
Определите максимальное количество комнат, в которые Беси
может включить свет.
ФОРМАТ ВВОДА (файл lightson.in):
Первая строка ввода содержит целые числа
\(N\) и
\(M\) ($1 \leq M \leq
20,000$).
Каждая из следующих \(M\) строк описывает один переключатель
четырьмя целыми числами \(x\), \(y\), \(a\), \(b\), означающими, что в
комнате \((x,y)\) можно переключить свет в комнате \((a,b)\). Несколько
переключателей могут находится в любой комнате и несколько переключателей
могут переключать свет в любой комнате.
ФОРМАТ ВЫВОДА (файл
lightson.out):
Одна строка, задающая максимальное количество комнат, в которых
Беси может включить свет.
ПРИМЕР ВЫВОДА
5
Здесь Беси может использовать переключатель в комнате \((1,1)\),
чтобы включить свет в комнатах \((1,2)\) и \((1,3)\). Затем она может
перейти в комнату \((1,3)\) и включить свет в комнате \((2,1)\), где
она может включить свет в комнате \((2,2)\). Переключатель в
комнате \((2,3)\) недоступен для неё, поскольку он находится в комнате,
где свет не включён. Поэтому Беси может посетить не более 5
комнат.
Авторы: Austin Bannister и Brian Dean