Find the Treasure#3125
Four hundred years ago, a group of pirates hid a treasure on an island in an archipelago consisting of many very small islands. Unfortunately, these pirates were not skilled navigators or cartographers. Therefore, instead of a map, they drew 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 a lot of fog, so some islands that must have been in the field of view between the islands in the drawing may not be depicted. For example, in Figure 1 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. It is known that the pirates had acute vision with a viewing angle of 180 degrees, but poor 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 reality from Rummet, Liquorel should be only slightly to the left of Cidrel, even partially overlapping it. Fortunately, all islands in the drawings can be easily identified thanks to the unique towers atop each island.
Figure 1. Map of the hypothetical archipelago and some views from Rummet as the pirates might have drawn them.
Now, four hundred years later, you have the pirates' drawings and an accurate map of the archipelago showing all islands. On which island is the treasure hidden?
The first line of input contains a single number: the number of archipelagos to follow. Each archipelago has the following format:
One line with an integer , 1 \leq n \leq 125\,000: the number of islands in the archipelago.
lines, each with two integers x_i and y_i, 0 < x_i < 2^{29} and 0 < y_i < 2^{29}: the coordinates of tower T_i on each island.
One line with an integer : the number of test cases for this archipelago. Each test case has the following format:
One line with an integer , 0 \leq m \leq 10\,000: the number of pairs of islands appearing in the pirates' drawings.
lines, each with two integers and such that 1 \leq l \leq n, 1 \leq r \leq n, l \neq r, meaning that tower T_l is drawn to the left of tower T_r.
For each test case in the input, the output should contain:
For every possible treasure island, one line with an integer (1 \leq i \leq n), identifying the -th island in the archipelago. These lines should be in increasing order.
One line containing the number .
Example
The following input describes one archipelago with one test case, namely the information corresponding to the map and the views shown in Figure 1. The possible treasure islands are Rummet, Alet, and Schnahpsum.
Example 1