F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:五月份月赛定于5.27日12:30--17:30,欢迎大家来玩! 2:关于OJ的注册可看https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671
Problem 2657. -- [Zjoi2012]旅游(journey)

2657: [Zjoi2012]旅游(journey)

Time Limit: 5 Sec  Memory Limit: 128 MB
Submit: 1101  Solved: 703
[Submit][Status][Discuss]

Description

     到了难得的暑假,为了庆祝小白在数学考试中取得的优异成绩,小蓝决定带小白出去旅游~~

    经过一番抉择,两人决定将T国作为他们的目的地。T国的国土可以用一个凸N边形来表示,N个顶点表示N个入境/出境口。T国包含N-2个城市,每个城市都是顶点均为N边形顶点的三角形(换而言之,城市组成了关于T国的一个三角剖分)两人的旅游路线可以看做是连接N个顶点中不相邻两点的线段

   为了能够买到最好的纪念品,小白希望旅游路线上经过的城市尽量多。作为小蓝的好友,你能帮帮小蓝吗?

Input

 每个输入文件中仅包含一个测试数据。
第一行包含两个由空格隔开的正整数NN的含义如题目所述。
     接下来有N-2行,每行包含三个整数 p,q,r,表示该城市三角形的三个顶点的编号(T国的N个顶点按顺时间方向从1n编号)

Output

      输出文件共包含1行,表示最多经过的城市数目。(一个城市被当做经过当且仅当其与线路有至少两个公共点)

Sample Input

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

Sample Output

4

HINT

4<=N<=200000

Source

[Submit][Status][Discuss]

HOME Back