eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Наводнение

Наводнение

Лимит времени 2 секунды
Лимит использования памяти 64 MiB

В 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 строк должны содержать номера стен, которые останутся целыми, по одному номеру в каждой строке. Номера стен можно выводить в произвольном порядке.

Пример

Входные данные #1
15
1 1
8 1
4 2
7 2
2 3
4 3
6 3
2 5
4 5
6 5
4 6
7 6
1 8
4 8
8 8
17
1 2
2 15
15 14
14 13
13 1
14 11
11 12
12 4
4 3
3 6
6 5
5 8
8 9
9 11
9 10
10 7
7 6
Выходные данные #1
4
6
15
16
17
Источник IOI-2007, День 1