Наводнение
В 1964 году катастрофическое наводнение потрясло Загреб. Много строений было уничтожено водой, ударившей в их стены. В этой задаче вам будет задана упрощенная модель города перед наводнением, и вы должны определить, какие из стін останутся целыми после наводнения.
Модель состоит из N точек на координатной плоскости и W стен. Каждая стена соединяет пару точек и не проходит через другие точки. Модель также удовлетворяет следующим свойствам:
- никакие две стены не пересекаются и не накладываются на другую, за исключением того, что они могут иметь общие концы;
- каждая стена является параллельной или к горизонтальной, или к вертикальной координатной оси.
Вначале вся координатная плоскость является сухой. В момент времени ноль вода мгновенно затапливает внешнее пространство (пространство, не ограниченное стенами). Ровно через час каждая стена, у которой с одной стороны - вода, а с другой стороны - воздух, рушиться под давлением воды. После этого вода мгновенно затапливает пространство, переставшее быть ограниченным целыми стенами. В результате этого могут появиться новые стены, у которых с одной стороны вода, а с другой стороны - воздух. Еще через час эти стены также рушатся, и вода попадает в новое пространство. Так продолжается до тех пор, пока вода не затопит всю территорию.
Пример процесса разрушения показан на рисунке (интервал между состояниями - один час).
Задание
Напишите программу, которая за заданными координатами N точек и описанием W стен, соединяющих эти точки, определяет, какие стены останутся целыми после наводнения.
Входные данные
Первая строка входных данных содержит целое число N (2 ≤ N ≤ 100 000), количество точек на плоскости. Каждая из последующих N строк содержит по два целых числа X и Y (каждое от 0 до 1 000 000 включительно) - координаты точки. Точки пронумерованы от 1 до N в том порядке, в котором они заданы. Никакие две точки не совпадают.
Следующая строка содержит целое число W (1 ≤ W ≤ 2N) - количество стен.
Каждая из последующих W строк содержит по два разных целых числа A и B (1 ≤ A, B ≤ N), которые означают, что перед наводнением была стена, соединявшая точки A и B. Стены пронумерованы от 1 до W в том порядке, в котором они заданы.
Выходные данные
Первая строка выходных данных должна содержать целое число K - количество стен, которые останутся целыми после наводнения.
Последующие K строк должны содержать номера стен, которые останутся целыми, по одному номеру в каждой строке. Номера стен можно выводить в произвольном порядке.