Shibuya Crossing

The scramble crossing in Shibuya, Tokyo carries so much foot traffic that people bump into each other. Model the crossing as a convex polygon. The $n$ people who are about to cross start at points on the lower half of the polygon's boundary. When the light changes, each person walks toward a distinct point on the upper half of the boundary. A path can wander like a strand of spaghetti and may even meet itself, but it never leaves the polygon, and two different paths never meet more than once.

Oskar watches the crossing from a cafe nearby. He has numbered the people $1$ through $n$ in counter-clockwise order, starting with the person standing farthest to the left. He does not know which route anyone takes, but he has worked out exactly which pairs of paths cross, and that information agrees with an arrangement that can really happen.

By Murphy's law, everyone who can bump into someone does, so two people whose paths cross always bump into each other. After all $n$ people have crossed, find the size of the largest group of people in which every two members have bumped into each other.

A drawing of one situation that can produce the first example.

The first line contains the number of people at the crossing $n$ ($1 \le n \le 800$) and the number of crossing path pairs $m$ ($0 \le m \le 10000$).

Each of the next $m$ lines contains two integers $a$ and $b$ ($1 \le a < b \le n$), meaning that the path of person $a$ crosses the path of person $b$. No pair is given twice.

Print one integer, the size of the largest group of people in which every two members have bumped into each other.