Drawing Problem#5673
Recently Andy has found an old book in the attic. The book from the end of the XIX-th century contains a lot of various puzzles. One puzzle impressed Andy very much — the complicated figure is drawn on the page and the task is to draw it in one stroke, never lifting the pen off the paper and never drawing the same non-zero part twice. To make the problem harder, the additional quest is to do it drawing the minimal number of segments.
Having spent several hours on the problem, Andy asked you to write the program that would do it for him.
Input file contains the figure to be drawn as the set of segments. First the number of segments is specified. It is followed by segments descriptions. Each segment is described with coordinates of its endpoints. All segments are parallel to the sides of the page, that are aligned with coordinate axes.
The number of segments does not exceed , all coordinates are integer and do not exceed by their absolute value, no two segments have a part of non-zero length in common.
If it is impossible to fulfil the task, output on the first line of the output file. In the other case output the minimal number of segments to draw, followed by the segments themselves. Remember that it must be possible to draw segments continuously in order you list them, neither lifting the pen off the paper, nor drawing any non-zero segment twice. Endpoints of each segment must be listed in such an order, that it is drawn from the first endpoint to the second one.
Example 1