Triangulation

Time limit3sMemory limit128 MB

Summary

Given a triangulated colored convex polygon, find the maximum number of triangulation diagonals that can be cut without separating same-colored triangles.

Level: Medium6 of 10
Topics: Union-find, Graph, DFS
Solved: No attempts yet

Problem

In computational geometry, a triangulation is a set of triangles satisfying the following two conditions:

The three vertices of every triangle are vertices of the given polygon.
No two triangles overlap in their interiors, and the union of all triangles equals the whole polygon.

A convex polygon is a polygon with at least three sides in which every interior angle is less than 180 degrees. A straight line that splits a convex polygon into two convex polygons is called a cut line of that polygon.

You are given a triangulated convex polygon in which the interior of each triangle is painted with a color $C_i$ . You want to draw as many cut lines as possible so that no two points of the same color are ever separated into different pieces. What is the maximum number of cut lines you can draw?

If a cut line passed through the interior of a triangle it would split two same-colored points of that triangle, so every cut line must coincide with exactly one of the internal diagonals of the triangulation.

Input

The first line contains the number of polygon vertices $n$ . ( $3 \le n \le 100{,}000$ )

Each of the next $n-2$ lines describes one triangle with four integers $a\ b\ c\ d$ : the triangle has polygon vertices $a$ , $b$ , $c$ as its three corners, and its interior is painted with color $d$ . ( $1 \le a, b, c, d \le n$ )

The given input is always a valid triangulation satisfying the conditions above.

Output

Print, on a single line, the maximum number of cut lines that can be drawn.

Examples3

Example 1
Input
```
5
1 2 3 2
4 5 1 1
3 1 4 2
```
Expected output
```
1
```
Example 2
Input
```
6
1 4 2 1
2 4 5 2
6 2 5 3
3 6 5 1
```
Expected output
```
0
```
Example 3
Input
```
4
1 2 3 1
1 3 4 2
```
Expected output
```
1
```