P3229 [HNOI2013] 旅行

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

第一行为两个空格隔开的正整数 $n, m$，表示旅行的城市数与旅行所花的月数。 接下来 $n$ 行，其中第 $i$ 行包含两个空格隔开的整数 $A_i$ 和 $B_i$，$A_i$ 表示他第 $i$ 个去的城市编号，$B_i$ 为 $0$ 或 $1$。如果 $B_i=0$ 则表示城市 $A_i$ 没有小 L 想去的景点，如果 $B_i=1$ 则表示城市 $A_i$ 有小 L 想去的景点，$A_i$ 两两不同且有 $1\leq A_i\leq N$，即 $\{A_i\}$ 为 $1,2,\ldots,N$ 的一个排列。

输出仅包含一行，包含 $m$ 个空格隔开的正整数 $X_1,X_2,\ldots,X_m$，即给小 L 安排的旅行计划对应的路线。

第 $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$。