In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].

If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.

We are given a convex polygon of sides (where ) and its distinct diagonals not crossing one another inside the polygon. (The only point that two distinct diagonals may share is a vertex of the polygon.) Vertices of the polygon are numbered successively from to counterclockwise. All the diagonals divide into smaller convex polygons whose interiors do not intersect.

Four diagonals: 1-8, 8-3, 3-1 and 3-6 divide the polygon shown in the picture below into two quadrilaterals and three triangles.

Write a program that:

- reads a description of the polygon and its diagonals from the standard input,
- calculates the maximal number of sides of a polygon among the polygons created by the division of by the given diagonals,
- writes the result in the standard output.

In each line of the standard input two positive integers separated by a single space are written.

In the first line there is the number of vertices of the polygon and the number of diagonals .

In each of the following lines there is a description of one diagonal of the polygon in the form of a pair of positive integers. These integers are the numbers of the vertices of the polygon the diagonal joins. Just after the second number there is the end of the line.

The data in the standard input are written correctly and your program need not verify that.

In the standard output one should write one positive integer - the maximal number of sides of a convex polygon created by the division of the given polygon .

For the input data:

9 4 1 8 8 3 3 1 3 6

the correct result is:

4

*Task author: Krzysztof Diks.*