2035: 畜栏预定

Memory Limit：128 MB Time Limit：1.500 S
Judge Style：Text Compare Creator：
Submit：100 Solved：24

Description

有 n 头牛在畜栏中吃草。每个畜栏在同一时间段只能提供给一头牛吃草，所以可能会需要多个畜栏，给出第 i头牛开始吃草的时间区间 [ai, bi]，求需要的最少畜栏数和每头牛对应的畜栏方案。

Input

第一行一个正整数 n 
接下来 n行，分别为ai，bi。

Output

第一行一个整数，表示需要的最少畜栏数。

Sample Input Copy 

5
1 10
2 4
3 6
5 8
4 7

Sample Output Copy 

4

HINT

1<= N <= 5*10^5,    1<= ai, bi <= 10^6