P3229 [HNOI2013] 旅行

在遥远的 HX 国，住着一个旅行家小 L，他希望骑着他的自行车游遍全国。在这个国家中，每个城市都有一个编号，共有 $n$ 个城市，编号从 $1$ 到 $n$。 有的城市没有小 L 想去的景点，而有的城市有且仅有一个小 L 想去的景点，所有的城市都是这两种情况之一，小 L 非常热爱信息学，他编写程序给他的旅行安排了一条最短路线以到达所有他想去的景点（所有的通知旅行线路上城市编号是乱序的）：他第 $1$ 个到达的城市编号为 $a_1$，第 $i$ 个到达的城市编号为 $a_i$，最后到达城市 $a_n$ 结束这次旅行。小L希望用恰好的 $m$ 个月（$m

无

无

第 $1$ 个月得到 $2$ 点快乐值与 $2$ 点疲劳值，第 $2$ 个月得到 $1$ 点快乐值与 $1$ 点疲劳值，第 $3$ 个月得到 $1$ 点快乐值与 $1$ 点疲劳值。$3$ 个月中疲劳值与快乐值差的最大值为 $0$，达到所有方案最小值。 可行方案有： - 1 6 8 - 3 6 8 - 3 1 8 其中 1 6 8 字典序最小。 $N \leq 5 \times 10^5$，$M \leq 2 \times 10^5$。