0349 - 暗いのは苦手

時間制限 1 秒 / メモリ制限 256 MB / 得点 4 / Writer ei1333 / x 2 / 統計 /

TLE
1sec
MLE
256MB
得点
4

問題

忍の住む大宮家では, 縦 N × 横 N のグリッド状に部屋が並んでいる. 左下の部屋を(1, 1), 右上の部屋を(N, N) で表す. 一部の部屋には, 他の部屋の電灯をつけるためのスイッチが設置されていて, スイッチを押すと, 電灯がつく. また, 同じ部屋に複数個のスイッチが存在することもある.

各部屋には、アリスが 1 人いる. 日が落ちて暗くなってきたので, それぞれのアリスは, 電灯をつけようと思った. しかし, 背が小さくてスイッチに届かなかったので, 忍に助けを求めた.

忍は今 (1, 1) の部屋にいる. 最初はその部屋のみ点灯している. 忍は, 今いる部屋のスイッチを押しつつ, 隣接している明るい部屋のみを通って移動することができる. 一度訪れた部屋をまた訪れることもできる. 部屋 (x, y) に隣接している部屋は, (x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1) の 4 つである(但し, N × N の範囲外には移動できない).

照らすことができる部屋の数の最大値を求めよ. 部屋 (1, 1) はこれに含むので注意すること.

入力

標準入力から以下の入力を読み込め． 

N M
A1 B1 X1 Y1
A2 B2 X2 Y2
:
AM BM XM YM
  • 1 行目には整数 N, M が半角空白区切りで書かれている. N はグリッドの大きさ, M はスイッチの個数を表す．
  • 続く M 行には，スイッチの情報が書かれている. このうち i 行目には Ai, Bi, Xi, Yi が半角空白区切りで書かれている. これはスイッチが部屋 (Ai, Bi) に設置されていて, このスイッチを押すと 部屋(Xi, Yi) の電灯がつくことを表す.

制限

すべての入力データは以下の制約を満たす.

  • 2 ≤ N ≤ 100
  • 1 ≤ M ≤ 20 000
  • 1 ≤ Ai, Bi, Xi, Yi ≤ N

出力

標準出力に，照らすことのできる部屋の数の最大値を表す整数を出力せよ．

入出力例

入力例

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

忍は最初 (1, 1) にいて, (1, 2), (1, 3) を照らすことができる. 続いて (1, 3) に移動して, (2, 1) を照らすことができる. 続いて (2, 1) に移動して, (2, 2) を照らすことができる. (2, 3) にあるスイッチは, 明るい部屋のみを通って (2, 3) に移動できないので, 押すことができない.

よって, 照らすことができた部屋は(1, 1), (1, 2), (1, 3), (2, 1), (2, 2) の 5 部屋なので, 5 を出力する.