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 say that two triangles intersect if their interiors have at least one common point. A polygon is called convex if every segment connecting any two of its points is contained in this polygon. A triangle whose vertices are also vertices of a convex polygon is called an elementary triangle of this polygon. A triangulation of a convex polygon is a set of elementary triangles of this polygon, such that no two triangles from the set intersect and a union of all triangles covers the polygon.

We are given a polygon and its triangulation. What is the maximal number of triangles in this triangulation that can be intersected by an elementary triangle of this polygon?

Consider the following triangulation:

The elementary triangle intersects all the triangles in this triangulation.

Write a program that:

- reads the number of vertices of a polygon and its triangulation from the standard input;
- computes the maximal number of triangles intersected by an elementary triangle of the given polygon;
- writes the result to the standard output.

In the first line of the standard input there is a number , , which equals the number of vertices of the polygon. The vertices of the polygon are numbered from to clockwise.

The following lines describe the triangles in the triangulation. There are three integers separated by single spaces in the -st line, where . These are the numbers of the vertices of the -th triangle in the triangulation.

In the first and only line of the standard output there should be exactly one integer — the maximal number of triangles in the triangulation, that can be intersected by a single elementary triangle of the input polygon.

For the input data:

6 0 1 2 2 4 3 4 2 0 0 5 4

the correct result is:

4

*Task author: Krzysztof Diks.*