#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <limits.h>

#define DEBUGGING 0
#define DEBUG0(a) if(DEBUGGING) { printf(a); }
#define DEBUG1(a,b) if(DEBUGGING) { printf(a,b); }
#define DEBUG2(a,b,c) if(DEBUGGING) { printf(a,b,c); }
#define DEBUG3(a,b,c,d) if(DEBUGGING) { printf(a,b,c,d); }
#define DEBUG4(a,b,c,d,e) if(DEBUGGING) { printf(a,b,c,d,e); }
#define MAXPOLYS 10
#define MAXEDGES 20
#define VERTICAL 10000 /* this works since max slope is really 200 */
#define MINDIFF  (1.0/(double)VERTICAL) /* min difference between 'same' slopes */

typedef struct { double x; double y; } point_t;
typedef struct { point_t pstart; point_t pend; double slope; } edge_t;
typedef struct { int edgecount; edge_t e[MAXEDGES]; } poly_t;

FILE *infile;

int numpolys;
poly_t poly[MAXPOLYS];

int points_equal(point_t pt1, point_t pt2) {
   if (pt1.x != pt2.x || pt1.y != pt2.y) return 0;
   return 1;
}

double slope(point_t pt1, point_t pt2) {
   double dx, dy;
   dx = pt1.x - pt2.x;
   dy = pt1.y - pt2.y;
   if (dx == 0) {
      return VERTICAL;
   } else {
      return (dy / dx);
   }
}

int readds () {
   int i,j;
   fscanf(infile,"%d",&numpolys);
   for (i=0;i<numpolys;i++) {
      int numedges;
      fscanf(infile,"%d",&poly[i].edgecount);
      for (j=0;j<poly[i].edgecount;j++) {
         fscanf(infile,"%lf,%lf", &(poly[i].e[j].pstart.x), &(poly[i].e[j].pstart.y));
         if (j!=0) {
            poly[i].e[j-1].pend.x = poly[i].e[j].pstart.x;
            poly[i].e[j-1].pend.y = poly[i].e[j].pstart.y;
         }
      }
      poly[i].e[j-1].pend.x = poly[i].e[0].pstart.x;
      poly[i].e[j-1].pend.y = poly[i].e[0].pstart.y;

      /* now calculate slopes */
      for (j=0;j<poly[i].edgecount;j++) {
         poly[i].e[j].slope = slope(poly[i].e[j].pend, poly[i].e[j].pstart);
      }
   }
}

/* Does the given point lie on the given edge? */
int point_on_edge(point_t pt, edge_t e) {
   if (points_equal(e.pstart, pt) || points_equal(e.pend, pt)) return 1;
   if (e.slope > (slope(e.pstart, pt) + MINDIFF) ||
       e.slope < (slope(e.pstart, pt) - MINDIFF)) return 0;
   if (e.slope == VERTICAL) {
      if (( pt.y >= e.pstart.y && pt.y <= e.pend.y ) ||
          ( pt.y >= e.pend.y   && pt.y <= e.pstart.y)) {
         return 1;
      }
      return 0;
   }
   if (( pt.x >= e.pstart.x && pt.x <= e.pend.x ) ||
       ( pt.x >= e.pend.x   && pt.x <= e.pstart.x)) {
      return 1;
   }
   return 0;
}

/* Finds the intersection between e1 and e2.
 * If we have to extend e1 to get an intersection, then we will.
 */
edges_intersect(edge_t e1, edge_t e2, point_t *intersection, int *extended) {
   double b1, b2;

   *extended = 0;

   /* parallel case */
   if(e1.slope == e2.slope) {
      /* parallel and separate??? */
      if (slope(e1.pstart,e2.pstart) != e1.slope) return 0;
      /* share same line */
      if (point_on_edge(e1.pstart,e2)) {
         *intersection = e1.pstart;
         return 1;
      }
      if (point_on_edge(e1.pend,e2)) {
         *intersection = e1.pend;
         return 1;
      }
      /* must extend */
      *extended = 1;
      *intersection = e2.pstart;
      return 1;
   }

   /* non-parallel, thank god! */
   /* remember the line formula: y=mx+b */
   if (e1.slope == VERTICAL || e2.slope == VERTICAL) {
      edge_t etemp;
      if (e2.slope == VERTICAL) {
         b2 = e1.pstart.y - ( e1.slope * e1.pstart.x );
         intersection->x=e2.pstart.x;
         intersection->y=e1.slope*intersection->x+b2; 
      } else {
         b2 = e2.pstart.y - ( e2.slope * e2.pstart.x );
         intersection->x=e1.pstart.x;
         intersection->y=e2.slope*intersection->x+b2; 
      }
   } else {
      b1 = e1.pstart.y - ( e1.slope * e1.pstart.x );
      b2 = e2.pstart.y - ( e2.slope * e2.pstart.x );
      intersection->x=(b2-b1)/(e1.slope-e2.slope);
      intersection->y=e2.slope*intersection->x+b2; 
   }

   /* Ok, so we have an intersection point.  Does it really
    * lie on the target edge?
    */
   if (!point_on_edge(*intersection,e2)) return 0;

   /* Ok, so it does lie on the target edge.  Do we have to
    * extend our edge to make it hit?
    */
   if (!point_on_edge(*intersection,e1)) *extended=1;

   return 1; 
}

/* There are five classes of polygon intersections to consider:
 *   1) shared endpoints
 *   2) endpoint touches an edge
 *   3) shared edges
 *   4) crossing edges (non-endpoint)
 *   5) containment (one polygon inside the other)
 */
int polys_intersect(poly_t p1, poly_t p2) {
   int i, j, crossings;

   /* check for shared endpoints */
   for (i=0; i<p1.edgecount; i++) {
      for (j=0; j<p2.edgecount; j++) {
         if (p1.e[i].pstart.x == p2.e[j].pstart.x &&
             p1.e[i].pstart.y == p2.e[j].pstart.y) {
            DEBUG2("Edges %d and %d share an endpoint\n",i+1,j+1)
            return 1;
         }
      }
   }

   /* check for endpoint touches an edge */
   /* For this check we need for the endpoint's x and y
    * values to be between the x and y values of the edge
    * AND we need the slope from our endpoint to one of the
    * edge's endpoints to be the same as the edge's slope.
    */
   for (i=0; i<p1.edgecount; i++) {
      point_t mypoint=p1.e[i].pstart;
      for (j=0; j<p2.edgecount; j++) {
         edge_t myedge=p2.e[j];
         if ( (mypoint.x > myedge.pstart.x && mypoint.x > myedge.pend.x) ||
              (mypoint.x < myedge.pstart.x && mypoint.x < myedge.pend.x) ||
              (mypoint.y > myedge.pstart.y && mypoint.y > myedge.pend.y) ||
              (mypoint.y < myedge.pstart.y && mypoint.y < myedge.pend.y)) {
            continue;
         }
         if (myedge.slope == slope(myedge.pend,mypoint)) {
            DEBUG2("Edge %d touches edge %d with an endpoint\n",i+1,j+1)
            return 1;
         }
      }         
   }

   /* check for shared edges */
   /* Luckily, my implementation for the previous case
    * also takes care of this one, so do nothing... 
    */

   /* check for crossing edges */
   /* check for containment */
   /* We'll do both of these at the same time. */
   
   for (i=0; i<p1.edgecount; i++) {
      int outside = 0;
      int edge_tried[MAXEDGES];
      memset(&edge_tried[0],0,sizeof(int)*MAXEDGES);
      crossings=0;
      for (j=0; j<p2.edgecount; j++) {
         if (edge_tried[j]) { continue; }
         edge_tried[j]=1;
         point_t intersection;
         int extended;
         if (edges_intersect(p1.e[i], p2.e[j], &intersection, &extended)) {
            edge_t e1, e2, enew;
            int delta;
            /* edges intersect normally? */
            if (!extended) {
               DEBUG4("Edges %d and %d intersect at (%lf,%lf)",i+1,j+1,intersection.x,intersection.y)
               return 1;
            }
            /* edges intersect only when p1.e[i] is extended */
            /* This is where we figure out if we're completely contained. */
            /* We do this by extending each edge of the original polygon to
             * the edge of the 'board', where we know the line will be outside
             * of the other polygon we're being compared to.  Following the
             * line back to its originating edge, we examine intersection 
             * points where we hit the other polygon.  If we hit in the middle
             * of an edge, we've just crossed into or out of the other polygon's
             * interior. If we hit at the intersection of two of the other
             * polygon's edges then we have to determine if both edges lie on
             * the same side of our extended edge or not.  If so, we haven't
             * changed state (from outside to inside, or vice versa), otherwise
             * we have.  
             * Note that this works in both directions. For my purposes, I'll choose
             * left/down (that is, intersections with smaller x values, or smaller
             * y values for vertical intersections).
             */
            /* First, let's see if this edge is parallel to us.  If so, ignore it. */
            if (p1.e[i].slope == p2.e[j].slope) {
               continue;
            }
            /* Similarly, if it is to the right or (for the vertical case) above us,
             * also ignore it.
             */
            if (p1.e[i].slope==VERTICAL) {
               if (intersection.y > p1.e[i].pstart.y) continue;
            }
            else {
               if (intersection.x > p1.e[i].pstart.x) continue;
            }
            /* Ok, this crossing counts */
            ++crossings;
            /* Then, check to see if we hit at a midpoint */
            if (!points_equal(intersection, p2.e[j].pstart) && 
                !points_equal(intersection, p2.e[j].pend)) {
               continue; /* yep - midpoint */
            }
            /* We hit an endpoint, now we have to look at the other edge sharing it */
            /* If that other edge is parallel to us, then skip it and keep looking */
            e1=p2.e[j];
            delta=0;
            do {
               if (intersection.x == e1.pstart.x) {
                  --delta;
               } else {
                  ++delta;
               }
               e2=   p2.e[(j+p2.edgecount+delta)%p2.edgecount];
               edge_tried[(j+p2.edgecount+delta)%p2.edgecount] = 1;
            } while (e2.slope == p1.e[i].slope);

            /* Now we have to determine if both of these edges are on the same side of
             * our extended line.
             */
            if (points_equal(intersection, e1.pstart)) { 
                enew.pstart=e2.pstart;
                enew.pend=e1.pend;
            } else {
                enew.pstart=e1.pstart;
                enew.pend=e2.pend;
            }
            enew.slope=slope(enew.pstart,enew.pend);
            /* Ok, so we have this new bogus edge defined that connects the other
             * endpoints of the two edges whose endpoints we're hitting.
             * If my original extended segment intersects this new edge directly,
             * then I'm crossing in/out of the interior of the other polygon.
             * Otherwise, I'm not.
             */
            if (!edges_intersect(p1.e[i], enew, &intersection, &extended)) {
               ++crossings; /* nullify my earlier increment */
            }
         }
/*
         if (p1.e[i].pstart.x == p2.e[j].pstart.x &&
             p1.e[i].pstart.y == p2.e[j].pstart.y) {
            return 1;
         }
*/
      }
      if ((crossings%2) == 1) {
         DEBUG2("Edge %d had %d crossings with poly",i+1,crossings)
         return 1;
      }
   }

   return 0;
}

int main (int argc, char *argv[]) {

   int datasets, i, j, k, p1, p2, found_collision;

   infile=stdin;
   if (argc>1) infile=fopen(argv[1],"r");

   fscanf(infile,"%d",&datasets);

   for (i=0; i<datasets; i++) {

      /* read in this data set */
      readds();

      /* print the header */
      printf("Data Set #%d\n",i+1);

      /* test the intersection of each pair of polys */
      found_collision = 0;
      for (j = 0; j < numpolys; j++) {
         for (k = j + 1; k < numpolys; k++) {
            if (polys_intersect(poly[j],poly[k]) || 
                polys_intersect(poly[k],poly[j])) {
               found_collision = 1;
               printf("%d %d\n",j+1,k+1);
            }
         }
      }

      if (!found_collision) printf("no collisions\n");

   }
}