← 返回题目列表

Codeforces · 568/D

D. 路标

中文机器翻译题面 查看原题

一个汗国有很多道路,但木材却很少。沿路骑行很不方便,因为路上没有通往重要城市的路标。

汉决定是时候解决这个问题了,并下令在每条道路上放置标志。交通部长必须这样做,但他只有 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)。

在第二次测试中,所有三条道路形成一个三角形,并且无法放置一个标志使其同时站在所有三条道路上。