Задача Billiard
У Петрика і Василька вдома є
великий стіл, поверхня якого має форму еліпса. Хлопці іноді граються, катаючи
по його поверхні маленькі металеві кульки. Кульки завжди запускають з
деяких «улюблених» точок на краю столу, намагаючись влучити у інші «улюблені»
точки, теж розміщені на краю столу. Всього таких «улюблених» точок N
(7≤N≤200 000), і кожна з них може бути стартом або фінішем.
Одного разу до хлопців прийшли друзі (загальна кількість дітей
виявилася рівною M, де 2≤M≤10 000, і всі
вирішили пограти в дану гру. Кожен вибрав для своєї кульки «трасу», кінці
якої розміщені у двох (гарантовано різних) «улюблених» точках.
Напишіть програму, яка з’ясує, чи вдалося гравцям обрати «траси»
так, щоб вони не перетиналися (ні всередині столу, ні в «улюблених»
точках). Програма повинна або повідомляти, що вибрані «траси» справді не
мають перетинів, або знаходити будь-яку одну пару «трас», що
перетинаються (всередині столу або мають спільний край).
Технічні
умови
Програма Billiard читає з клавіатури спочатку
два числа: N (7≤N≤200 000) і M (2≤M≤10 000) — кількість «улюблених»
точок та кількість «трас»; далі M пар натуральних чисел — номери
тих «улюблених» точок, які є кінцями відповідної «траси». Нумерація «улюблених»
точок починається з 1 і відповідає порядку обходу навколо столу
за годинниковою стрілкою. Гарантовано, що всі «улюблені» точки лежать на
еліпсі–краю стола.
Програма має вивести на екран два числа через пропуск. Якщо
вибрані дітьми «траси» не перетинаються (і не мають спільних країв), це
мають бути два числа –1. Інакше треба вивести два натуральні
числа — номери будь-яких двох «трас», що перетинаються (або мають
спільний край). Нумерація «трас» задається порядком опису цих «трас» у
вхідних даних. Якщо можливі різні правильні відповіді, вивести будь-яку
одну з них.
Приклади
Введення
7 3 2 4 7 1 6 3
Виведення
1 3
Введення
100 2 1 17 42 64
Виведення
-1 -1