Polygon

You are given a convex polygon $P$ with $n$ sides, where $3 < n \le 5000$, together with $k$ distinct diagonals that do not cross one another inside the polygon. (The only point that two distinct diagonals may share is a vertex of the polygon.) The vertices of the polygon are numbered from $1$ to $n$ counterclockwise. These diagonals split $P$ into smaller convex polygons whose interiors do not overlap.

In the figure below, the four diagonals 1-8, 8-3, 3-1, and 3-6 split the polygon $P$ into two quadrilaterals and three triangles.

Write a program that reads the description of the polygon $P$ and its diagonals from standard input, finds the largest number of sides among the polygons produced by dividing $P$, and writes that number to standard output.

Each line of the input contains two positive integers separated by a single space.

The first line contains the number of vertices $n$ and the number of diagonals $k$.

Each of the next $k$ lines describes one diagonal as a pair of positive integers: the numbers of the two vertices that the diagonal joins.

The input is always well formed, so your program does not need to validate it.

Output a single positive integer: the largest number of sides among the convex polygons produced by dividing $P$ with the given diagonals.