Flood#281
In , a catastrophic flood struck the city of Zagreb. Many buildings were destroyed as water broke through their walls. In this task, you are given a simplified model of the city before the flood and must determine which of the walls remain standing after the flood.
The model consists of points in the coordinate plane and walls. Each wall connects a pair of points and does not pass through any other points. The model has the following properties:
No two walls intersect or overlap, but they may touch at endpoints;
Each wall is parallel to either the horizontal or the vertical coordinate axis.
Initially, the entire coordinate plane is dry. At time zero, water instantly floods the exterior (the space not bounded by walls). After exactly one hour, every wall with water on one side and air on the other breaks under the water pressure. Water then instantly floods the new area not bounded by intact walls. As a result, there may be new walls with water on one side and air on the other. After another hour these walls also break down, and water floods further. This process continues until water floods the entire area.
An example of the process is shown in the figure (the time interval between states is one hour).
The first line contains an integer (2 \leq N \leq 100\ 000), the number of points in the plane.
Each of the following lines contains two integers and (0 \leq X, Y \leq 1\ 000\ 000), the coordinates of a point. The points are numbered from to in the order in which they are given. No two points coincide.
The next line contains an integer (1 \leq W \leq 2N), the number of walls.
Each of the following lines contains two different integers and (1 \leq A, B \leq N) indicating that there was a wall connecting points and before the flood. The walls are numbered from to in the order they are given.
The first line should contain an integer , the number of walls remaining after the flood.
The following lines should contain the indices of the walls that remain, one per line. The indices may be given in any order.
Example 1