A number of segments are lying on a line. Every segment is given with the coordinates of its endpoints. Segments are numbered from 1 to N (0 < N < 500). We assume, that one segment is inside another, if the two segments are different, the first one is fully contained in the second one, and their endpoints do not coincide. Write a program, which finds the numbers of the segments in the longest sequence of segments which are contained in. In the sequence, every segment except the last is inside the next segment in the sequence.
The first line contains one integer N. Next, there are N lines, with two integers on every line, which are the coordinates of the left and the right endpoints of the corresponding segment. These coordinates
are integers in the interval [–10000, 10000]. We assume that, the given segments are numbered according to their place in the input.
The first line must contain one integer, equal to the number of segments in the found sequence. The following line must contain the numbers of the segments in this sequence. These numbers must be outputted, in the order in which the segments' lengths increase, starting from the smallest.
If there are more than one output sequences, write any of them.
2 1 3
Problem Author: Emil Kelevedzhiev
Problem Source: Winter Mathematical Festival Varna '2001 Informatics Tournament