Cuộc thi trên bậc thang

Cho ma trận vuông $n\times n$ với các dòng đánh số từ $1$ đến $n$ từ trên xuống và các cột đánh số từ $1$ đến $n$ từ trái sang. Đường chéo phụ là đường chéo đi từ ô góc trên bên phải $(1,n)$ tới ô góc dưới bên trái $(n,1)$, tức là gồm các ô $(i,n+1-i)$ với $1\le i\le n$.

Bậc thang cấp $n$ là ma trận vuông $n\times n$ sau khi bỏ đi mọi ô nằm phía trên đường chéo phụ. Nói cách khác, ô $(r,c)$ thuộc bậc thang khi và chỉ khi $r+c\ge n+1$.

Trên bậc thang cấp $n$ có $m$ vận động viên đứng ở $m$ ô đôi một khác nhau. Mỗi vận động viên cần một giây để di chuyển sang một ô kề cạnh của bậc thang. Trước khi cuộc thi bắt đầu, mỗi vận động viên phải chọn cho mình một trong các đường đi ngắn nhất từ ô đang đứng tới đường chéo phụ.

Sau tiếng còi xuất phát, tất cả vận động viên đồng loạt di chuyển theo đường đã chọn. Khi một vận động viên tới được một ô của đường chéo phụ, người đó dừng lại và không di chuyển nữa. Cuộc thi kết thúc khi mọi vận động viên đều đã tới đường chéo phụ.

Cuộc thi được xem là thành công nếu trong suốt quá trình đó không có thời điểm nào hai vận động viên cùng đứng trên một ô; mỗi ô của đường chéo phụ cũng không được chứa quá một người. Nếu tại một thời điểm một vận động viên rời khỏi một ô và ngay lúc đó một vận động viên khác đi vào ô đấy thì không bị coi là cùng đứng trên một ô. Các tình huống trớ trêu khác (chẳng hạn hai vận động viên đi ngược chiều nhau) là không thể xảy ra, vì mọi đường đi đều là đường đi ngắn nhất.

Hãy chọn ra nhiều vận động viên nhất có thể sao cho tồn tại cách chọn đường đi ngắn nhất cho họ để cuộc thi thành công. Những vận động viên không được chọn sẽ bị loại khỏi bậc thang trước khi cuộc thi bắt đầu.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$.
• $m$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $r_i$ và $c_i$ là toạ độ ô mà vận động viên thứ $i$ đang đứng.

Dữ liệu ra

• Dòng đầu in ra $k$ là số vận động viên được chọn.
• Dòng thứ hai in ra $k$ chỉ số của các vận động viên được chọn theo thứ tự bất kỳ, cách nhau bởi dấu cách. Các vận động viên được đánh số từ $1$ theo thứ tự xuất hiện trong dữ liệu vào.

Nếu có nhiều đáp án, in ra đáp án bất kỳ.

Ràng buộc

• $1\le n,m\le {10}^5$
• $1\le r_i,c_i\le n$ và $n-c_i<r_i$
• Không có hai vận động viên đứng trên cùng một ô

Ví dụ