Вася — хороший парень. Но у него есть плохая привычка — он курит. Всё то время, сколько Петя дружит с Васей, он пытается отучить его от этого. Но ему это так и не удалось, потому что Вася не хочет бросать курить.
Недавно Петя придумал способ, как отучить своего друга от курения. Вася — неряха, поэтому его сигареты не лежат в пачке, а разбросаны по огромному столу. Петя хочет брать несколько сигарет в день незаметно для Васи. Вася не заметит пропажи сигарет, если в день будет пропадать не более одной сигареты. Кроме того, Петя должен брать только ту сигарету, которая пересекается с какой-нибудь другой сигаретой на столе. Помогите Пете узнать, сможет ли он начать реализацию своего плана.
Исходные данные
Сигарета представляет собой отрезок ненулевой длины. В первой строке записано число N (1 ≤ N ≤ 50000) — количество сигарет на Васином столе. Следующие N строк содержат описания сигарет: (i + 1)-я строка содержит координаты концов i-й сигареты — целые числа x1, y1, x2, y2 (–10000 ≤ x1, y1, x2, y2 ≤ 10000).
Результат
В первой строке выведите слово «YES», если Пете удастся начать реализацию своего плана. Вторая строка должна содержать
числа i и j: i — номер сигареты, которую должен взять Петя, j — номер сигареты, с которой она пересекается.
Если Петя не сможет взять ни одной сигареты, выведите «NO».
Примеры
исходные данные | результат |
---|
2
0 0 2 2
0 2 2 0
| YES
1 2
|
2
0 0 0 5
5 0 5 10
| NO
|
Автор задачи: Илья Шишков
Источник задачи: Ural SU and Orel STU Contest. Petrozavodsk Summer Session, August 2006