Roger was unable to tilt Victor with rectangles, so now he's going to try with triangles instead!
Roger has given Victor a triangulation of a convex polygon with
Roger challenges Victor to draw as many line segments connecting points on the border of the polygon such that, for every color present on the polygon, that color only appears in exactly one region defined by the polygon and the line segments that Victor has drawn.
Compute the maximum number of segments that Victor can draw respecting the above constraint.
Constraints
The triangulation provided in the input will correspond to a valid triangulation of some polygon with
Subtask 1 [50%]
Subtask 2 [50%]
No additional constraints.
Input Specification
The first line will contain a single integer,
Each of the next
Output Specification
Print, on a single line, the maximum number of line segments Victor can draw.
Sample Input 1
5
1 2 3 2
4 5 1 1
3 1 4 2
Sample Output 1
1
Sample Input 2
6
1 4 2 1
2 4 5 2
6 2 5 3
3 6 5 1
Sample Output 2
0
Comments