题目描述

有一家大型酒店，有 $n$ 名顾客即将入住。每位顾客都需要一个单独的房间。

你已知每位顾客的到达日和离开日。如果第一位顾客的离开日早于（即小于）(第二位顾客的到达日，那么他们可以住在同一个房间。

现在请你求出，为了容纳所有顾客，酒店最少需要多少个房间？以及如何分配这些房间？

输入格式

第一行一个整数 $n$，表示顾客的数量。

接下来 $n$ 行，每行两个整数 $a, b$，表示一位顾客的到达日和离开日。

输出格式

首先输出一个整数 $k$，表示所需的最少房间数。

接下来输出一行，包含 $n$ 个整数，依次表示每位顾客被分配到的房间号。房间号从 $1, 2, \dots, k$ 编号。如果有多种可行的分配方案，你可以输出任意一种。

3
1 2
2 4
4 4

2
1 2 1

数据规模与约定

数据范围

对于全部测试数据，满足 $1 \le n \le 2 \times 10^5$， $1 \le a \le b \le 10^9$。

自定义类型的优先队列使用方法

C++中 STL 的优先队列 priority_queue 默认“最大”的元素放在队头。 结构体类型的优先队列使用方法如下：

struct Type{
	int a,b,c,d;
};
//重载 Type 的 < 运算符，将 a 作为比较大小的关键字
bool operator<(const Type& x,const Type& y){
	return x.a < y.a;
	//如需让优先队列将队头元素最小化
	//则改为 return x.a > y.a;
}

//创建优先队列，默认为大根堆（队头元素最大）
priority_queue<Type> big_queue;