题目描述

盼望已久的假期终于到了。为了庆祝小岚在期末测验里的出色发挥，阿澈答应带她出海度假。两人挑中的目的地是翡翠岛——它的版图恰好是一个凸 $n$ 边形，$n$ 个顶点就是 $n$ 个出入岛的口岸。岛上分布着 $n-2$ 个街区，每个街区都是以 $n$ 边形顶点为端点的三角形（换句话说，这些街区正好构成翡翠岛版图的一种三角剖分）。两人的游览航线可以看作是连接 $n$ 个顶点中不相邻两点的线段。

小岚想多带些纪念品回去，所以希望航线沿途经过的街区尽量多。作为阿澈的智囊，你能帮他算出这个最大值吗？

输入格式

每个输入文件中仅包含一个测试数据。

第一行包含一个正整数 $n$，$n$ 的含义如题目所述。

接下来有 $n-2$ 行，每行包含三个整数 $p,q,r$，表示该街区三角形的三个顶点的编号（翡翠岛的 $n$ 个顶点按顺时针方向从 $1$ 至 $n$ 编号）。

输出格式

输出文件共包含一行，表示最多经过的街区数目。（一个街区被当做经过，当且仅当它与航线有至少两个公共点）

样例

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

4

提示

对于 $20\%$ 的数据，$n\le 2000$。

对于 $100\%$ 的数据，$4\le n \le 200000$。