题目描述

多边形的三角剖分是指这个多边形上的点组成的三角形的集合，这些三角形不能重叠，并且能覆盖住整个多边形。

对多边形的 $\rm{CUT}$ 指用一条直线将多边形分成两部分。

现在给出一个多边形的三角剖分，每个三角形都有自己的颜色，问你对这个多边形最多可进行多少次 $\rm{CUT}$ 使得同一颜色的点在同一块中。

输入格式

第一行给出数字 $n$。

下面 $n-2$ 行，每行四个数 $a,b,c,d$ 表示由顶点 $a,b,c$ 组成的三角形的颜色为 $d$。

输出格式

最多要进行多少次 $\rm{CUT}$。

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

1

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

2

样例解释

数据规模与约定

对于 $100\%$ 的数据，满足 $3\le n\le 10^5$。