Məsələlər
Наводнение
Наводнение
\includegraphics{https://static.e-olymp.com/content/76/769ba2d9d04b718bda0bd1d902300b4c423a69ee.jpg}
В 1964 году катастрофическое наводнение потрясло Загреб. Много строений было уничтожено водой, ударившей в их стены. В этой задаче вам будет задана упрощенная модель города перед наводнением, и вы должны определить, какие из стін останутся целыми после наводнения.
Модель состоит из \textbf{N} точек на координатной плоскости и \textbf{W} стен. Каждая стена соединяет пару точек и не проходит через другие точки. Модель также удовлетворяет следующим свойствам:
- никакие две стены не пересекаются и не накладываются на другую, за исключением того, что они могут иметь общие концы;
- каждая стена является параллельной или к горизонтальной, или к вертикальной координатной оси.
Вначале вся координатная плоскость является сухой. В момент времени ноль вода мгновенно затапливает внешнее пространство (пространство, не ограниченное стенами). Ровно через час каждая стена, у которой с одной стороны - вода, а с другой стороны - воздух, рушиться под давлением воды. После этого вода мгновенно затапливает пространство, переставшее быть ограниченным целыми стенами. В результате этого могут появиться новые стены, у которых с одной стороны вода, а с другой стороны - воздух. Еще через час эти стены также рушатся, и вода попадает в новое пространство. Так продолжается до тех пор, пока вода не затопит всю территорию.
Пример процесса разрушения показан на рисунке (интервал между состояниями - один час).
\textbf{Задание}
Напишите программу, которая за заданными координатами \textbf{N} точек и описанием \textbf{W} стен, соединяющих эти точки, определяет, какие стены останутся целыми после наводнения.
\InputFile
Первая строка входных данных содержит целое число \textbf{N} (\textbf{2 ≤ N ≤ 100 000}), количество точек на плоскости. Каждая из последующих \textbf{N} строк содержит по два целых числа \textbf{X} и \textbf{Y} (каждое от \textbf{0} до \textbf{1 000 000} включительно) - координаты точки. Точки пронумерованы от \textbf{1} до \textbf{N} в том порядке, в котором они заданы. Никакие две точки не совпадают.
Следующая строка содержит целое число \textbf{W} (\textbf{1 ≤ W ≤ 2N}) - количество стен.
Каждая из последующих \textbf{W} строк содержит по два разных целых числа \textbf{A} и \textbf{B} (\textbf{1 ≤ A}, \textbf{B ≤ N}), которые означают, что перед наводнением была стена, соединявшая точки \textbf{A} и \textbf{B}. Стены пронумерованы от \textbf{1} до \textbf{W} в том порядке, в котором они заданы.
\OutputFile
Первая строка выходных данных должна содержать целое число \textbf{K} - количество стен, которые останутся целыми после наводнения.
Последующие \textbf{K} строк должны содержать номера стен, которые останутся целыми, по одному номеру в каждой строке. Номера стен можно выводить в произвольном порядке.
Giriş verilənləri #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
Çıxış verilənləri #1
4 6 15 16 17