方阵的次对角线是从右上角到左下角的对角线。让我们将 n 度楼梯定义为方阵 n × n,在次对角线上方不包含任何正方形(下图显示了 5 度楼梯)。
n 度楼梯的方格包含 m 个运动员。
一名运动员需要一秒钟才能移动到楼梯旁边的一个正方形。比赛开始前,每位运动员必须选择到达次对角线的最短路线之一。
起跑哨响后,比赛开始,所有运动员开始沿着选定的路径移动。当运动员到达次对角线的一个单元格时,他停下来不再移动。当所有运动员到达次对角线时,比赛结束。如果比赛期间没有两名运动员同时出现在同一个广场上,则比赛被认为是成功的。属于次对角线的任何方格也不能包含超过一名运动员。如果一名运动员在给定时刻离开一个方格,而另一名运动员来到该方格,则不认为他们同时占据同一个方格。请注意,其他极端情况(例如,两名运动员朝对方移动)是不可能的,因为所选择的路线是最短的路线。
给定了楼梯上 m 个运动员的位置。你的任务是从其中选择能够在比赛中获胜的最大数量的运动员,也就是说,存在这样一种最短路径选择,使得没有两个运动员同时出现在同一个方格中。所有其他未被选中的运动员将在比赛开始前被从楼梯上移走。
输入
第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 105)。然后 m 行包含运动员在楼梯上的坐标,作为整数对 ri, ci (1 ≤ ri, ci ≤ n, n - ci < ri),其中 ri 是楼梯行数,ci 是楼梯列数(要了解行和列编号的原理,请参见解释图片)。没有两个运动员站在楼梯的同一个正方形上。
输出
在第一行打印所选运动员的号码。在第二行中以任意顺序打印所选运动员的号码,并用空格分隔号码。如果有多个答案,您可以打印其中任何一个。运动员按照输入数据中给出的顺序从 1 开始编号。
示例
输入 #1
3 3 2 3 3 2 3 3
输出 #1
3 1 2 3
注意
第一个示例的注释。