多边形的三角剖分是指一组顶点均为多边形顶点的三角形集合。这些三角形不能重叠，且必须覆盖整个多边形。

我们定义多边形的“割”（cut）为一条将多边形分割成两部分的直线。

给定一个已三角剖分的凸多边形，其中每个三角形都染有某种颜色。求最多可以进行多少次割，使得任意两个具有相同颜色的点都不会被分到两个不同的部分中。

输入格式

输入从标准输入读取。

第一行包含一个整数 $n$，表示顶点的数量。顶点用 $1$ 到 $n$ 之间的唯一整数编号。

接下来的 $n - 2$ 行，每行包含四个整数 $a, b, c$ 和 $d$（$1 \le a, b, c, d \le n$），表示以 $a, b, c$ 为顶点的三角形的颜色为 $d$。其中 $a, b, c$ 是三个不同的顶点。

输入数据保证是一个合法的多边形三角剖分，且所有三角形都已染色。

输出格式

输出到标准输出，包含一行一个整数，表示最大可进行的割的数量。

样例

输入 1

5
1 2 3 2
4 5 1 1
3 1 4 2

输出 1

1

输入 2

6
1 4 2 1
2 4 5 2
6 2 5 3
3 6 5 1

输出 2

0

数据范围

$3 \le n \le 100,000$。

子任务

对于占总分 50% 的测试数据，满足 $n \le 5000$。