Задача 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