P2610 [ZJOI2012] Travel

During the rare summer vacation, to celebrate Xiaobai’s excellent performance in the math exam, Xiaolan decides to take Xiaobai on a trip~~ After some deliberation, they choose Country T as their destination. The territory of Country T can be represented by a convex $n$-gon, and the $n$ vertices represent $n$ entry/exit ports. Country T contains $n - 2$ cities, each city being a triangle whose vertices are vertices of the $n$-gon (in other words, the cities form a triangulation of Country T). The travel route of the two can be regarded as a line segment connecting two non-adjacent vertices among the $n$ vertices.  To buy the best souvenirs, Xiaobai hopes the route passes through as many cities as possible. As Xiaolan’s friend, can you help?

Each input file contains only one test case. The first line contains a positive integer $n$, as described above. Then there are $n - 2$ lines. Each line contains three integers $p, q, r$, indicating the vertex indices of that city’s triangle (the $n$ vertices of Country T are numbered from $1$ to $n$ in clockwise order).

Output a single line: the maximum number of cities that can be passed through. (A city is counted as passed if and only if it shares at least two common points with the route.)

For $20\%$ of the testdata, $n \le 2000$. For $100\%$ of the testdata, $4 \le n \le 200000$. Translated by ChatGPT 5