Решите на Python или C++

Школьник Сережа очень любит играть в популярную игру — Doka 2. Его радости не
было предела, когда он узнал, что в игре вышло обновление, и был добавлен новый герой — Пудж.
Пудж сразу стал любимым героем Сережи. И это неспроста, ведь отличительной особенностью данного героя является возможность бросить крюк в указанном направлении.

Правила в данной игре следующие:
ˆ крюк летит строго по прямой в определенном направлении;
ˆ крюк летит до тех пор, пока не попадает в первого героя, встретившегося на его пути;
ˆ герой, в которого попал крюк, погибает;
ˆ если Пудж погиб до того, как совершил все свои ходы, считается, что несовершенные
ходы пропускаются;
ˆ крюк, попавший в героя, сразу возвращается его владельцу;
ˆ eсли на пути крюка не встретилось ни одного героя, то считается, что крюк теряется;
ˆ Пудж, потерявший свой крюк, не может бросить его повторно;
ˆ если цель, в котороую бросили крюк, погибла до этого броска, то считается, что крюк полетит в направлении последнего положения этой цели.

В очередной игре, найденной Сережей, оказалось 𝑁 Пуджей. Все герои находятся в разных точках (𝑥𝑖 , 𝑦𝑖) на карте. Перед началом игры определяется последовательность ходов,
в которой Пуджи совершают броски своих крюков.
Сережа плохо разобрался в механике нового героя, да и по геометрии у него уверенная
тройка с минусом. Помогите школьнику определить, кто из Пуджей останется в живых в конце игры.

Формат входных данных

Первая строка входного файла содержит два целых числа 𝑁, 𝑀 — количество Пуджей и количество ходов (2 ⩽ 𝑁 ⩽ 6000, 0 ⩽ 𝑀 ⩽ 105 ). Далее следует 𝑁 строк, 𝑖-я строка содержит два целых числа 𝑥𝑖 , 𝑦𝑖 — координаты 𝑖-го Пуджа (−109 ⩽ 𝑥𝑖 , 𝑦𝑖 ⩽ 109 ).
Затем следует 𝑀 строк, описывающих последовательность ходов. 𝑖-я строка содержит
два целых числа 𝑘𝑖 и 𝑡𝑖 — номер Пуджа, кинувшего крюк, и номер Пуджа, в направлении которого этот бросок производится (1 ⩽ 𝑘𝑖 , 𝑡𝑖 ⩽ 𝑁, 𝑘𝑖 ̸= 𝑡𝑖). Пуджи номеруются с единицы в том порядке, в котором задавались их координаты.

Формат выходных данных

В первую строку выходного файл необходимо вывести одно число 𝐿 — количество Пуджей
оставшихся в живых в конце игры.
В следующей строке должно быть записано 𝐿 чисел — номера Пуджей, оставшихся в
живых.

Примеры
input.txt output.txt
3 3 2
0 0 1 3
1 3
3 1
1 2
3 2
3 1

2 0 2
1 1 1 2
3 3

3 2 1
0 0 1
1 1
2 1
1 2
1 3