Risk Game Conflict Detection

The game of Risk has become a national phenomenon after years of promotion. In the game, each country is represented by a simple polygon (i.e. a polygon whose boundary does not intersect itself) and a point indicating the location of its largest army (which is guaranteed to lie strictly inside the polygon, not on its boundary). Two countries are considered to be in potential conflict if their borders share a common segment of positive length. Note that if the territories of two countries touch at only a single point, they are not considered adjacent.

More formally, let each country be represented by a simple polygon with vertices \(v_0,v_1,\dots,v_{m-1}\) and let its border consist of the \(m\) edges

[ \overline{v_0v_1},,\overline{v_1v_2},,\dots,,\overline{v_{m-1}v_0} ]

We say that two countries are adjacent if there exists an edge in one polygon that exactly matches (possibly in reverse order) an edge in the other polygon.

Your task is to determine all pairs of countries that are adjacent according to the above definition. Countries are numbered from 1 to \(n\) in the order of input. Output the number of adjacent pairs followed by each pair in increasing order (first by the smaller index then by the larger index).

inputFormat

The input begins with an integer \(n\) (the number of countries). For each country, the input is given in the following format:

 m
 x1 y1
 x2 y2
 ...
 xm ym
 a b

Here, \(m\) is the number of vertices of the country’s border (in order), followed by \(m\) lines each containing two integers \(x_i\) and \(y_i\) which represent the coordinates of the vertices. Finally, a line with two integers \(a\) and \(b\) is given, representing the position of the largest army, which is guaranteed to lie strictly inside the polygon. All polygons are guaranteed to be simple and non-self-intersecting.

outputFormat

First, output an integer \(k\) which denotes the number of pairs of adjacent countries. Then output \(k\) lines, each containing two integers \(i\) and \(j\) (with \(i<j\)), indicating that country \(i\) and country \(j\) are adjacent. The pairs should be listed in sorted order (first by \(i\), then by \(j\)).

sample

2
3
0 0
3 0
0 3
1 1
3
0 0
-3 0
0 -3
-1 -1

0