Find the Treasure

Four hundred years ago, a group of pirates hid a treasure on an island in an archipelago that consists of many very small islands. Unfortunately, these pirates were particularly bad navigators and cartographers. Therefore, instead of a map, they made drawings of views from the top of the mountain on the treasure island. Each view shows two or more other islands of the archipelago that can be seen from the treasure island, ordered from left to right. The views also contain lots of fog, so the drawings may fail to show some islands that must have been in the field of view between the islands that appear in the drawing. For example, in Figure 2 below, if the treasure is hidden on Rummet, then the pirates could have drawn a view showing (from left to right) Wisket, Ginnet and Vinnet, or a view showing (from left to right) Liquorel and Cidrel. The pirates are known to have had acute vision, with a viewing angle of 180 degrees, but bad drawing skills: the distances between Wisket, Ginnet and Vinnet in their drawing are meaningless, and Liquorel may be drawn far to the left of Cidrel while in the actual view from Rummet, Liquorel must have been only slightly to the left of Cidrel, even obscuring part of it. Fortunately, all islands in the drawings can be identied easily thanks to the unique towers on top of each island.

Now, four hundred years later, you have got the pirates' drawings and an excellent, accurate map of the archipelago, showing all islands. On which island is the treasure hidden?

The first line of the input contains a single number: the number of archipelagos to follow. Each archipelago has the following format:
1.One line with an integer n, satisfying 1 <= n <= 125,000: the number of islands in the archipelago.
2.n lines, each with two integers xi and yi, satisfying 0 < xi < 2^29 and 0 < yi < 2^29: these are the coordinates of the tower Ti on each island.
3.One line with an integer k: the number of test cases for this archipelago. Each test case hasthe following format:
----One line with an integer m, satisfying 0 <= m <= 10,000: the number of pairs of islands that appear in the pirates' drawings.
----m lines, each with two integers l and r such that 1 <= l <= n, 1 <= r <= n, l != r, meaning that the tower Tl is drawn to the left of tower Tr.

For every test case in the input, the output should contain:
1.One line with an integer i (1 <= i <= n), identifying the i-th island in the archipelago, for each island that could be the treasure island. These lines need to be in increasing order.
2.One line containing the number 0.
The following input describes one archipelago with one test case, namely the information corre-sponding to the map and the views shown in Figure 2. The potential treasure islands are Rummet, Alet, and Schnahpsum.

1
9
28 34
32 30
12 29
27 22
42 23
18 18
5 14
26 12
34 5
1
4
1 2
1 9
2 9
4 5

6
7
8
0

BAPC 2011