说明

本题差SPJ，欢迎大家提供标准SPJ

题目描述

有 $N$头牛在畜栏中吃草。

每个畜栏在同一时间段只能提供给一头牛吃草，所以可能会需要多个畜栏。

给定$N$头牛和每头牛开始吃草的时间 A 以及结束吃草的时间$B$，每头牛在 [A,B] 这一时间段内都会一直吃草。

当两头牛的吃草区间存在交集时（包括端点），这两头牛不能被安排在同一个畜栏吃草。

求需要的最小畜栏数目和每头牛对应的畜栏方案。

输入格式

第 1 行：输入一个整数$N$。

第 2..$N$+1 行：第 $i$+1 行输入第 $i$头牛的开始吃草时间 $A$以及结束吃草时间 $B$，数之间用空格隔开。

输出格式

第 1 行：输出一个整数，代表所需最小畜栏数。

第 2..$N$+1 行：第 $i$+1 行输出第 $i$头牛被安排到的畜栏编号，编号是从 1 开始的 连续 整数，只要方案合法即可。

样例

5
1 10
2 4
3 6
5 8
4 7

4
1
2
3
2
4

数据范围

• $1≤N≤50000$
• $1≤A,B≤1000000$

来源

• USACO 2006 Feb.
• poj3190
• 算法竞赛进阶指南