P6559 [SBCOI2020] Town

In a place unknown to people, there is a small town. A town that nobody can even name. The seasons once again enter winter, the season that belongs to snow. Beneath that snow, buried away, are dreams and legends that belong only to this town. ...... “It’s winter again!” “Yeah! Everything around has turned into a vast whiteness...” “Sigh, if only days like this could last forever.” “Ah, forever...” “But what in this world can truly be forever? Like the melting snow, blending into the earth in pure white, before people even have time to savor it—so helpless, yet so pure......” In the snow, the lights between rows of houses give off a warm glow.  “Will we still be able to watch the snow together in the future?” “Of course, always......”

The town can be viewed as an $n \times n$ grid, where $k$ cells are houses. There are also lamps in the town. Between every two adjacent cells, there is a lamp. If two houses are **adjacent**, then the lamp between these two houses will be lit. Please find how many lamps are lit in total in this town. Note: in this problem, “adjacent” means sharing a common edge.

The first line contains two integers $n, k$, representing the side length of the grid and the number of houses. The next $k$ lines each contain two integers $x, y$, representing the coordinates of a house.

One line with one integer, representing the answer.

#### Sample Explanation  As shown in the figure, the shaded cells are houses, and the red edges are lamps. #### Constraints For $30\%$ of the testdata, $1 \leq n, k \leq 100$. For $80\%$ of the testdata, $1 \leq n, k \leq 5000$. For $100\%$ of the testdata, $1 \le n, k \le 10^5$. Translated by ChatGPT 5