You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

翻译自 CSES-1164 题。

题目描述

有一家大酒店，即将迎来 $n$ 位顾客。每个顾客都希望拥有一个单独的房间。

已知每个顾客的到达和离开日期。如果第一个顾客的离开日期早于第二个顾客的到达日期，那么这两个顾客可以住在同一个房间。

请问，为了容纳所有顾客，最少需要多少个房间？并且如何为这些顾客分配房间？

输入格式

第一行输入一个整数 $n$，代表顾客的数量。

接下来的 $n$ 行，每行描述一个顾客，包含两个整数 $a$ 和 $b$，分别代表顾客的到达日期和离开日期。

输出格式

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

然后输出一行，其中包含每位客户的房间号，顺序与输入相同。房间编号为 $1,2,\dots,k$ 。你可以输出任何有效的解决方案。

样例

3
1 2
2 4
4 4

2
1 2 1

说明/提示

$1 \le n \le 2\cdot 10^5$；

$1 \leq a \leq b \leq 10^9$。