[Hnoi2013]旅行

时间限制:10s      空间限制:128MB

题目描述


输入格式

第一行为两个空格隔开的正整数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}
N<=500000,M<=200000


输出格式

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

提示

1个月得到2点快乐值与2点疲劳值,第2个月得到1点快乐值与1点疲劳值,第3 个月得到1点快乐值与1点疲劳值。3个月中疲劳值与快乐值差的最大值为0,达到所有方 案最小值。

可行方案有:

1  6 8

3  6 8

3  1 8

其中1 6 8字典序最小。


题目来源

没有写明来源