В одном ханстве было очень много дорог и очень мало дерева. Ездить по дорогам было неудобно, ведь на дорогах не было столбиков с указанием направления на важные города.
Хан решил, что это пора исправить, и приказал поставить столбики на каждую дорогу. Министр транспорта был бы и рад, только вот столбиков у него всего k. Помогите министру решить его проблему, иначе бедолага может потерять не только должность, но и голову.
Более формально: каждая дорога в ханстве представляет собой прямую на плоскости Oxy, заданную уравнением вида Ax + By + C = 0 (A и B не равны нулю одновременно). Требуется определить, можно ли поставить столбики в не более, чем k точек так, чтобы на каждой дороге оказался установлен хотя бы один столбик.
Выходные данные
Если решения не существует, выведите "NO" в единственной строке (без кавычек).
Иначе в первой строке выведите "YES" (без кавычек).
Во второй строке выведите единственное число m (m ≤ k) — количество использованных столбов. Затем в m строках выведите описания положений столбиков.
Описание положения одного столбика — это два целых числа v, u. Если u и v — два различных целых числа от 1 до n, то считается, что столбик стоит в точке пересечения дорог с номерами v и u. Если u = - 1, а v — целое число от 1 до n, то столбик стоит на дороге номер v, причем не в точке пересечения с какой-либо другой дорогой. В любом ином случае описание столбика будет считаться некорректным, а ваш ответ — неправильным. В том числе, если v = u, либо если v и u — номера двух непересекающихся дорог, ваш ответ также будет признан неправильным.
Дороги нумеруются с 1 в том порядке, в котором они даны во входных данных.
Примечание
Обратите внимание, вам не требуется минимизировать m, но оно должно быть не больше k.
В первом тесте все три дороги пересекаются в точке (0,0).
Во втором тесте три дороги образуют треугольник, и никак нельзя поставить один столб, чтобы он стоял на всех трёх дорогах сразу.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 1
1 0 0
0 -1 0
7 -93 0
|
YES
1
1 2
|
|
2
|
3 1
1 0 0
0 1 0
1 1 3
|
NO
|
|
3
|
2 3
3 4 5
5 6 7
|
YES
2
1 -1
2 -1
|