一个汗国有很多道路,但木材却很少。沿路骑行很不方便,因为路上没有通往重要城市的路标。
汉决定是时候解决这个问题了,并下令在每条道路上放置标志。交通部长必须这样做,但他只有 k 个标志。帮助部长解决他的问题,否则这个可怜的家伙不仅会失去他的职位,还会失去他的头。
更正式地说,汗国的每条道路都是 Oxy 平面上的一条线,由 Ax + By + C = 0 形式的方程给出(A 和 B 不同时等于 0)。您需要确定是否可以在最多 k 个点上放置标志,以便每条道路至少安装一个标志。
输入
输入以两个正整数 n, k 开头 (1 ≤ n ≤ 105, 1 ≤ k ≤ 5)
接下来的 n 行每行包含三个整数,Ai、Bi、Ci,即确定道路的方程的系数(|Ai|、|Bi|、|Ci| ≤ 105、Ai2 + Bi2 ≠ 0)。
保证没有两条道路重合。
输出
如果没有解决方案,请在单行中打印“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 开始编号。
示例
输入 #1
3 1 1 0 0 0 -1 0 7 -93 0
输出 #1
YES 1 1 2
输入 #2
3 1 1 0 0 0 1 0 1 1 3
输出 #2
NO
输入 #3
2 3 3 4 5 5 6 7
输出 #3
YES 2 1 -1 2 -1
注意
请注意,您不必最小化 m,但它不应大于 k。
在第一个测试中,所有三条道路都相交于点 (0,0)。
在第二次测试中,所有三条道路形成一个三角形,并且无法放置一个标志使其同时站在所有三条道路上。