Simple Polygons
------ --------

A polygon is a closed circular chain of line segments.
A simple polygon is a polygon such that no two non-
adjacent segments intersect each other.

A polygon's vertices are the ends of its line segments.
A polygon may be defined by listing its vertices in the
order that they are first encountered while traversing
the chain of line segments, so each consecutive pair of
vertices defines one of the line segments, and there is
also a line segment connecting the first and last
vertex.

Your friend Improbable George has come up with a new way
to generate very large random simple polygons very fast.
Unfortunately a very few of his polygons are not simple
and have a few intersections.  He wants you to come
up with an equally fast way of checking whether a very
large polygon is simple and identifying its few inter-
sections if it is not.  Here an intersection is defined
as any pair of non-adjacent segments that touch each
other.


Input
-----

For each test case, first a line that gives the test
case name.  Then a line of the form

	V

giving the number of vertices.  Then V lines each giving
the coordinates (Vx,Vy) of one vertex in the format:

	Vx Vy

The vertices are given in the order they appear on the
polygon boundary, with the last vertex being connected
to the first vertex.

All input numbers are integers.  No two vertices will
have the same coordinates (this is a property of
Improbable's polygon generator).

	3 <= V <= 100,000
	-1,000,000 <= Vx, Vy <= +1,000,000

Input ends with an end of file.  Test case name lines
are at most 80 characters.


Output
------

For each test case, first an exact copy of the test case
name line.  Then a line containing just

	W

which is the number of intersections.  Then W lines
each containing

	s1 s2

identifying pairs (s1,s2) of non-adjacent segments that
intersect (i.e., that touch each other).  Note you are
outputting pairs of non-adjacent segments that touch
each other, and not the intersection points themselves,
so, for example, if 4 non-adjacent segments intersect at
a single point you output 4*(4-1)/2 = 6 segment pairs.

A segment identifier s refers the segment whose first
vertex is the s'th vertex input and whose second vertex
is the s+1'st vertex input, except if s == V it is
the 1'st vertex input instead.

In order to make judging easier, the intersections must
be sorted.  s1 < s2 is required.  The intersections
must be in order of increasing s1, and for those with
equal s1, in order of increasing s2.

Segments may intersect at a point or by overlapping.
The interior of a segment may contain a vertex of
another segment, thus intersecting the other segment.
However, two non-adjacent segments cannot intersect by
sharing a vertex, as all vertices are unique.

Importantly, you may assume that

	W <= 100


Sample Input
------ -----

-- SAMPLE 1 --
4
 0  0
 0 10
10 00
10 10
-- SAMPLE 2 --
14
  0   0
100   0
 20  20
100  40
 60  60
100  80
 20 100
100 120
  0 120
 80 100
  0  80
 40  60
  0  40
 80  20


Sample Output
------ ------

-- SAMPLE 1 --
1
2 4
-- SAMPLE 2 --
4
2 14
3 13
6 10
7 9


File:	   simplepoly.txt
Author:	   Bob Walton <walton@seas.harvard.edu>
Date:	   Sat Oct  7 14:16:36 EDT 2017

The authors have placed this file in the public domain;
they make no warranty and accept no liability for this
file.