eolymp
bolt
Try our new interface for solving problems
Məsələlər

Find the Treasure

Find the Treasure

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 32 MiB

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 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. 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.

Figure 1. Map of 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?

Giriş verilənləri

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 1n125,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 hasthe following format:

    • One line with an integer m, satisfying 0m10,000: the number of pairs of islands that appear in the pirates' drawings.

    • m lines, each with two integers l and r such that 1ln, 1rn, lr, meaning that the tower T_l is drawn to the left of tower T_r.

Ouput

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

  • One line with an integer i (1in), 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.

Example

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

Nümunə

Giriş verilənləri #1
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
Çıxış verilənləri #1
6
7
8
0
Mənbə ICPC BAPC 2011 Finals