## Mock CCO '18 Contest 2 Problem 5 - Victor's Triangles

View as PDF

Points: 20 (partial)
Time limit: 0.6s
Memory limit: 64M

Problem type

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 sides. The polygon has already been triangulated by Roger, and every triangle has been filled in with some color. The vertices are randomly labeled with distinct positive integers from to .

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 sides.

##### Subtask 2 [50%]

No additional constraints.

#### Input Specification

The first line will contain a single integer, .

Each of the next lines will contain four space-separated integers, , , , and , indicating that the triangle with vertices , , , is colored with color .

#### 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

There are no comments at the moment.