Знайди Скарб
Чотириста років тому група піратів заховала скарб на одному з островів архіпелагу, що складається з багатьох дуже маленьких островів. На жаль, ці пірати були не найкращими навігаторами та картографами. Тому, замість карти, вони створили малюнки видів з вершини гори на острові зі скарбом. Кожен малюнок показує два або більше інших островів архіпелагу, які можна побачити з острова зі скарбом, розташованих зліва направо. Види також містять багато туману, тому на малюнках можуть бути відсутні деякі острови, які повинні були бути в полі зору між островами, що з'являються на малюнку. Наприклад, на Рисунку 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. Потенційні острови зі скарбом — Руммет, Алет і Шнапсум.