D. Замын тэмдэг

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Ханатэ хотод олон зам байдаг, харин цөөн тооны модтой. Зам дагаж явах нь төөрөх боломжтой учир нь энэ хотод чиглэл заасан замын тэмдэг байдаггүй.

Хан энэ асуудлыг засахаар шийдсэн бөгөөд бүх зам дээр замын тэмдэг тавь гэж тушаажээ. Тээврийн сайд үүнийг хийх ёстой боловч түүнд зөвхөн $k$ ширхэг тэмдэг байв. Сайдад энэ асуудлыг шийдвэрлэхэд туслаарай. Үгүй бол түүний ажлаас гадна толгойгоо ч алдаж магадгүй юм.

Ханатэд байгаа бүх зам нь $Oxy$ хавтгай дээр байгаа $Ax + By + C = 0$ тэгшитгэлтэй шулуунууд юм ($A$ болон $B$ нь зэрэг 0-тэй тэнцэхгүй). Зам болгонд нэг ширхэг замын тэмдэг байхаар хамгийн ихдээ $k$ ширхэг цэгийг олно уу.

Оролт

Эхний мөрөнд 2 ширхэг эерэг бүхэл тоо $n$, $k$ ($1 ≤ n ≤ 10^{5}, 1 ≤ k ≤ 5$) өгөгдөнө.

Дараагийн $n$ ширхэг мөрөнд замын шулууны тэгшитгэлийн коэффициентүүд болох 3-н бүхэл тоо $A_{i}, B_{i}, C_{i}$ ($|A_{i}|, |B_{i}|, |C_{i}| ≤ 10^{5}$, $A_{i}^{2} + B_{i}^{2} ≠ 0$) өгөгдөнө.

Аль ч 2 зам хоорондоо давхцахгүй.

Гаралт

Хэрвээ хариулт олдохгүй бол $NO$ гэж хэвлэнэ үү.

Харин олдож байвал эхний мөрөнд $YES$ гэж хэвлэнэ үү.

2 дахь мөрөнд нийт хэрэглэгдсэн замын тэмдэгний тоо хэмжээ болох $m$ ($m ≤ k$) бүхэл тоо өгөгдөнө. Дараагийн $m$ ширхэг мөрөнд эдгээр замын тэмдэгний тодорхойлолтыг хэвлэнэ үү.

Нэг ширхэг замын тэмдэгний тодорхойлолт нь 2 ширхэг бүхэл тоо $v, u$-оос бүтнэ. Хэрвээ $u$ болон $v$ нь хоорондоо ялгаатай бөгөөд $1$-ээс $n$-ын хоорондох бүхэл тоонууд байвал замын тэмдэг $v$ болон $u$ дугаартай замын огтлолцол дээр байна гэж үзнэ. Хэрвээ $u =  - 1$ бөгөөд $v$ нь $1$-ээс $n$-ын хоорондох бүхэл тоо бол замын тэмдэг зөвхөн $v$ зам дээр байгаа бөгөөд өөр аль ч замд хамаарагдахгүй гэж үзнэ. Замын тэмдэгний тодорхойлолт энэ 2-оос өөр тэмдэглэгээтэй бол таний хариултыг буруу гэж үзнэ. Хэрвээ $v = u$ эсвэл зам $v$ болон зам $u$ хоорондоо огтлолцохгүй байвал таны хариултыг мөн буруу гэж авч үзнэ.

Замын дугаарууд оролтонд өгөгдсөн дарааллаараа $1$-ээс эхлэн дугаарлагдсан.

Орчуулсан: Энхлут

Жишээ тэстүүд

Оролт
3 1
1 0 0
0 -1 0
7 -93 0
Гаралт
YES
1
1 2
Оролт
3 1
1 0 0
0 1 0
1 1 3
Гаралт
NO
Оролт
2 3
3 4 5
5 6 7
Гаралт
YES
2
1 -1
2 -1

Тэмдэглэл

Та $m$-ыг хамгийн бага байлгах шаардлагагүй, гэхдээ $k$-г хэтрэхгүй байх ёстой.

Эхний жишээнд бүх 3-н ширхэг зам (0,0) гэсэн цэгт огтлолцож байна.

2 дахь жишээнд бүх 3-н ширхэг зам гурвалжин үүсгэж байгаа бөгөөд ганцхан ширхэг замын тэмдэгийг бүх зам дээр байрлуулах боломжгүй.

Сэтгэгдлүүдийг ачааллаж байна...