Найди сокровище
Четыреста лет назад группа пиратов спрятала сокровище на одном из островов архипелага, состоящего из множества крошечных островков. К сожалению, пираты оказались не самыми лучшими навигаторами и картографами. Вместо карты они оставили рисунки видов с вершины горы на острове с сокровищем. Каждый рисунок изображает два или более других островов архипелага, которые можно увидеть с острова с сокровищем, расположенные слева направо. Из-за густого тумана на рисунках могут отсутствовать некоторые острова, которые должны были быть видны между изображенными островами. Например, на Рисунке 1 ниже, если сокровище спрятано на Руммете, пираты могли нарисовать вид, показывающий (слева направо) Вискет, Джиннет и Виннет, или вид, показывающий (слева направо) Ликворель и Сидрель. Известно, что у пиратов было острое зрение с углом обзора 180 градусов, но плохие навыки рисования: расстояния между Вискетом, Джиннетом и Виннетом на их рисунке не имеют значения, и Ликворель может быть изображен далеко слева от Сидреля, хотя в реальности с Руммета Ликворель должен был быть лишь немного левее Сидреля, даже частично его заслоняя. К счастью, все острова на рисунках можно легко идентифицировать благодаря уникальным башням на вершине каждого острова.
Рисунок 1. Карта гипотетического архипелага и некоторые виды с Руммета, как их могли нарисовать пираты.
Теперь, четыреста лет спустя, у вас есть рисунки пиратов и точная карта архипелага, показывающая все острова. На каком острове спрятано сокровище?
Входные данные
Первая строка ввода содержит одно число: количество архипелагов, которые следуют. Каждый архипелаг представлен в следующем формате:
Одна строка с целым числом n, где 1 ≤ n ≤ 125,000: количество островов в архипелаге.
n строк, каждая с двумя целыми числами x_i и y_i, где 0 < x_i < 2^29 и 0 < y_i < 2^29: это координаты башни T_i на каждом острове.
Одна строка с целым числом k: количество тестовых случаев для этого архипелага. Каждый тестовый случай представлен в следующем формате:
Одна строка с целым числом m, где 0 ≤ m ≤ 10,000: количество пар островов, которые появляются на рисунках пиратов.
m строк, каждая с двумя целыми числами l и r такими, что 1 ≤ l ≤ n, 1 ≤ r ≤ n, l ≠ r, означающими, что башня T_l нарисована левее башни T_r.
Вывод
Для каждого тестового случая во входных данных вывод должен содержать:
Одна строка с целым числом i (1 ≤ i ≤ n), идентифицирующим i-й остров в архипелаге, для каждого острова, который может быть островом с сокровищем. Эти строки должны быть в порядке возрастания.
Одна строка, содержащая число 0.
Пример
Следующий ввод описывает один архипелаг с одним тестовым случаем, а именно информацию, соответствующую карте и видам, показанным на Рисунке 1. Потенциальные острова с сокровищем — это Руммет, Алет и Шнапсум.