CF568D.Sign Posts

One Khanate had a lot of roads and very little wood. Riding along the roads was inconvenient, because the roads did not have road signs indicating the direction to important cities.

The Han decided that it's time to fix the issue, and ordered to put signs on every road. The Minister of Transport has to do that, but he has only k signs. Help the minister to solve his problem, otherwise the poor guy can lose not only his position, but also his head.

More formally, every road in the Khanate is a line on the Oxy plane, given by an equation of the form Ax + By + C = 0 (A and B are not equal to 0 at the same time). You are required to determine whether you can put signs in at most k points so that each road had at least one sign installed.

一个汗国拥有大量道路，但木材却极为匮乏。沿道路骑行十分不便，因为道路上没有指示通往重要城市方向的路标。

可汗决定是时候解决这一问题了，于是下令在每条道路上设置路标。交通大臣必须完成这项任务，但他仅有 $k$ 个路标。请帮助这位大臣解决难题，否则这位可怜的官员不仅会丢掉官职，甚至可能丢掉脑袋。

更严格地讲，汗国中的每条道路都是 $Oxy$ 平面上的一条直线，其方程形式为 $Ax + By + C = 0$（其中 $A$ 和 $B$ 不同时为 $0$）。你的任务是判断：能否在至多 $k$ 个点上设置路标，使得每条道路至少经过其中一个路标点。

The input starts with two positive integers n, k (1 ≤ n ≤ 105, 1 ≤ k ≤ 5)

Next n lines contain three integers each, A__i, B__i, C__i, the coefficients of the equation that determines the road (|A__i|, |B__i|, |C__i| ≤ 105, _A__i_2 + _B__i_2 ≠ 0).

It is guaranteed that no two roads coincide.

输入的第一行包含两个正整数 $n$、$k$（$1 \leq n \leq 10^5$，$1 \leq k \leq 5$）。

接下来的 $n$ 行每行包含三个整数 $A_i$、$B_i$、$C_i$，它们是确定道路的直线方程的系数（满足 $|A_i|, |B_i|, |C_i| \leq 10^5$，且 $A_i^2 + B_i^2 \neq 0$）。

保证任意两条道路不重合。

If there is no solution, print "NO" in the single line (without the quotes).

Otherwise, print in the first line "YES" (without the quotes).

In the second line print a single number m (m ≤ k) — the number of used signs. In the next m lines print the descriptions of their locations.

Description of a location of one sign is two integers v, u. If u and v are two distinct integers between 1 and n, we assume that sign is at the point of intersection of roads number v and u. If u =  - 1, and v is an integer between 1 and n, then the sign is on the road number v in the point not lying on any other road. In any other case the description of a sign will be assumed invalid and your answer will be considered incorrect. In case if v = u, or if v and u are the numbers of two non-intersecting roads, your answer will also be considered incorrect.

The roads are numbered starting from 1 in the order in which they follow in the input.

如果无解，在单独一行中输出 “NO”（不带引号）。

否则，在第一行输出 “YES”（不带引号）。

在第二行输出一个整数 $ m $（满足 $ m \leq k $）—— 表示所用标识牌的数量。接下来的 $ m $ 行中，每行输出一个标识牌位置的描述。

一个标识牌位置的描述由两个整数 $ v $、$ u $ 组成：

• 若 $ u $ 和 $ v $ 是 $ 1 $ 到 $ n $ 之间的两个不同整数，则表示该标识牌位于编号为 $ v $ 与编号为 $ u $ 的两条道路的交点处；
• 若 $ u = -1 $，且 $ v $ 是 $ 1 $ 到 $ n $ 之间的整数，则表示该标识牌位于编号为 $ v $ 的道路上，且该位置不与其他任何道路相交；
• 其他所有情况均视为标识牌位置描述无效，你的答案将被判为错误。
  此外，若 $ v = u $，或 $ v $ 与 $ u $ 对应两条不相交的道路，你的答案也将被判为错误。

道路编号从 1 开始，按输入中出现的顺序依次编号。

Note that you do not have to minimize m, but it shouldn't be more than k.

In the first test all three roads intersect at point (0,0).

In the second test all three roads form a triangle and there is no way to place one sign so that it would stand on all three roads at once.

注意，你不需要最小化 $m$，但 $m$ 不应超过 $k$。

在第一个测试用例中，三条道路均相交于点 $(0,0)$。

在第二个测试用例中，三条道路构成一个三角形，因此无法放置一个路标使其同时位于这三条道路上。