CF568D Sign Posts

有一个“汗国”拥有许多道路，却几乎没有木材。因为道路缺乏指示重要城市方向的路标，出行变得十分不便。 可汗决定要解决这个问题，下令在每条道路上都设立一个路标。交通大臣要负责落实这个命令，但他只有 $k$ 个路标。请帮助大臣解决这个难题，否则他可能不仅丢掉职位，还会丢掉性命。 更正式地，每条道路在 $Oxy$ 平面上表示为 $Ax+By+C=0$ 形式的一条直线（$A$ 和 $B$ 不会同时为 $0$）。你需要判断，是否能够在不超过 $k$ 个点上放置路标，使得每条道路上都至少有一个路标被安置。

输入的第一行为两个正整数 $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$）。 保证没有两条道路重合。

如果无解，输出一行 “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$ 到 $n$。

请注意，你无需最小化 $m$，但它不能超过 $k$。 在第一个测试样例中，三条道路都在 $(0,0)$ 处相交。 在第二个测试样例中，三条道路构成了一个三角形，无法仅用一个路标同时覆盖三条道路。 由 ChatGPT 5 翻译