좌석 배정

다음 주에 큰 경기가 열린다. 경기장에는 좌석이 $N$개 있고, 좌석마다 $1$번부터 $N$번까지 번호가 붙어 있다. 팬은 표를 한 장 신청하면서 앉아도 괜찮은 좌석 범위를 함께 적는다. 범위는 두 정수 $F$와 $L$로 주어지고, 이 팬은 $F \le S \le L$인 좌석 $S$라면 어느 좌석이든 받아들인다.

매표소에 신청 $M$개가 들어왔다. 두 팬이 같은 좌석을 받을 수는 없다. 동시에 만족시킬 수 있는 신청의 최대 개수를 구하고, 그 개수만큼 좌석을 배정하는 프로그램을 작성하라.

첫 줄에 좌석 수 $N$ ($1 \le N \le 100000$)과 신청 수 $M$ ($1 \le M \le 1000000$)이 공백으로 구분되어 주어진다.

다음 $M$개의 줄에는 신청이 하나씩, 두 정수 $F$와 $L$ ($1 \le F \le L \le N$)로 주어진다. 신청은 입력에 나오는 순서대로 $1$번부터 $M$번까지 번호를 매긴다.

첫 줄에 선택한 신청의 최대 개수 $K$를 출력한다.

이어지는 $K$개의 줄에는 좌석 배정을 좌석 번호가 증가하는 순서로 하나씩 출력한다. 각 줄에는 좌석 번호 $S$와 그 좌석을 받은 신청 번호 $R$을 공백으로 구분해 출력한다.

최대 개수를 만드는 배정은 여러 가지가 있으므로, 다음 규칙으로 정해지는 배정 하나만 정답으로 인정한다. 좌석을 $1$번부터 $N$번까지 차례로 본다. 지금 보고 있는 좌석 $S$에 대해, 아직 좌석을 받지 않았고 $F \le S \le L$을 만족하는 신청을 모은다. 그런 신청이 하나라도 있으면 그중 $L$이 가장 작은 신청에 좌석 $S$를 준다. $L$이 같은 신청이 둘 이상이면 번호가 가장 작은 신청에 준다. 그런 신청이 없으면 좌석 $S$는 비워 둔다.

이 규칙은 만족시킬 수 있는 신청 개수를 항상 최대로 만든다.