Description

A catastrophic flood in 1964 destroyed the city of Zagreb. When the flood arrived, the walls of many buildings were completely destroyed. In this problem, you are given a simplified model of the city before the flood, and your task is to determine which walls were not destroyed after the flood.

The simplified model consists of $N$ points on the plane and $W$ walls. Each wall connects two points, and no wall passes through any other point. The model has the following properties:

• No two walls intersect or overlap, but two walls may share an endpoint.
• Each wall is either parallel to the $x$-axis or parallel to the $y$-axis.

At the beginning, the entire coordinate plane is dry. At time $0$, the flood inundates the outside of the city (the outside means the region not enclosed by walls). After one hour, every wall that has water on one side and air on the other side will collapse due to the water pressure. Then the flood will inundate those regions that are not enclosed by intact walls. Next, some walls again have water on one side and air on the other and are about to be destroyed. After another hour, these walls also collapse. This process repeats until the flood inundates the whole city.

The figure below shows an example of the flooding process.

Given the coordinates of the $N$ points and the descriptions of the $W$ walls connecting these points, write a program to determine which walls remain after the flood.

Input Format

The first line contains an integer $N(2 \leq N \leq 100 000)$, the number of points on the plane. The next $N$ lines each contain two integers $X$ and $Y$ (both integers between $0$ and $1 000 000$ (inclusive)), giving the coordinates of a point. All points are numbered from $1$ to $N$ in the order they are given. No two points share the same position. The next line contains an integer $W(1 \leq W \leq 2N)$, the number of walls. The next $W$ lines each contain two different integers $A$ and $B(1 \leq A \leq N, 1 \leq B \leq N)$, meaning that before the flood there is a wall connecting $A$ and $B$. These walls are numbered from $1$ to $W$ in the order they are given.

Output Format

The first line contains an integer $K$, the number of walls that remain after the flood.

The next $K$ lines contain the indices of the remaining walls, one per line. The indices may be output in any order.

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 

Hint

This sample corresponds to the example in the figure on the previous page.

For $40$ points of testdata, all coordinates are at most $500$.

In the above testdata and another $15$ points of testdata, the number of points does not exceed $500$.

Translated by ChatGPT 5