题目描述

译自 BalticOI 2009 Day1 T2「Candy Machine」

在糖果工厂中，有一台神秘的机器。它生产许多美味的糖果，每一个都与众不同。这个机器有一排输出槽，编号为 $1$ 到 $n$，糖果加工完毕就会从里面出来。没有人真正知道它的工作原理，但是在每一次产品计划之前，它会打印一个列表告诉老板每个糖果会在何时从哪个槽出来。

现在，老板可以安装自动收集车在每个槽下移动，以收集掉落的糖果。当然，糖果不能掉到地上，不然就会碎裂。然而，安装自动收集车的成本极其高昂，老板想尽量少安装自动收集车。

写一个程序计算接住所有糖果需要的自动收集车的数量，它应当尽可能小。此外，你的程序还需要输出每颗糖果会被哪辆收集车接住。收集车每秒可以从一个槽移动到另一个相邻的槽。在生产过程开始前，每辆收集车可以移动到他应当收集的第一个糖果的位置。

输入格式

第一行，一个整数 $n$，表示将要生产的糖果的数量。

以下 $n$ 行，每行两个整数 $s_i$ 和 $t_i$，表示第 $i$ 颗糖果的输出槽和输出时间。每一组 $(s_i,t_i)$ 互不相同。

输出格式

第一行，一个整数 $w$，表示接住所有糖果需要的收集车的数量（尽量小）。
收集车被编号为 $1$ 到 $w$。

以下 $n$ 行描述每颗糖果会被哪辆收集车接住。
出于此目的，这 $n$ 行每行三个整数：第 $j$ 颗糖果的输出槽 $s_j$ 和输出时间 $t_j$ 和收集车的编号 $w(j)$。表示在时刻 $t_j$ 收集车 $w(j)$ 会在槽 $s_j$ 下并接到糖果。

样例

5
1 1
2 3
1 5
3 4
2 6

2
1 1 1
2 3 1
1 5 2
3 4 1
2 6 2

数据范围与提示