Remaining Walls after the Flood

In 1964 a catastrophic flood hit Zagreb and swept away many walls of buildings. In this problem a simplified model of the city is given; the model consists of N points in the plane and W walls connecting some pairs of points. Each wall (a line segment) connects two points and does not pass through any other point. Moreover, no two walls intersect or overlap (although they may meet at endpoints), and every wall is either horizontal or vertical.

At time 0 the flood water invades all regions that are not enclosed by walls (i.e. the outside). One hour later, every wall that has water on one side and air on the other collapses under the water pressure, and the water then advances into the newly opened regions. One hour later, any wall that now has water on one side and intact air on the other is swept away, and so on. This process repeats until the flood water eventually covers the entire city. Your task is to determine, after the entire process, which walls remain standing.

A key observation is that the walls that survive are exactly those for which the two sides are flooded at the same time – they are never subject to a water–air pressure difference when the wall could be swept away. Formally, one may think of the walls as boundaries between faces (regions) in the planar subdivision induced by the walls. Defining a flooding time for each face (with the unbounded face having time 0 initially and the water propagating through open gaps at cost 0, but through an intact wall incurring a delay of 1 hour), a wall will break if and only if the flooding times on its two sides differ. (Any formula should be written in \( \LaTeX \) format.)

More precisely, if we denote by \(T_1\) and \(T_2\) the flooding times of the two faces adjacent to a wall, then the wall will be destroyed if \(T_1 \neq T_2\) and will survive otherwise.

Input Format: The first line contains two integers \(N\) and \(W\). The following \(N\) lines contain the coordinates of the points. Then the following \(W\) lines describe the walls. Each wall is given by two integers \(u\) and \(v\) (1-indexed) which indicate that there is a wall connecting the \(u\)th point and the \(v\)th point. It is guaranteed that every wall is either horizontal (i.e. with constant \(y\)) or vertical (i.e. with constant \(x\)), and that no wall passes through a point other than its endpoints.

Output Format: On the first line output an integer \(M\) denoting the number of walls that remain after the flood. On the next line output the indices (in increasing order) of these walls (walls are numbered from 1 to \(W\) in the input order).

Note: It is advisable to use \(\LaTeX\) for any mathematical expressions (for example, use \(N\) and \(W\), and write formulas like \(T_1 \neq T_2\) in \(\LaTeX\) format).

inputFormat

The input begins with a line containing two integers \(N\) and \(W\). The next \(N\) lines each contain two integers representing the \(x\) and \(y\) coordinates of a point. The following \(W\) lines each contain two integers \(u\) and \(v\) (1-indexed) meaning there is a wall connecting the \(u\)th and \(v\)th points.

outputFormat

Output the number of walls that remain followed by a line containing the indices of the surviving walls in increasing order, separated by spaces.

sample

4 4
0 0
0 1
1 1
1 0
1 2
2 3
3 4
4 1

0