Polygon

Time limit1sMemory limit128 MB

Summary

Given a convex polygon and a set of non-crossing diagonals, report the largest number of sides among the pieces the diagonals divide it into.

Level: Medium4 of 10
Topics: Graph, DFS, Implementation, Geometry
Solved: No attempts yet

Problem

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.

Input

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

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

Examples3

Example 1
Input
```
9 4
1 8
8 3
3 1
3 6
```
Expected output
```
4
```
Example 2
Input
```
4 1
1 3
```
Expected output
```
3
```
Example 3
Input
```
6 1
1 4
```
Expected output
```
4
```