Buggy Satellite

Time limit1sMemory limit128 MB

Summary
Each test case gives cities with coordinates and a list of regions; report which region is the outer one.
Level

Medium4 of 10

Topics
Geometry, Implementation
Solved
No attempts yet

Problem

Discovery Co., Ltd. builds a satellite equipped with a new kind of intelligent camera. The camera runs special software that detects cities and roads in an image, and it can also detect every region — a connected part of the surface bounded by a series of connected roads and containing no other region inside it. Using this technology, the satellite compresses each picture before transmitting it: the compressed form of a picture is simply the list of city locations together with the list of regions.

The satellite was launched before the software was fully tested, so after a while the team began receiving buggy pictures that contain one extra region: the outer region. The outer region is the region of the plane that encloses every other region, and therefore has infinite area.

Every image that is received has the following properties:

  1. Every city is connected by roads to at least two other cities.
  2. There is a path between every pair of cities.
  3. There is at most one road between any pair of cities.
  4. Roads never cross one another except at cities.

The figure above shows one received image.

Write a program that reads a buggy image and reports which region is the outer region.

Input

The first line contains a single integer NN (1≤N≤201 \le N \le 20), the number of test cases. The test cases follow one after another with no blank lines between them.

Each test case is given as follows:

  • A line with the number of cities CC (1≤C≤501 \le C \le 50).
  • Then CC lines, each containing two integers xx and yy: the location of a city. Cities are numbered 11 through CC in the order they are listed.
  • A line with the number of regions FF (1≤F≤501 \le F \le 50).
  • Then FF lines, each describing one region: an integer kk (the number of cities on that region's boundary) followed by the kk city numbers, listed in clockwise or counterclockwise order.

Output

For each test case, print a single line containing the number of the region that is the outer region. Regions are numbered 11 through FF in the order they are given in the input. Print the answers in the same order as the test cases, with no blank lines between them.

Examples5

  1. Example 1

    Input
    1
5
2 6
4 4
4 7
8 6
4 10
3
4 1 2 4 3
4 1 3 4 5
4 1 2 4 5
    Expected output
    3

  2. Example 2

    Input
    1
4
0 0
4 0
4 4
0 4
3
3 1 2 3
3 1 3 4
4 1 2 3 4
    Expected output
    3

  3. Example 3

    Input
    1
4
0 0
4 0
4 4
0 4
3
4 1 2 3 4
3 1 2 3
3 1 3 4
    Expected output
    1

  4. Example 4

    Input
    1
4
0 0
4 0
4 4
0 4
3
3 1 2 3
4 1 2 3 4
3 1 3 4
    Expected output
    2

  5. Example 5

    Input
    2
5
2 6
4 4
4 7
8 6
4 10
3
4 1 2 4 3
4 1 3 4 5
4 1 2 4 5
4
0 0
4 0
4 4
0 4
3
3 1 2 3
3 1 3 4
4 1 2 3 4
    Expected output
    3
3