W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
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:
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.