C. Бээлийнүүд

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

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

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

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

$S$ хотод $n$ хүүхэдтэй зул сарын үдэшлэг болов. Бүх хүүхдүүд үдэшлэгт бээлийтэй иржээ. Мөн бээлийнүүд нь ялгаатай өнгөнүүдтэй, гэхдээ хүүхэд бүр зүүн болон баруун гартаа ижил өнгийн бээлийтэй. Бээлийнүүдийн өнгөнүүдийг $1$ ээс $m$ хүртэлх бүхэл тоогоор дуугаарласан ба хүүхдүүд ч гэсэн $1$ ээс $n$ хүртэл дугаарлагдсан. Тэгээд $i$ дахь хүүхдийн $2$ бээлий нь хоёулаа $c_i$ өнгөтэй.

Үдэшлэгт Санта Клаус (Оросоор өвлийн аав) түүний цасан охид болон хүүхдүүд сайхан чимэглэсэн зул сарын модоо тойроод бүжиглэж байв. Үнэндээ бүх зүйл сайхан байсан учраас хүүхдүүд ялгаатай өнгийн бээлийнүүд өмсөхийг хүсжээ. Тэд бээлийгээ хоорондоо солилцохоор шийдсэн ба төгсгөлд нь хүүхэд бүр баруун зүүн гартаа нэг нэг бээлийтэй байна. Эдгээр хоёр бээлий нь хоорондоо ялгаатай өнгөнүүдтэй байх ба бүх бээлий ижил хэмжээтэй мөн бүх хүүхдэд таарна.

Хүүхдүүд бээлийнүүдээ санаандгүй солилцож эхэлсэн боловч хүүхэд бүр ялгаатай өнгийн хос бээлийтэй байх нөхцөлд хүрч чадахгүй байв. Вазиля Петров - нэг хүүхдийх нь аав ба хүүхдүүдийн энэ санаа нь боломжгүй байж магадгүйг анзаарчээ. Түүнээс гадна тэр математикч тул ялгаатай өнгийн бээлийтэй хүүхдүүдийн тоо хамгийн их байхаар бээлий хувиарлах аргийг бодож олсон. Таны хийх ёстой зүйл бол түүний аргийг давтах юм. Баруун болон зүүн гарын бээлий ялгаатай , хүүхэд бүр хамгийн сүүлд баруун зүүн гартаа нэг нэг бээлийтэй байхийг анхаараарай.

Оролт

Эхний мөрөнд $n$, $m$ бүхэл тоонууд – хүүхдүүдийн тоо болон боломжтой бээлийнүүдийн өнгөнүүдийн тоо. $(1 ≤n ≤ 5000; 1 ≤ m ≤ 100)$. Хоёр дахь мөрөнд n ширхэг $c_1$, $c_2$, ... $c_n$ тоонууд байна. $c_i$ нь $i$ дугаар хүүхдийн одоо өмсөж байгаа бээлийний өнгө. $(1 ≤ ci ≤ m)$.

Гаралт

Эхний мөрөнд хамгийн сүүлд өөр өнгийн хос бээлийтэй байх хамгийн их хүүхдийн тоо. Дараагийн $n$ мөрөнд дээрх тохиолдолд байж болох хүүхдүүдийн өмссөн бээлийнүүд. Эдгээд мөрүүдийн $i$ дугаар мөр бүрт $2$ бүхэл тоо зайгаар тусгаарлагдсан байна: $i$ дугаар хүүхдийн өмссөн зүүн болон баруун гарын бээлийний өнгө. Хэрэв олон хариутай бол алийг нь ч хэвлэсэн болно.

Орчуулсан: Gantushig

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

Оролт
6 3
1 3 2 2 1 1
Гаралт
6
2 1
1 2
2 1
1 3
1 2
3 1
Оролт
4 2
1 2 1 1
Гаралт
2
1 2
1 1
2 1
1 1
Сэтгэгдлүүдийг ачааллаж байна...