Electric Wires 2

Several electric wires connect utility poles A and B. If two different wires cross, there is a risk of a short circuit, so some wires must be removed so that no remaining wires cross.

In the configuration shown below, removing the wire connecting position 1 on pole A to position 8 on pole B, the wire connecting position 3 on pole A to position 9 on pole B, and the wire connecting position 4 on pole A to position 1 on pole B leaves all remaining wires non-crossing.

Positions where wires attach to a pole are numbered from top to bottom. Given the number of wires and the position numbers where each wire is attached to the two poles, find the minimum number of wires that must be removed to eliminate all crossings, and output the position numbers on pole A for the wires to remove.

The first line contains the number N of wires between the two poles. N is a positive integer not greater than 100,000.

Each of the next N lines contains two integers: the position number where one wire is attached to pole A, followed by the position number where that wire is attached to pole B. Each position number is a positive integer not greater than 500,000. No two wires are attached to the same position on the same pole.

On the first line, print the minimum number of wires that must be removed so that all remaining wires are non-crossing.

Starting on the second line, print the pole-A position number of each wire to remove, one per line, in increasing order. If there is more than one valid answer, print any one of them.