[SGU521] “North-East”

题目描述

著名乐队 “North-East” 即将在 Berland 巡演。现在只知道他们会访问若干座城市，并且从一座城市前往下一座城市时，始终同时向东、向北移动。

也就是说，如果乐队从城市 $i$ 前往城市 $j$，那么必须满足：

• $x_j>x_i$；
• $y_j>y_i$。

乐队希望访问尽可能多的城市。设所有能够访问最大城市数的巡演方案为“最优巡演”。

请找出两个城市集合：

• 集合 $A$：至少出现在一个最优巡演中的城市；
• 集合 $B$：出现在每一个最优巡演中的城市。

输入格式

第一行一个整数 $n$，表示城市数量。

接下来 $n$ 行，每行两个整数 $x_i,y_i$，表示第 $i$ 座城市的坐标。

保证不存在两座城市位于同一点。

输出格式

第一行输出集合 $A$。先输出集合大小，然后按编号从小到大输出其中所有城市编号。

第二行输出集合 $B$，格式相同。

数据范围

$1\le n\le10^5$，$-10^6\le x_i,y_i\le10^6$。

样例 1

样例输入

5
3 2
1 1
5 5
2 3
4 4

样例输出

5 1 2 3 4 5
3 2 3 5

样例 2

样例输入

5
1 1
10 10
5 6
10 1
6 5

样例输出

4 1 2 3 5
2 1 2