旅行
题目描述:
在遥远的 HX 国，住着一个旅行家小 L，他希望骑着他的自行车游遍全国。在这个国家中， 每个城市都有一个编号， 共有 n 个城市， 编号从 1 到 n。 有的城市没有小 L 想去的景点，而有的城市有且仅有一个小 L 想去的景点，所有城市都是这两种情况之一。小 L 非常热爱信息学，他编写程序给他的旅行安排了一条最短路线以到达所有他想去的景点（所以他旅行线路上城市编号是乱序的）：他第 1 个到达的城市编号为 a1，第 i 个到达的城市编号为 ai， 最后到达城市 an 结束这次旅行。小 L 希望用恰好 m 个月（m < n）的时间完成这次旅行，所以他需要制定一个理性的旅行计划。
当他到达一个城市时，如果这个城市有他想要去的景点，他会因此获得 1 点快乐值；但是若到达的城市没有他想去的景点，他会因旅途的疲惫得到 1 点疲劳值。一个月的时间足够他游玩任意多个城市，但他也希望拿出一定时间来休息。他每个月总是在本月所达到的最后一个城市休息（但如果这个城市有景点，那么小 L 总会游玩完这个景点再休息）。当然，小L 希望每个月都能有一定的旅行任务，即便这个月他所到达的城市中并没有他想去的景点，换句话说，每个月他都会至少到达一个新的城市。
小 L 无法自己安排旅行计划，所以求助于你。你需要告诉他一个序列：
x1, x2, …, xm
xi 表示小 L 第 i 个月休息时，他所在的城市编号。由于他最后一个月必须完成他的旅行，所以 xm 肯定等于 an。例如，设 n = 5， m = 3， (a1, a2, a3, a4, a5) = (3, 2, 4, 1, 5)， (x1, x2, x3) = (2,1, 5)，这意味着：第 1 个月先后到达 3 号和 2 号城市，并在 2 号城市休息；第 2 个月先后到达 4 号和 1 号城市，并在 1 号城市休息；第 3 个月到达 5 号城市，并在 5 号城市休息。
这样的方案序列有很多种，设每种方案序列中的第 i 个月旅行中当月获得的快乐值与疲劳值的差的绝对值为 di，设第 k 种方案序列中求出的 d1, d2, …, dm这个 m 个值的最大值为 ck，小 L 希望所选择的方案序列的 ck 在所有方案序列中是最小的。
事实上，可能有多个方案序列的 ck 达到并列最小值。由于小 L 喜爱编程，他患上了一定的强迫症（虽然他自己认为他的强迫症让他炫的发黄），他希望给他的序列是这多个方案中字典序最小的。。
Tips：比较两个序列字典序即比较第一个不相同数字的大小，如 1, 2, 3, 4 < 1, 2, 4, 3。
输入格式:
第一行为两个空格隔开的正整数n, m，表示旅行的城市数与旅行所花的月数。接下来n行，其中第 i行包含两个空格隔开的整数Ai和Bi，Ai表示他第i个去的城市编号。Bi为0或1;如果Bi=0则表示城市Ai没有小L想去的景点，如果Bi=1则表示城市Ai有小L想去的景点，Ai两两不同且有1<=Ai<=N,即{Ai}为1,2....N的一个排列。
例如{2,1,3,4...N}
输出格式:
t仅包括一行，包含m个空格隔开的正整数X1,X2...Xm，t仅包括一行，包含m个空格隔开的正整数X1,X2...Xm，为给小L安排的旅行计划对应的路线。为给小L安排的旅行计划对应的路线。
样例输入:
8 3 2 0 3 1 4 1 1 0 5 0 6 1 7 1 8 0
样例输出:
1 6 8
提示:
【样例解释2】
6 个月中每个月获得的疲劳值与快乐值差均为 1，所以差的最大值为 1，达到所有方案最小值。
对于 10%的数据， n ≤ 10；
对于 25%的数据， m ≤ 10；
对于 30%的数据， n ≤ 100；
对于 40%的数据， m ≤ 100；
对于 40%的数据， n ≤ 1000；
对于 55%的数据， n ≤ 180000；
对于 100%的数据， n ≤ 500000， m ≤ 200000。
空间限制: 256MB
来源: 湖南省选2013day1t3