2479: 畜栏预定

内存限制:128 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:Special Judge 上传者:
提交:1 通过:0

题目描述

有 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

分类标签