CF144E.Competition

The secondary diagonal of a square matrix is a diagonal going from the top right to the bottom left corner. Let's define an n-degree staircase as a square matrix n × n containing no squares above the secondary diagonal (the picture below shows a 5-degree staircase).

The squares of the n-degree staircase contain m sportsmen.

A sportsman needs one second to move to a side-neighboring square of the staircase. Before the beginning of the competition each sportsman must choose one of the shortest ways to the secondary diagonal.

After the starting whistle the competition begins and all sportsmen start moving along the chosen paths. When a sportsman reaches a cell of the secondary diagonal, he stops and moves no more. The competition ends when all sportsmen reach the secondary diagonal. The competition is considered successful if during it no two sportsmen were present in the same square simultaneously. Any square belonging to the secondary diagonal also cannot contain more than one sportsman. If a sportsman at the given moment of time leaves a square and another sportsman comes to it, then they are not considered to occupy the same square simultaneously. Note that other extreme cases (for example, two sportsmen moving towards each other) are impossible as the chosen ways are the shortest ones.

You are given positions of m sportsmen on the staircase. Your task is to choose among them the maximum number of sportsmen for who the competition can be successful, that is, so that there existed such choice of shortest ways for the sportsmen at which no two sportsmen find themselves in the same square simultaneously. All other sportsmen that are not chosen will be removed from the staircase before the competition starts.

方阵的次对角线（secondary diagonal）是一条从右上角指向左下角的对角线。我们定义一个 $n$ 阶阶梯矩阵为一个 $n \times n$ 的方阵，其中次对角线上方不包含任何方格（如下图所示为一个 5 阶阶梯矩阵）。

该 $n$ 阶阶梯矩阵中共有 $m$ 名运动员。

一名运动员移动到阶梯矩阵中一个与当前所在方格边相邻（即上下左右相邻）的方格需要 1 秒。在比赛开始前，每名运动员必须选定一条通往次对角线的最短路径。

起跑哨声响起后，比赛开始，所有运动员同时沿各自选定的路径移动。当一名运动员抵达次对角线上的某个方格时，他立即停止移动，不再继续前进。当所有运动员均抵达次对角线时，比赛结束。若在整个比赛过程中，任意时刻均无两名运动员同时位于同一方格内，则称该比赛是成功的。此外，次对角线上的每个方格也至多只能容纳一名运动员。注意：若某时刻一名运动员恰好离开某一方格，而另一名运动员恰好进入该方格，则他们不被视为同时占据该方格。需注意，其他极端情况（例如两名运动员相向而行）不可能发生，因为所有运动员选择的均为最短路径。

现给出 $m$ 名运动员在阶梯矩阵中的初始位置。你的任务是：从中选出尽可能多的运动员，使得存在一种为这些被选中运动员指定最短路径的方式，从而保证比赛成功（即任意时刻均无两名运动员同时位于同一方格）。所有未被选中的运动员将在比赛开始前被移出阶梯矩阵。

The first line contains two integers n and m (1 ≤ n, m ≤ 105). Then m lines contain coordinates of sportsmen on the staircase as pairs of integers r__i, c__i (1 ≤ r__i, c__i ≤ n, n - c__i < r__i), where r__i is the number of the staircase row, c__i is the number of the staircase column (to understand the principle of numbering rows and columns see the explanatory pictures). No two sportsmen stand on the same square of the staircase.

第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 10^5$）。接下来 $m$ 行，每行包含一名运动员在楼梯上的坐标，以整数对 $r_i,\,c_i$ 给出（$1 \leq r_i,\,c_i \leq n$，且满足 $n - c_i < r_i$），其中 $r_i$ 表示楼梯的行号，$c_i$ 表示楼梯的列号（关于行列编号规则，请参见说明性图片）。任意两名运动员均不站在楼梯的同一格子上。

In the first line print the number of the chosen sportsmen. In the second line print the numbers of chosen sportsmen in any order, separating the numbers with spaces. If there are several answers, you are permitted to print any of them. The sportsmen are numbered starting from one in the order in which they are given in the input data.

第一行输出所选运动员的数量。
第二行以任意顺序输出所选运动员的编号，编号之间用空格分隔。若存在多种可行答案，输出其中任意一种即可。运动员按输入数据中给出的顺序从 1 开始编号。

A note to the first sample.

The picture shows a three-degree staircase. The arrows show the shortest paths that the sportsmen choose.

对第一个样例的说明。

该图展示了一个三级台阶。箭头表示运动员所选择的最短路径。