[Baltic2009]Triangulation

内存限制：64 MiB 时间限制：20 Sec

提交提交记录讨论

多边形的三角剖分是指由这个多边形上的点组成的三角形的集合，这些三角形不能重叠，并且能覆盖住整个多边形。对多边形的CUT指一条直线将多边形分成两部分。现在给出一个多边形的三角剖分，每个三角形都有自己的颜色，问你对这个多边形最多可进行多少次CUT 使得同一颜色的点在同一块中.

第一行给出数字n,3 ≤ n ≤ 100,000. 下面n-2行，每行四个数a,b,c,d表示由顶点a,b,c组成的三角形的颜色为d

最多要进行多少次cut

样例输入


			input data1

5

1 2 3 2

4 5 1 1

3 1 4 2



input data2

6

1 4 2 1

2 4 5 2

6 2 5 3

3 6 5 1

样例输出


			output data1

1



output data2

0