Competition

题意翻译

我们定义方阵的辅助对角线是从右上角到左下角的对角线，一个n阶楼梯是一个n*n的方阵不超过辅助对角线的部分（如图是一个5阶楼梯）。 已知在一个n阶楼梯上有m个运动员，我们给出每个运动员的坐标（如图示）。每个运动员移动一格需要1s，他们会从初始坐标通过一条最短的路径运动到辅助对角线上的格子（一个运动员可能有多条路径）。 我们定义满足如下条件的比赛是成功的： 1：比赛开始时所有运动员沿着一条最短的路径运动，运动到辅助对角线上时停止。所有运动员都停止时，比赛结束。 2：比赛过程中的任意时刻，不能有两个运动员出现在同一个方格内（同一时刻a离开(x,y)格，b进入（x,y）格不算同时出现）。 3：比赛结束时不能有多个运动员出现在同一个方格内。 给定m个运动员的位置，请你选出尽量多的运动员使得比赛能够成功进行（未被选择的运动员将在比赛开始前被移出楼梯）。 第一行输出选择的运动员的个数。 第二行输出选择运动员的坐标，若有多种方案，则输出任意一种即可。

题目描述

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.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ m $ ( $ 1<=n,m<=10^{5} $ ). 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}&lt;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.

输出格式

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

3 3
2 3
3 2
3 3

输出样例 #1

3
1 2 3 

说明

A note to the first sample.  The picture shows a three-degree staircase. The arrows show the shortest paths that the sportsmen choose.