다각형

볼록한 $n$각형 $P$가 주어진다 ($3 < n \le 5000$). 또한 다각형 내부에서 서로 교차하지 않는, 서로 다른 대각선 $k$개가 함께 주어진다. (서로 다른 두 대각선이 공유할 수 있는 점은 다각형의 꼭짓점뿐이다.) 다각형의 꼭짓점은 반시계 방향으로 $1$번부터 $n$번까지 차례로 번호가 매겨져 있다. 이 대각선들은 $P$를 내부가 서로 겹치지 않는 더 작은 볼록 다각형들로 나눈다.

아래 그림에서 네 대각선 1-8, 8-3, 3-1, 3-6은 다각형 $P$를 두 개의 사각형과 세 개의 삼각형으로 나눈다.

다각형 $P$와 그 대각선들의 정보를 표준 입력에서 읽어, 이 대각선들이 $P$를 나누어 만든 다각형들 중에서 변의 개수가 가장 많은 다각형의 변의 개수를 계산하여 표준 출력에 출력하는 프로그램을 작성하시오.

입력의 각 줄에는 공백 하나로 구분된 두 양의 정수가 적혀 있다.

첫째 줄에는 다각형의 꼭짓점 개수 $n$과 대각선 개수 $k$가 주어진다.

이어지는 $k$개의 줄에는 각 줄마다 대각선 하나의 정보가 두 양의 정수 쌍으로 주어진다. 이 두 정수는 그 대각선이 잇는 두 꼭짓점의 번호이다.

입력은 항상 올바른 형식으로 주어지므로 프로그램이 이를 따로 검증할 필요는 없다.

주어진 대각선들로 다각형 $P$를 나누어 만든 볼록 다각형들 중에서 변의 개수가 가장 많은 것의 변의 개수를, 하나의 양의 정수로 표준 출력에 출력한다.