Farmer John gần đây đã xây một chuồng khổng lồ gồm một lưới \(N\times N\) phòng (\(2\le N\le100\)), được đánh số từ \((1,1)\) đến \((N,N)\). Vì hơi sợ bóng tối, cô bò Bessie muốn bật đèn trong càng nhiều phòng càng tốt.

Bessie bắt đầu ở phòng \((1,1)\), căn phòng duy nhất có đèn sáng ban đầu. Trong một số phòng, cô sẽ tìm thấy các công tắc đèn có thể dùng để chuyển trạng thái đèn ở những phòng khác; chẳng hạn, trong phòng \((1,1)\) có thể có một công tắc chuyển trạng thái đèn ở phòng \((1,2)\). Bessie chỉ có thể đi qua các phòng có đèn sáng, và từ phòng \((x,y)\) cô chỉ có thể di chuyển đến bốn phòng kề \((x-1,y)\), \((x+1,y)\), \((x,y-1)\) và \((x,y+1)\) (hoặc có thể ít phòng kề hơn nếu phòng này nằm trên biên lưới).

Hãy xác định số phòng tối đa Bessie có thể thắp sáng.

Dữ liệu vào

Dòng đầu tiên chứa các số nguyên \(N\) và \(M\) (\(1\le M\le20\,000\)).

\(M\) dòng tiếp theo, mỗi dòng mô tả một công tắc đèn bằng bốn số nguyên \(x,y,a,b\), cho biết một công tắc trong phòng \((x,y)\) có thể được dùng để chuyển trạng thái đèn trong phòng \((a,b)\). Mỗi phòng có thể chứa nhiều công tắc và đèn của một phòng có thể được điều khiển bởi nhiều công tắc.

Dữ liệu ra

In một dòng chứa số phòng tối đa Bessie có thể thắp sáng.

Ví dụ

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

Nguồn

USACO 2015 December Contest, Silver - Switching on the Lights: https://usaco.org/index.php?page=viewproblem2&cpid=570

Tác giả: Austin Bannister và Brian Dean.