#PQJ66x10762. QOJ 66_10762

    ID: 3020 传统题 1000ms 128MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:ZJOI 2012

QOJ 66_10762

旅游(journey) 【题目描述】 到了难得的暑假,为了庆祝小白在数学考试中取得的优异成绩,小蓝决定 带小白出去旅游~~ 经过一番抉择,两人决定将T 国作为他们的目的地。T 国的国土可以用一个 凸N 边形来表示,N 个顶点表示N 个入境/出境口。T 国包含N-2 个城市,每个 城市都是顶点均为N 边形顶点的三角形(换而言之,城市组成了关于T 国的一个 三角剖分)。两人的旅游路线可以看做是连接N 个顶点中不相邻两点的线段。

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

为小蓝的好友,你能帮帮小蓝吗? 【输入说明】 每个输入文件中仅包含一个测试数据。 第一行包含两个由空格隔开的正整数N,N 的含义如题目所述。 接下来有N-2 行,每行包含三个整数 p,q,r,表示该城市三角形的三个顶点 的编号(T 国的N 个顶点按顺时间方向从1 至n 编号)。 【输出说明】 输出文件共包含1 行,表示最多经过的城市数目。(一个城市被当做经过当 且仅当其与线路有至少两个公共点) 【样例输入】 6 1 2 4 2 3 4 1 4 5

 1 5 6 

【样例输出】 4 【数据范围】 对于20%的数据,

对于100%的数据,