[IOI2007] flood 洪水

1964年的一场灾难性的洪水冲毁了萨格勒布城。洪水袭来时许多建筑的墙被彻底冲毁。在这个题目中，给定了城市在洪水来袭前的简化模型，你的任务是确定洪水过后哪些墙没有被冲毁。 简化模型由平面上的$N$个点和$W$堵墙构成。每堵墙连接两个点，没有任何一堵墙通过其它点。模型具有如下性质： - 不存在两堵墙相交或者重合的情况，但是两堵墙可以在端点相连； - 每堵墙或者平行于坐标系的横轴，或者平行于坐标系的纵轴。 最开始，整个坐标平面都是干的。在零时刻，洪水将城市的外围淹没（城市的外围是指没有被墙围起来的区域）。一个小时之后，所有一边是水，一边是空气的墙在水的压力下都会倒塌。于是洪水又会吞没那些没有被完好的墙围住的区域。接下来又有一些墙面临一边是水一边是空气，将要被洪水冲毁的局面。又过了一个小时，这些墙也被冲毁了。这样的过程不断重复，直到洪水淹没整个城市。 下图给出了洪水侵袭过程的一个例子。  给定$N$个点的坐标和连接这些点的$W$堵墙的描述，编程确定洪水过后，哪些墙会被留下来。

输入的第一行包含一个整数$N(2 \leq N \leq 100 000)$, 表示平面上的点的个数。 接下来的$N$行每行包含两个整数$X$和$Y$（都是$0$到$1 000 000$之间（包括$0$和$1 000 000$）的整数），表示点的坐标。所有点按照它们被给出的顺序编号为$1$到$N$。没有两个点在同一位置上。 接下来一行包含一个整数$W(1 \leq W \leq 2N)$，表示墙的数目。 接下来$W$行每行包含两个不同的整数$A$和$B(1 \leq A \leq N, 1 \leq B \leq N)$，表示在洪水到来前，有一堵墙连接$A$和$B$。这些墙按照它们被给出的顺序编号为$1$到$W$。

输出的第一行包含一个整数$K$，表示洪水过后留下的墙的数目。 接下来的$K$行包含留下的墙的序号，每行一个，序号可以以任意顺序输出。

15 
1 1 
8 1 
4 2 
7 2 
2 3 
4 3 
6 3 
2 5 
4 5 
6 5 
4 6 
7 6 
1 8 
4 8 
8 8 
17 
1 2 
2 15 
15 14 
14 13 
13 1 
14 11 
11 12 
12 4 
4 3 
3 6 
6 5 
5 8 
8 9 
9 11 
9 10 
10 7 
7 6 

4 
6 
15 
16 
17 

这个样例对应前页图中的例子。 有40分的测试点，所有坐标小于等于$500$。 在上面的测试点和另外15分的测试点中，点的个数不超过$500$个。