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 ~N~ 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 ~1~ to ~N~.
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.
~3 \le N \le 10^5~
~1 \le a_i, b_i, c_i, d_i \le N~
The triangulation provided in the input will correspond to a valid triangulation of some polygon with ~N~ sides.
For at most 50% of full credit, ~N \le 5 \cdot 10^3~.
The first line will contain a single integer, ~N~.
Each of the next ~N-2~ lines will contain four space-separated integers, ~a_i~, ~b_i~, ~c_i~, and ~d_i~, indicating that the triangle with vertices ~a_i~, ~b_i~, ~c_i~, is colored with color ~d_i~.
Print, on a single line, the maximum number of line segments Victor can draw.
5 1 2 3 2 4 5 1 1 3 1 4 2
6 1 4 2 1 2 4 5 2 6 2 5 3 3 6 5 1