시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
---|---|---|---|---|---|

1 초 | 128 MB | 0 | 0 | 0 | 0.000% |

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 identified easily thanks to the unique towers on top of each island.

Figure 2: Map of a hypothetical archipelago, and some views from Rummet as the pirates could have drawn them.

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:

- One line with an integer n, satisfying 1 ≤ n ≤ 125,000: the number of islands in the archipelago.
- n lines, each with two integers x
_{i}and y_{i}, satisfying 0 < x_{i}< 2^{29}and 0 < y_{i}< 2^{29}: these are the coordinates of the tower T_{i}on each island. - One line with an integer k: the number of test cases for this archipelago. Each test case has the 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 T
_{l}is drawn to the left of tower T_{r}.

In any archipelago, no two towers have the same x-coordinate, no two towers have the same y-coordinate, and no three towers lie on a line.

For every test case in the input, the output should contain:

- 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.
- One line containing the number 0.

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

The following input describes one archipelago with one test case, namely the information corresponding to the map and the views shown in Figure 2. The potential treasure islands are Rummet, Alet, and Schnahpsum.